1 /* Instruction scheduling pass.
2 Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000,
3 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
4 Free Software Foundation, Inc.
5 Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
6 and currently maintained by, Jim Wilson (wilson@cygnus.com)
8 This file is part of GCC.
10 GCC is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free
12 Software Foundation; either version 3, or (at your option) any later
15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING3. If not see
22 <http://www.gnu.org/licenses/>. */
24 /* Instruction scheduling pass. This file, along with sched-deps.c,
25 contains the generic parts. The actual entry point is found for
26 the normal instruction scheduling pass is found in sched-rgn.c.
28 We compute insn priorities based on data dependencies. Flow
29 analysis only creates a fraction of the data-dependencies we must
30 observe: namely, only those dependencies which the combiner can be
31 expected to use. For this pass, we must therefore create the
32 remaining dependencies we need to observe: register dependencies,
33 memory dependencies, dependencies to keep function calls in order,
34 and the dependence between a conditional branch and the setting of
35 condition codes are all dealt with here.
37 The scheduler first traverses the data flow graph, starting with
38 the last instruction, and proceeding to the first, assigning values
39 to insn_priority as it goes. This sorts the instructions
40 topologically by data dependence.
42 Once priorities have been established, we order the insns using
43 list scheduling. This works as follows: starting with a list of
44 all the ready insns, and sorted according to priority number, we
45 schedule the insn from the end of the list by placing its
46 predecessors in the list according to their priority order. We
47 consider this insn scheduled by setting the pointer to the "end" of
48 the list to point to the previous insn. When an insn has no
49 predecessors, we either queue it until sufficient time has elapsed
50 or add it to the ready list. As the instructions are scheduled or
51 when stalls are introduced, the queue advances and dumps insns into
52 the ready list. When all insns down to the lowest priority have
53 been scheduled, the critical path of the basic block has been made
54 as short as possible. The remaining insns are then scheduled in
57 The following list shows the order in which we want to break ties
58 among insns in the ready list:
60 1. choose insn with the longest path to end of bb, ties
62 2. choose insn with least contribution to register pressure,
64 3. prefer in-block upon interblock motion, ties broken by
65 4. prefer useful upon speculative motion, ties broken by
66 5. choose insn with largest control flow probability, ties
68 6. choose insn with the least dependences upon the previously
69 scheduled insn, or finally
70 7 choose the insn which has the most insns dependent on it.
71 8. choose insn with lowest UID.
73 Memory references complicate matters. Only if we can be certain
74 that memory references are not part of the data dependency graph
75 (via true, anti, or output dependence), can we move operations past
76 memory references. To first approximation, reads can be done
77 independently, while writes introduce dependencies. Better
78 approximations will yield fewer dependencies.
80 Before reload, an extended analysis of interblock data dependences
81 is required for interblock scheduling. This is performed in
82 compute_block_backward_dependences ().
84 Dependencies set up by memory references are treated in exactly the
85 same way as other dependencies, by using insn backward dependences
86 INSN_BACK_DEPS. INSN_BACK_DEPS are translated into forward dependences
87 INSN_FORW_DEPS the purpose of forward list scheduling.
89 Having optimized the critical path, we may have also unduly
90 extended the lifetimes of some registers. If an operation requires
91 that constants be loaded into registers, it is certainly desirable
92 to load those constants as early as necessary, but no earlier.
93 I.e., it will not do to load up a bunch of registers at the
94 beginning of a basic block only to use them at the end, if they
95 could be loaded later, since this may result in excessive register
98 Note that since branches are never in basic blocks, but only end
99 basic blocks, this pass will not move branches. But that is ok,
100 since we can use GNU's delayed branch scheduling pass to take care
103 Also note that no further optimizations based on algebraic
104 identities are performed, so this pass would be a good one to
105 perform instruction splitting, such as breaking up a multiply
106 instruction into shifts and adds where that is profitable.
108 Given the memory aliasing analysis that this pass should perform,
109 it should be possible to remove redundant stores to memory, and to
110 load values from registers instead of hitting memory.
112 Before reload, speculative insns are moved only if a 'proof' exists
113 that no exception will be caused by this, and if no live registers
114 exist that inhibit the motion (live registers constraints are not
115 represented by data dependence edges).
117 This pass must update information that subsequent passes expect to
118 be correct. Namely: reg_n_refs, reg_n_sets, reg_n_deaths,
119 reg_n_calls_crossed, and reg_live_length. Also, BB_HEAD, BB_END.
121 The information in the line number notes is carefully retained by
122 this pass. Notes that refer to the starting and ending of
123 exception regions are also carefully retained by this pass. All
124 other NOTE insns are grouped in their same relative order at the
125 beginning of basic blocks and regions that have been scheduled. */
129 #include "coretypes.h"
131 #include "diagnostic-core.h"
132 #include "hard-reg-set.h"
136 #include "function.h"
138 #include "insn-config.h"
139 #include "insn-attr.h"
142 #include "sched-int.h"
144 #include "common/common-target.h"
150 #include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.h. */
153 #ifdef INSN_SCHEDULING
155 /* issue_rate is the number of insns that can be scheduled in the same
156 machine cycle. It can be defined in the config/mach/mach.h file,
157 otherwise we set it to 1. */
161 /* This can be set to true by a backend if the scheduler should not
162 enable a DCE pass. */
165 /* The current initiation interval used when modulo scheduling. */
166 static int modulo_ii
;
168 /* The maximum number of stages we are prepared to handle. */
169 static int modulo_max_stages
;
171 /* The number of insns that exist in each iteration of the loop. We use this
172 to detect when we've scheduled all insns from the first iteration. */
173 static int modulo_n_insns
;
175 /* The current count of insns in the first iteration of the loop that have
176 already been scheduled. */
177 static int modulo_insns_scheduled
;
179 /* The maximum uid of insns from the first iteration of the loop. */
180 static int modulo_iter0_max_uid
;
182 /* The number of times we should attempt to backtrack when modulo scheduling.
183 Decreased each time we have to backtrack. */
184 static int modulo_backtracks_left
;
186 /* The stage in which the last insn from the original loop was
188 static int modulo_last_stage
;
190 /* sched-verbose controls the amount of debugging output the
191 scheduler prints. It is controlled by -fsched-verbose=N:
192 N>0 and no -DSR : the output is directed to stderr.
193 N>=10 will direct the printouts to stderr (regardless of -dSR).
195 N=2: bb's probabilities, detailed ready list info, unit/insn info.
196 N=3: rtl at abort point, control-flow, regions info.
197 N=5: dependences info. */
199 int sched_verbose
= 0;
201 /* Debugging file. All printouts are sent to dump, which is always set,
202 either to stderr, or to the dump listing file (-dRS). */
203 FILE *sched_dump
= 0;
205 /* This is a placeholder for the scheduler parameters common
206 to all schedulers. */
207 struct common_sched_info_def
*common_sched_info
;
209 #define INSN_TICK(INSN) (HID (INSN)->tick)
210 #define INSN_EXACT_TICK(INSN) (HID (INSN)->exact_tick)
211 #define INSN_TICK_ESTIMATE(INSN) (HID (INSN)->tick_estimate)
212 #define INTER_TICK(INSN) (HID (INSN)->inter_tick)
213 #define FEEDS_BACKTRACK_INSN(INSN) (HID (INSN)->feeds_backtrack_insn)
214 #define SHADOW_P(INSN) (HID (INSN)->shadow_p)
215 #define MUST_RECOMPUTE_SPEC_P(INSN) (HID (INSN)->must_recompute_spec)
217 /* If INSN_TICK of an instruction is equal to INVALID_TICK,
218 then it should be recalculated from scratch. */
219 #define INVALID_TICK (-(max_insn_queue_index + 1))
220 /* The minimal value of the INSN_TICK of an instruction. */
221 #define MIN_TICK (-max_insn_queue_index)
223 /* List of important notes we must keep around. This is a pointer to the
224 last element in the list. */
227 static struct spec_info_def spec_info_var
;
228 /* Description of the speculative part of the scheduling.
229 If NULL - no speculation. */
230 spec_info_t spec_info
= NULL
;
232 /* True, if recovery block was added during scheduling of current block.
233 Used to determine, if we need to fix INSN_TICKs. */
234 static bool haifa_recovery_bb_recently_added_p
;
236 /* True, if recovery block was added during this scheduling pass.
237 Used to determine if we should have empty memory pools of dependencies
238 after finishing current region. */
239 bool haifa_recovery_bb_ever_added_p
;
241 /* Counters of different types of speculative instructions. */
242 static int nr_begin_data
, nr_be_in_data
, nr_begin_control
, nr_be_in_control
;
244 /* Array used in {unlink, restore}_bb_notes. */
245 static rtx
*bb_header
= 0;
247 /* Basic block after which recovery blocks will be created. */
248 static basic_block before_recovery
;
250 /* Basic block just before the EXIT_BLOCK and after recovery, if we have
252 basic_block after_recovery
;
254 /* FALSE if we add bb to another region, so we don't need to initialize it. */
255 bool adding_bb_to_current_region_p
= true;
259 /* An instruction is ready to be scheduled when all insns preceding it
260 have already been scheduled. It is important to ensure that all
261 insns which use its result will not be executed until its result
262 has been computed. An insn is maintained in one of four structures:
264 (P) the "Pending" set of insns which cannot be scheduled until
265 their dependencies have been satisfied.
266 (Q) the "Queued" set of insns that can be scheduled when sufficient
268 (R) the "Ready" list of unscheduled, uncommitted insns.
269 (S) the "Scheduled" list of insns.
271 Initially, all insns are either "Pending" or "Ready" depending on
272 whether their dependencies are satisfied.
274 Insns move from the "Ready" list to the "Scheduled" list as they
275 are committed to the schedule. As this occurs, the insns in the
276 "Pending" list have their dependencies satisfied and move to either
277 the "Ready" list or the "Queued" set depending on whether
278 sufficient time has passed to make them ready. As time passes,
279 insns move from the "Queued" set to the "Ready" list.
281 The "Pending" list (P) are the insns in the INSN_FORW_DEPS of the
282 unscheduled insns, i.e., those that are ready, queued, and pending.
283 The "Queued" set (Q) is implemented by the variable `insn_queue'.
284 The "Ready" list (R) is implemented by the variables `ready' and
286 The "Scheduled" list (S) is the new insn chain built by this pass.
288 The transition (R->S) is implemented in the scheduling loop in
289 `schedule_block' when the best insn to schedule is chosen.
290 The transitions (P->R and P->Q) are implemented in `schedule_insn' as
291 insns move from the ready list to the scheduled list.
292 The transition (Q->R) is implemented in 'queue_to_insn' as time
293 passes or stalls are introduced. */
295 /* Implement a circular buffer to delay instructions until sufficient
296 time has passed. For the new pipeline description interface,
297 MAX_INSN_QUEUE_INDEX is a power of two minus one which is not less
298 than maximal time of instruction execution computed by genattr.c on
299 the base maximal time of functional unit reservations and getting a
300 result. This is the longest time an insn may be queued. */
302 static rtx
*insn_queue
;
303 static int q_ptr
= 0;
304 static int q_size
= 0;
305 #define NEXT_Q(X) (((X)+1) & max_insn_queue_index)
306 #define NEXT_Q_AFTER(X, C) (((X)+C) & max_insn_queue_index)
308 #define QUEUE_SCHEDULED (-3)
309 #define QUEUE_NOWHERE (-2)
310 #define QUEUE_READY (-1)
311 /* QUEUE_SCHEDULED - INSN is scheduled.
312 QUEUE_NOWHERE - INSN isn't scheduled yet and is neither in
314 QUEUE_READY - INSN is in ready list.
315 N >= 0 - INSN queued for X [where NEXT_Q_AFTER (q_ptr, X) == N] cycles. */
317 #define QUEUE_INDEX(INSN) (HID (INSN)->queue_index)
319 /* The following variable value refers for all current and future
320 reservations of the processor units. */
323 /* The following variable value is size of memory representing all
324 current and future reservations of the processor units. */
325 size_t dfa_state_size
;
327 /* The following array is used to find the best insn from ready when
328 the automaton pipeline interface is used. */
329 char *ready_try
= NULL
;
331 /* The ready list. */
332 struct ready_list ready
= {NULL
, 0, 0, 0, 0};
334 /* The pointer to the ready list (to be removed). */
335 static struct ready_list
*readyp
= &ready
;
337 /* Scheduling clock. */
338 static int clock_var
;
340 /* Clock at which the previous instruction was issued. */
341 static int last_clock_var
;
343 /* Set to true if, when queuing a shadow insn, we discover that it would be
344 scheduled too late. */
345 static bool must_backtrack
;
347 /* The following variable value is number of essential insns issued on
348 the current cycle. An insn is essential one if it changes the
350 int cycle_issued_insns
;
352 /* This records the actual schedule. It is built up during the main phase
353 of schedule_block, and afterwards used to reorder the insns in the RTL. */
354 static VEC(rtx
, heap
) *scheduled_insns
;
356 static int may_trap_exp (const_rtx
, int);
358 /* Nonzero iff the address is comprised from at most 1 register. */
359 #define CONST_BASED_ADDRESS_P(x) \
361 || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
362 || (GET_CODE (x) == LO_SUM)) \
363 && (CONSTANT_P (XEXP (x, 0)) \
364 || CONSTANT_P (XEXP (x, 1)))))
366 /* Returns a class that insn with GET_DEST(insn)=x may belong to,
367 as found by analyzing insn's expression. */
370 static int haifa_luid_for_non_insn (rtx x
);
372 /* Haifa version of sched_info hooks common to all headers. */
373 const struct common_sched_info_def haifa_common_sched_info
=
375 NULL
, /* fix_recovery_cfg */
376 NULL
, /* add_block */
377 NULL
, /* estimate_number_of_insns */
378 haifa_luid_for_non_insn
, /* luid_for_non_insn */
379 SCHED_PASS_UNKNOWN
/* sched_pass_id */
382 /* Mapping from instruction UID to its Logical UID. */
383 VEC (int, heap
) *sched_luids
= NULL
;
385 /* Next LUID to assign to an instruction. */
386 int sched_max_luid
= 1;
388 /* Haifa Instruction Data. */
389 VEC (haifa_insn_data_def
, heap
) *h_i_d
= NULL
;
391 void (* sched_init_only_bb
) (basic_block
, basic_block
);
393 /* Split block function. Different schedulers might use different functions
394 to handle their internal data consistent. */
395 basic_block (* sched_split_block
) (basic_block
, rtx
);
397 /* Create empty basic block after the specified block. */
398 basic_block (* sched_create_empty_bb
) (basic_block
);
400 /* Return the number of cycles until INSN is expected to be ready.
401 Return zero if it already is. */
403 insn_delay (rtx insn
)
405 return MAX (INSN_TICK (insn
) - clock_var
, 0);
409 may_trap_exp (const_rtx x
, int is_store
)
418 if (code
== MEM
&& may_trap_p (x
))
425 /* The insn uses memory: a volatile load. */
426 if (MEM_VOLATILE_P (x
))
428 /* An exception-free load. */
431 /* A load with 1 base register, to be further checked. */
432 if (CONST_BASED_ADDRESS_P (XEXP (x
, 0)))
433 return PFREE_CANDIDATE
;
434 /* No info on the load, to be further checked. */
435 return PRISKY_CANDIDATE
;
440 int i
, insn_class
= TRAP_FREE
;
442 /* Neither store nor load, check if it may cause a trap. */
445 /* Recursive step: walk the insn... */
446 fmt
= GET_RTX_FORMAT (code
);
447 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
451 int tmp_class
= may_trap_exp (XEXP (x
, i
), is_store
);
452 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
454 else if (fmt
[i
] == 'E')
457 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
459 int tmp_class
= may_trap_exp (XVECEXP (x
, i
, j
), is_store
);
460 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
461 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
465 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
472 /* Classifies rtx X of an insn for the purpose of verifying that X can be
473 executed speculatively (and consequently the insn can be moved
474 speculatively), by examining X, returning:
475 TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
476 TRAP_FREE: non-load insn.
477 IFREE: load from a globally safe location.
478 IRISKY: volatile load.
479 PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
480 being either PFREE or PRISKY. */
483 haifa_classify_rtx (const_rtx x
)
485 int tmp_class
= TRAP_FREE
;
486 int insn_class
= TRAP_FREE
;
489 if (GET_CODE (x
) == PARALLEL
)
491 int i
, len
= XVECLEN (x
, 0);
493 for (i
= len
- 1; i
>= 0; i
--)
495 tmp_class
= haifa_classify_rtx (XVECEXP (x
, 0, i
));
496 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
497 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
507 /* Test if it is a 'store'. */
508 tmp_class
= may_trap_exp (XEXP (x
, 0), 1);
511 /* Test if it is a store. */
512 tmp_class
= may_trap_exp (SET_DEST (x
), 1);
513 if (tmp_class
== TRAP_RISKY
)
515 /* Test if it is a load. */
517 WORST_CLASS (tmp_class
,
518 may_trap_exp (SET_SRC (x
), 0));
521 tmp_class
= haifa_classify_rtx (COND_EXEC_CODE (x
));
522 if (tmp_class
== TRAP_RISKY
)
524 tmp_class
= WORST_CLASS (tmp_class
,
525 may_trap_exp (COND_EXEC_TEST (x
), 0));
528 tmp_class
= TRAP_RISKY
;
532 insn_class
= tmp_class
;
539 haifa_classify_insn (const_rtx insn
)
541 return haifa_classify_rtx (PATTERN (insn
));
544 /* After the scheduler initialization function has been called, this function
545 can be called to enable modulo scheduling. II is the initiation interval
546 we should use, it affects the delays for delay_pairs that were recorded as
547 separated by a given number of stages.
549 MAX_STAGES provides us with a limit
550 after which we give up scheduling; the caller must have unrolled at least
551 as many copies of the loop body and recorded delay_pairs for them.
553 INSNS is the number of real (non-debug) insns in one iteration of
554 the loop. MAX_UID can be used to test whether an insn belongs to
555 the first iteration of the loop; all of them have a uid lower than
558 set_modulo_params (int ii
, int max_stages
, int insns
, int max_uid
)
561 modulo_max_stages
= max_stages
;
562 modulo_n_insns
= insns
;
563 modulo_iter0_max_uid
= max_uid
;
564 modulo_backtracks_left
= PARAM_VALUE (PARAM_MAX_MODULO_BACKTRACK_ATTEMPTS
);
567 /* A structure to record a pair of insns where the first one is a real
568 insn that has delay slots, and the second is its delayed shadow.
569 I1 is scheduled normally and will emit an assembly instruction,
570 while I2 describes the side effect that takes place at the
571 transition between cycles CYCLES and (CYCLES + 1) after I1. */
574 struct delay_pair
*next_same_i1
;
577 /* When doing modulo scheduling, we a delay_pair can also be used to
578 show that I1 and I2 are the same insn in a different stage. If that
579 is the case, STAGES will be nonzero. */
583 /* Two hash tables to record delay_pairs, one indexed by I1 and the other
585 static htab_t delay_htab
;
586 static htab_t delay_htab_i2
;
588 /* Called through htab_traverse. Walk the hashtable using I2 as
589 index, and delete all elements involving an UID higher than
590 that pointed to by *DATA. */
592 htab_i2_traverse (void **slot
, void *data
)
594 int maxuid
= *(int *)data
;
595 struct delay_pair
*p
= *(struct delay_pair
**)slot
;
596 if (INSN_UID (p
->i2
) >= maxuid
|| INSN_UID (p
->i1
) >= maxuid
)
598 htab_clear_slot (delay_htab_i2
, slot
);
603 /* Called through htab_traverse. Walk the hashtable using I2 as
604 index, and delete all elements involving an UID higher than
605 that pointed to by *DATA. */
607 htab_i1_traverse (void **slot
, void *data
)
609 int maxuid
= *(int *)data
;
610 struct delay_pair
**pslot
= (struct delay_pair
**)slot
;
611 struct delay_pair
*p
, *first
, **pprev
;
613 if (INSN_UID ((*pslot
)->i1
) >= maxuid
)
615 htab_clear_slot (delay_htab
, slot
);
619 for (p
= *pslot
; p
; p
= p
->next_same_i1
)
621 if (INSN_UID (p
->i2
) < maxuid
)
624 pprev
= &p
->next_same_i1
;
629 htab_clear_slot (delay_htab
, slot
);
635 /* Discard all delay pairs which involve an insn with an UID higher
638 discard_delay_pairs_above (int max_uid
)
640 htab_traverse (delay_htab
, htab_i1_traverse
, &max_uid
);
641 htab_traverse (delay_htab_i2
, htab_i2_traverse
, &max_uid
);
644 /* Returns a hash value for X (which really is a delay_pair), based on
647 delay_hash_i1 (const void *x
)
649 return htab_hash_pointer (((const struct delay_pair
*) x
)->i1
);
652 /* Returns a hash value for X (which really is a delay_pair), based on
655 delay_hash_i2 (const void *x
)
657 return htab_hash_pointer (((const struct delay_pair
*) x
)->i2
);
660 /* Return nonzero if I1 of pair X is the same as that of pair Y. */
662 delay_i1_eq (const void *x
, const void *y
)
664 return ((const struct delay_pair
*) x
)->i1
== y
;
667 /* Return nonzero if I2 of pair X is the same as that of pair Y. */
669 delay_i2_eq (const void *x
, const void *y
)
671 return ((const struct delay_pair
*) x
)->i2
== y
;
674 /* This function can be called by a port just before it starts the final
675 scheduling pass. It records the fact that an instruction with delay
676 slots has been split into two insns, I1 and I2. The first one will be
677 scheduled normally and initiates the operation. The second one is a
678 shadow which must follow a specific number of cycles after I1; its only
679 purpose is to show the side effect that occurs at that cycle in the RTL.
680 If a JUMP_INSN or a CALL_INSN has been split, I1 should be a normal INSN,
681 while I2 retains the original insn type.
683 There are two ways in which the number of cycles can be specified,
684 involving the CYCLES and STAGES arguments to this function. If STAGES
685 is zero, we just use the value of CYCLES. Otherwise, STAGES is a factor
686 which is multiplied by MODULO_II to give the number of cycles. This is
687 only useful if the caller also calls set_modulo_params to enable modulo
691 record_delay_slot_pair (rtx i1
, rtx i2
, int cycles
, int stages
)
693 struct delay_pair
*p
= XNEW (struct delay_pair
);
694 struct delay_pair
**slot
;
703 delay_htab
= htab_create (10, delay_hash_i1
, delay_i1_eq
, NULL
);
704 delay_htab_i2
= htab_create (10, delay_hash_i2
, delay_i2_eq
, free
);
706 slot
= ((struct delay_pair
**)
707 htab_find_slot_with_hash (delay_htab
, i1
, htab_hash_pointer (i1
),
709 p
->next_same_i1
= *slot
;
711 slot
= ((struct delay_pair
**)
712 htab_find_slot_with_hash (delay_htab_i2
, i2
, htab_hash_pointer (i2
),
717 /* Examine the delay pair hashtable to see if INSN is a shadow for another,
718 and return the other insn if so. Return NULL otherwise. */
720 real_insn_for_shadow (rtx insn
)
722 struct delay_pair
*pair
;
724 if (delay_htab
== NULL
)
728 = (struct delay_pair
*)htab_find_with_hash (delay_htab_i2
, insn
,
729 htab_hash_pointer (insn
));
730 if (!pair
|| pair
->stages
> 0)
735 /* For a pair P of insns, return the fixed distance in cycles from the first
736 insn after which the second must be scheduled. */
738 pair_delay (struct delay_pair
*p
)
743 return p
->stages
* modulo_ii
;
746 /* Given an insn INSN, add a dependence on its delayed shadow if it
747 has one. Also try to find situations where shadows depend on each other
748 and add dependencies to the real insns to limit the amount of backtracking
751 add_delay_dependencies (rtx insn
)
753 struct delay_pair
*pair
;
754 sd_iterator_def sd_it
;
761 = (struct delay_pair
*)htab_find_with_hash (delay_htab_i2
, insn
,
762 htab_hash_pointer (insn
));
765 add_dependence (insn
, pair
->i1
, REG_DEP_ANTI
);
769 FOR_EACH_DEP (pair
->i2
, SD_LIST_BACK
, sd_it
, dep
)
771 rtx pro
= DEP_PRO (dep
);
772 struct delay_pair
*other_pair
773 = (struct delay_pair
*)htab_find_with_hash (delay_htab_i2
, pro
,
774 htab_hash_pointer (pro
));
775 if (!other_pair
|| other_pair
->stages
)
777 if (pair_delay (other_pair
) >= pair_delay (pair
))
779 if (sched_verbose
>= 4)
781 fprintf (sched_dump
, ";;\tadding dependence %d <- %d\n",
782 INSN_UID (other_pair
->i1
),
783 INSN_UID (pair
->i1
));
784 fprintf (sched_dump
, ";;\tpair1 %d <- %d, cost %d\n",
788 fprintf (sched_dump
, ";;\tpair2 %d <- %d, cost %d\n",
789 INSN_UID (other_pair
->i1
),
790 INSN_UID (other_pair
->i2
),
791 pair_delay (other_pair
));
793 add_dependence (pair
->i1
, other_pair
->i1
, REG_DEP_ANTI
);
798 /* Forward declarations. */
800 static int priority (rtx
);
801 static int rank_for_schedule (const void *, const void *);
802 static void swap_sort (rtx
*, int);
803 static void queue_insn (rtx
, int, const char *);
804 static int schedule_insn (rtx
);
805 static void adjust_priority (rtx
);
806 static void advance_one_cycle (void);
807 static void extend_h_i_d (void);
810 /* Notes handling mechanism:
811 =========================
812 Generally, NOTES are saved before scheduling and restored after scheduling.
813 The scheduler distinguishes between two types of notes:
815 (1) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes:
816 Before scheduling a region, a pointer to the note is added to the insn
817 that follows or precedes it. (This happens as part of the data dependence
818 computation). After scheduling an insn, the pointer contained in it is
819 used for regenerating the corresponding note (in reemit_notes).
821 (2) All other notes (e.g. INSN_DELETED): Before scheduling a block,
822 these notes are put in a list (in rm_other_notes() and
823 unlink_other_notes ()). After scheduling the block, these notes are
824 inserted at the beginning of the block (in schedule_block()). */
826 static void ready_add (struct ready_list
*, rtx
, bool);
827 static rtx
ready_remove_first (struct ready_list
*);
828 static rtx
ready_remove_first_dispatch (struct ready_list
*ready
);
830 static void queue_to_ready (struct ready_list
*);
831 static int early_queue_to_ready (state_t
, struct ready_list
*);
833 static void debug_ready_list (struct ready_list
*);
835 /* The following functions are used to implement multi-pass scheduling
836 on the first cycle. */
837 static rtx
ready_remove (struct ready_list
*, int);
838 static void ready_remove_insn (rtx
);
840 static void fix_inter_tick (rtx
, rtx
);
841 static int fix_tick_ready (rtx
);
842 static void change_queue_index (rtx
, int);
844 /* The following functions are used to implement scheduling of data/control
845 speculative instructions. */
847 static void extend_h_i_d (void);
848 static void init_h_i_d (rtx
);
849 static int haifa_speculate_insn (rtx
, ds_t
, rtx
*);
850 static void generate_recovery_code (rtx
);
851 static void process_insn_forw_deps_be_in_spec (rtx
, rtx
, ds_t
);
852 static void begin_speculative_block (rtx
);
853 static void add_to_speculative_block (rtx
);
854 static void init_before_recovery (basic_block
*);
855 static void create_check_block_twin (rtx
, bool);
856 static void fix_recovery_deps (basic_block
);
857 static bool haifa_change_pattern (rtx
, rtx
);
858 static void dump_new_block_header (int, basic_block
, rtx
, rtx
);
859 static void restore_bb_notes (basic_block
);
860 static void fix_jump_move (rtx
);
861 static void move_block_after_check (rtx
);
862 static void move_succs (VEC(edge
,gc
) **, basic_block
);
863 static void sched_remove_insn (rtx
);
864 static void clear_priorities (rtx
, rtx_vec_t
*);
865 static void calc_priorities (rtx_vec_t
);
866 static void add_jump_dependencies (rtx
, rtx
);
868 #endif /* INSN_SCHEDULING */
870 /* Point to state used for the current scheduling pass. */
871 struct haifa_sched_info
*current_sched_info
;
873 #ifndef INSN_SCHEDULING
875 schedule_insns (void)
880 /* Do register pressure sensitive insn scheduling if the flag is set
882 enum sched_pressure_algorithm sched_pressure
;
884 /* Map regno -> its pressure class. The map defined only when
885 SCHED_PRESSURE != SCHED_PRESSURE_NONE. */
886 enum reg_class
*sched_regno_pressure_class
;
888 /* The current register pressure. Only elements corresponding pressure
889 classes are defined. */
890 static int curr_reg_pressure
[N_REG_CLASSES
];
892 /* Saved value of the previous array. */
893 static int saved_reg_pressure
[N_REG_CLASSES
];
895 /* Register living at given scheduling point. */
896 static bitmap curr_reg_live
;
898 /* Saved value of the previous array. */
899 static bitmap saved_reg_live
;
901 /* Registers mentioned in the current region. */
902 static bitmap region_ref_regs
;
904 /* Initiate register pressure relative info for scheduling the current
905 region. Currently it is only clearing register mentioned in the
908 sched_init_region_reg_pressure_info (void)
910 bitmap_clear (region_ref_regs
);
913 /* PRESSURE[CL] describes the pressure on register class CL. Update it
914 for the birth (if BIRTH_P) or death (if !BIRTH_P) of register REGNO.
915 LIVE tracks the set of live registers; if it is null, assume that
916 every birth or death is genuine. */
918 mark_regno_birth_or_death (bitmap live
, int *pressure
, int regno
, bool birth_p
)
920 enum reg_class pressure_class
;
922 pressure_class
= sched_regno_pressure_class
[regno
];
923 if (regno
>= FIRST_PSEUDO_REGISTER
)
925 if (pressure_class
!= NO_REGS
)
929 if (!live
|| bitmap_set_bit (live
, regno
))
930 pressure
[pressure_class
]
931 += (ira_reg_class_max_nregs
932 [pressure_class
][PSEUDO_REGNO_MODE (regno
)]);
936 if (!live
|| bitmap_clear_bit (live
, regno
))
937 pressure
[pressure_class
]
938 -= (ira_reg_class_max_nregs
939 [pressure_class
][PSEUDO_REGNO_MODE (regno
)]);
943 else if (pressure_class
!= NO_REGS
944 && ! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
))
948 if (!live
|| bitmap_set_bit (live
, regno
))
949 pressure
[pressure_class
]++;
953 if (!live
|| bitmap_clear_bit (live
, regno
))
954 pressure
[pressure_class
]--;
959 /* Initiate current register pressure related info from living
960 registers given by LIVE. */
962 initiate_reg_pressure_info (bitmap live
)
968 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
969 curr_reg_pressure
[ira_pressure_classes
[i
]] = 0;
970 bitmap_clear (curr_reg_live
);
971 EXECUTE_IF_SET_IN_BITMAP (live
, 0, j
, bi
)
972 if (sched_pressure
== SCHED_PRESSURE_MODEL
973 || current_nr_blocks
== 1
974 || bitmap_bit_p (region_ref_regs
, j
))
975 mark_regno_birth_or_death (curr_reg_live
, curr_reg_pressure
, j
, true);
978 /* Mark registers in X as mentioned in the current region. */
980 setup_ref_regs (rtx x
)
983 const RTX_CODE code
= GET_CODE (x
);
989 if (HARD_REGISTER_NUM_P (regno
))
990 bitmap_set_range (region_ref_regs
, regno
,
991 hard_regno_nregs
[regno
][GET_MODE (x
)]);
993 bitmap_set_bit (region_ref_regs
, REGNO (x
));
996 fmt
= GET_RTX_FORMAT (code
);
997 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
999 setup_ref_regs (XEXP (x
, i
));
1000 else if (fmt
[i
] == 'E')
1002 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1003 setup_ref_regs (XVECEXP (x
, i
, j
));
1007 /* Initiate current register pressure related info at the start of
1010 initiate_bb_reg_pressure_info (basic_block bb
)
1012 unsigned int i ATTRIBUTE_UNUSED
;
1015 if (current_nr_blocks
> 1)
1016 FOR_BB_INSNS (bb
, insn
)
1017 if (NONDEBUG_INSN_P (insn
))
1018 setup_ref_regs (PATTERN (insn
));
1019 initiate_reg_pressure_info (df_get_live_in (bb
));
1020 #ifdef EH_RETURN_DATA_REGNO
1021 if (bb_has_eh_pred (bb
))
1024 unsigned int regno
= EH_RETURN_DATA_REGNO (i
);
1026 if (regno
== INVALID_REGNUM
)
1028 if (! bitmap_bit_p (df_get_live_in (bb
), regno
))
1029 mark_regno_birth_or_death (curr_reg_live
, curr_reg_pressure
,
1035 /* Save current register pressure related info. */
1037 save_reg_pressure (void)
1041 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1042 saved_reg_pressure
[ira_pressure_classes
[i
]]
1043 = curr_reg_pressure
[ira_pressure_classes
[i
]];
1044 bitmap_copy (saved_reg_live
, curr_reg_live
);
1047 /* Restore saved register pressure related info. */
1049 restore_reg_pressure (void)
1053 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1054 curr_reg_pressure
[ira_pressure_classes
[i
]]
1055 = saved_reg_pressure
[ira_pressure_classes
[i
]];
1056 bitmap_copy (curr_reg_live
, saved_reg_live
);
1059 /* Return TRUE if the register is dying after its USE. */
1061 dying_use_p (struct reg_use_data
*use
)
1063 struct reg_use_data
*next
;
1065 for (next
= use
->next_regno_use
; next
!= use
; next
= next
->next_regno_use
)
1066 if (NONDEBUG_INSN_P (next
->insn
)
1067 && QUEUE_INDEX (next
->insn
) != QUEUE_SCHEDULED
)
1072 /* Print info about the current register pressure and its excess for
1073 each pressure class. */
1075 print_curr_reg_pressure (void)
1080 fprintf (sched_dump
, ";;\t");
1081 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1083 cl
= ira_pressure_classes
[i
];
1084 gcc_assert (curr_reg_pressure
[cl
] >= 0);
1085 fprintf (sched_dump
, " %s:%d(%d)", reg_class_names
[cl
],
1086 curr_reg_pressure
[cl
],
1087 curr_reg_pressure
[cl
] - ira_class_hard_regs_num
[cl
]);
1089 fprintf (sched_dump
, "\n");
1092 /* Determine if INSN has a condition that is clobbered if a register
1093 in SET_REGS is modified. */
1095 cond_clobbered_p (rtx insn
, HARD_REG_SET set_regs
)
1097 rtx pat
= PATTERN (insn
);
1098 gcc_assert (GET_CODE (pat
) == COND_EXEC
);
1099 if (TEST_HARD_REG_BIT (set_regs
, REGNO (XEXP (COND_EXEC_TEST (pat
), 0))))
1101 sd_iterator_def sd_it
;
1103 haifa_change_pattern (insn
, ORIG_PAT (insn
));
1104 FOR_EACH_DEP (insn
, SD_LIST_BACK
, sd_it
, dep
)
1105 DEP_STATUS (dep
) &= ~DEP_CANCELLED
;
1106 TODO_SPEC (insn
) = HARD_DEP
;
1107 if (sched_verbose
>= 2)
1108 fprintf (sched_dump
,
1109 ";;\t\tdequeue insn %s because of clobbered condition\n",
1110 (*current_sched_info
->print_insn
) (insn
, 0));
1117 /* Look at the remaining dependencies for insn NEXT, and compute and return
1118 the TODO_SPEC value we should use for it. This is called after one of
1119 NEXT's dependencies has been resolved. */
1122 recompute_todo_spec (rtx next
)
1125 sd_iterator_def sd_it
;
1126 dep_t dep
, control_dep
= NULL
;
1129 bool first_p
= true;
1131 if (sd_lists_empty_p (next
, SD_LIST_BACK
))
1132 /* NEXT has all its dependencies resolved. */
1135 if (!sd_lists_empty_p (next
, SD_LIST_HARD_BACK
))
1138 /* Now we've got NEXT with speculative deps only.
1139 1. Look at the deps to see what we have to do.
1140 2. Check if we can do 'todo'. */
1143 FOR_EACH_DEP (next
, SD_LIST_BACK
, sd_it
, dep
)
1145 ds_t ds
= DEP_STATUS (dep
) & SPECULATIVE
;
1147 if (DEBUG_INSN_P (DEP_PRO (dep
)) && !DEBUG_INSN_P (next
))
1160 new_ds
= ds_merge (new_ds
, ds
);
1162 if (DEP_TYPE (dep
) == REG_DEP_CONTROL
)
1166 DEP_STATUS (dep
) &= ~DEP_CANCELLED
;
1170 if (n_control
== 1 && n_spec
== 0)
1172 rtx pro
, other
, new_pat
;
1173 rtx cond
= NULL_RTX
;
1175 rtx prev
= NULL_RTX
;
1179 if ((current_sched_info
->flags
& DO_PREDICATION
) == 0
1180 || (ORIG_PAT (next
) != NULL_RTX
1181 && PREDICATED_PAT (next
) == NULL_RTX
))
1184 pro
= DEP_PRO (control_dep
);
1185 other
= real_insn_for_shadow (pro
);
1186 if (other
!= NULL_RTX
)
1189 cond
= sched_get_reverse_condition_uncached (pro
);
1190 regno
= REGNO (XEXP (cond
, 0));
1192 /* Find the last scheduled insn that modifies the condition register.
1193 We can stop looking once we find the insn we depend on through the
1194 REG_DEP_CONTROL; if the condition register isn't modified after it,
1195 we know that it still has the right value. */
1196 if (QUEUE_INDEX (pro
) == QUEUE_SCHEDULED
)
1197 FOR_EACH_VEC_ELT_REVERSE (rtx
, scheduled_insns
, i
, prev
)
1201 find_all_hard_reg_sets (prev
, &t
);
1202 if (TEST_HARD_REG_BIT (t
, regno
))
1207 if (ORIG_PAT (next
) == NULL_RTX
)
1209 ORIG_PAT (next
) = PATTERN (next
);
1211 new_pat
= gen_rtx_COND_EXEC (VOIDmode
, cond
, PATTERN (next
));
1212 success
= haifa_change_pattern (next
, new_pat
);
1215 PREDICATED_PAT (next
) = new_pat
;
1217 else if (PATTERN (next
) != PREDICATED_PAT (next
))
1219 bool success
= haifa_change_pattern (next
,
1220 PREDICATED_PAT (next
));
1221 gcc_assert (success
);
1223 DEP_STATUS (control_dep
) |= DEP_CANCELLED
;
1227 if (PREDICATED_PAT (next
) != NULL_RTX
)
1229 int tick
= INSN_TICK (next
);
1230 bool success
= haifa_change_pattern (next
,
1232 INSN_TICK (next
) = tick
;
1233 gcc_assert (success
);
1236 /* We can't handle the case where there are both speculative and control
1237 dependencies, so we return HARD_DEP in such a case. Also fail if
1238 we have speculative dependencies with not enough points, or more than
1239 one control dependency. */
1240 if ((n_spec
> 0 && n_control
> 0)
1242 /* Too few points? */
1243 && ds_weak (new_ds
) < spec_info
->data_weakness_cutoff
)
1250 /* Pointer to the last instruction scheduled. */
1251 static rtx last_scheduled_insn
;
1253 /* Pointer to the last nondebug instruction scheduled within the
1254 block, or the prev_head of the scheduling block. Used by
1255 rank_for_schedule, so that insns independent of the last scheduled
1256 insn will be preferred over dependent instructions. */
1257 static rtx last_nondebug_scheduled_insn
;
1259 /* Pointer that iterates through the list of unscheduled insns if we
1260 have a dbg_cnt enabled. It always points at an insn prior to the
1261 first unscheduled one. */
1262 static rtx nonscheduled_insns_begin
;
1264 /* Cached cost of the instruction. Use below function to get cost of the
1265 insn. -1 here means that the field is not initialized. */
1266 #define INSN_COST(INSN) (HID (INSN)->cost)
1268 /* Compute cost of executing INSN.
1269 This is the number of cycles between instruction issue and
1270 instruction results. */
1272 insn_cost (rtx insn
)
1278 if (recog_memoized (insn
) < 0)
1281 cost
= insn_default_latency (insn
);
1288 cost
= INSN_COST (insn
);
1292 /* A USE insn, or something else we don't need to
1293 understand. We can't pass these directly to
1294 result_ready_cost or insn_default_latency because it will
1295 trigger a fatal error for unrecognizable insns. */
1296 if (recog_memoized (insn
) < 0)
1298 INSN_COST (insn
) = 0;
1303 cost
= insn_default_latency (insn
);
1307 INSN_COST (insn
) = cost
;
1314 /* Compute cost of dependence LINK.
1315 This is the number of cycles between instruction issue and
1316 instruction results.
1317 ??? We also use this function to call recog_memoized on all insns. */
1319 dep_cost_1 (dep_t link
, dw_t dw
)
1321 rtx insn
= DEP_PRO (link
);
1322 rtx used
= DEP_CON (link
);
1325 if (DEP_COST (link
) != UNKNOWN_DEP_COST
)
1326 return DEP_COST (link
);
1330 struct delay_pair
*delay_entry
;
1332 = (struct delay_pair
*)htab_find_with_hash (delay_htab_i2
, used
,
1333 htab_hash_pointer (used
));
1336 if (delay_entry
->i1
== insn
)
1338 DEP_COST (link
) = pair_delay (delay_entry
);
1339 return DEP_COST (link
);
1344 /* A USE insn should never require the value used to be computed.
1345 This allows the computation of a function's result and parameter
1346 values to overlap the return and call. We don't care about the
1347 dependence cost when only decreasing register pressure. */
1348 if (recog_memoized (used
) < 0)
1351 recog_memoized (insn
);
1355 enum reg_note dep_type
= DEP_TYPE (link
);
1357 cost
= insn_cost (insn
);
1359 if (INSN_CODE (insn
) >= 0)
1361 if (dep_type
== REG_DEP_ANTI
)
1363 else if (dep_type
== REG_DEP_OUTPUT
)
1365 cost
= (insn_default_latency (insn
)
1366 - insn_default_latency (used
));
1370 else if (bypass_p (insn
))
1371 cost
= insn_latency (insn
, used
);
1375 if (targetm
.sched
.adjust_cost_2
)
1376 cost
= targetm
.sched
.adjust_cost_2 (used
, (int) dep_type
, insn
, cost
,
1378 else if (targetm
.sched
.adjust_cost
!= NULL
)
1380 /* This variable is used for backward compatibility with the
1382 rtx dep_cost_rtx_link
= alloc_INSN_LIST (NULL_RTX
, NULL_RTX
);
1384 /* Make it self-cycled, so that if some tries to walk over this
1385 incomplete list he/she will be caught in an endless loop. */
1386 XEXP (dep_cost_rtx_link
, 1) = dep_cost_rtx_link
;
1388 /* Targets use only REG_NOTE_KIND of the link. */
1389 PUT_REG_NOTE_KIND (dep_cost_rtx_link
, DEP_TYPE (link
));
1391 cost
= targetm
.sched
.adjust_cost (used
, dep_cost_rtx_link
,
1394 free_INSN_LIST_node (dep_cost_rtx_link
);
1401 DEP_COST (link
) = cost
;
1405 /* Compute cost of dependence LINK.
1406 This is the number of cycles between instruction issue and
1407 instruction results. */
1409 dep_cost (dep_t link
)
1411 return dep_cost_1 (link
, 0);
1414 /* Use this sel-sched.c friendly function in reorder2 instead of increasing
1415 INSN_PRIORITY explicitly. */
1417 increase_insn_priority (rtx insn
, int amount
)
1419 if (!sel_sched_p ())
1421 /* We're dealing with haifa-sched.c INSN_PRIORITY. */
1422 if (INSN_PRIORITY_KNOWN (insn
))
1423 INSN_PRIORITY (insn
) += amount
;
1427 /* In sel-sched.c INSN_PRIORITY is not kept up to date.
1428 Use EXPR_PRIORITY instead. */
1429 sel_add_to_insn_priority (insn
, amount
);
1433 /* Return 'true' if DEP should be included in priority calculations. */
1435 contributes_to_priority_p (dep_t dep
)
1437 if (DEBUG_INSN_P (DEP_CON (dep
))
1438 || DEBUG_INSN_P (DEP_PRO (dep
)))
1441 /* Critical path is meaningful in block boundaries only. */
1442 if (!current_sched_info
->contributes_to_priority (DEP_CON (dep
),
1446 /* If flag COUNT_SPEC_IN_CRITICAL_PATH is set,
1447 then speculative instructions will less likely be
1448 scheduled. That is because the priority of
1449 their producers will increase, and, thus, the
1450 producers will more likely be scheduled, thus,
1451 resolving the dependence. */
1452 if (sched_deps_info
->generate_spec_deps
1453 && !(spec_info
->flags
& COUNT_SPEC_IN_CRITICAL_PATH
)
1454 && (DEP_STATUS (dep
) & SPECULATIVE
))
1460 /* Compute the number of nondebug deps in list LIST for INSN. */
1463 dep_list_size (rtx insn
, sd_list_types_def list
)
1465 sd_iterator_def sd_it
;
1467 int dbgcount
= 0, nodbgcount
= 0;
1469 if (!MAY_HAVE_DEBUG_INSNS
)
1470 return sd_lists_size (insn
, list
);
1472 FOR_EACH_DEP (insn
, list
, sd_it
, dep
)
1474 if (DEBUG_INSN_P (DEP_CON (dep
)))
1476 else if (!DEBUG_INSN_P (DEP_PRO (dep
)))
1480 gcc_assert (dbgcount
+ nodbgcount
== sd_lists_size (insn
, list
));
1485 /* Compute the priority number for INSN. */
1489 if (! INSN_P (insn
))
1492 /* We should not be interested in priority of an already scheduled insn. */
1493 gcc_assert (QUEUE_INDEX (insn
) != QUEUE_SCHEDULED
);
1495 if (!INSN_PRIORITY_KNOWN (insn
))
1497 int this_priority
= -1;
1499 if (dep_list_size (insn
, SD_LIST_FORW
) == 0)
1500 /* ??? We should set INSN_PRIORITY to insn_cost when and insn has
1501 some forward deps but all of them are ignored by
1502 contributes_to_priority hook. At the moment we set priority of
1504 this_priority
= insn_cost (insn
);
1507 rtx prev_first
, twin
;
1510 /* For recovery check instructions we calculate priority slightly
1511 different than that of normal instructions. Instead of walking
1512 through INSN_FORW_DEPS (check) list, we walk through
1513 INSN_FORW_DEPS list of each instruction in the corresponding
1516 /* Selective scheduling does not define RECOVERY_BLOCK macro. */
1517 rec
= sel_sched_p () ? NULL
: RECOVERY_BLOCK (insn
);
1518 if (!rec
|| rec
== EXIT_BLOCK_PTR
)
1520 prev_first
= PREV_INSN (insn
);
1525 prev_first
= NEXT_INSN (BB_HEAD (rec
));
1526 twin
= PREV_INSN (BB_END (rec
));
1531 sd_iterator_def sd_it
;
1534 FOR_EACH_DEP (twin
, SD_LIST_FORW
, sd_it
, dep
)
1539 next
= DEP_CON (dep
);
1541 if (BLOCK_FOR_INSN (next
) != rec
)
1545 if (!contributes_to_priority_p (dep
))
1549 cost
= dep_cost (dep
);
1552 struct _dep _dep1
, *dep1
= &_dep1
;
1554 init_dep (dep1
, insn
, next
, REG_DEP_ANTI
);
1556 cost
= dep_cost (dep1
);
1559 next_priority
= cost
+ priority (next
);
1561 if (next_priority
> this_priority
)
1562 this_priority
= next_priority
;
1566 twin
= PREV_INSN (twin
);
1568 while (twin
!= prev_first
);
1571 if (this_priority
< 0)
1573 gcc_assert (this_priority
== -1);
1575 this_priority
= insn_cost (insn
);
1578 INSN_PRIORITY (insn
) = this_priority
;
1579 INSN_PRIORITY_STATUS (insn
) = 1;
1582 return INSN_PRIORITY (insn
);
1585 /* Macros and functions for keeping the priority queue sorted, and
1586 dealing with queuing and dequeuing of instructions. */
1588 #define SCHED_SORT(READY, N_READY) \
1589 do { if ((N_READY) == 2) \
1590 swap_sort (READY, N_READY); \
1591 else if ((N_READY) > 2) \
1592 qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \
1595 /* For each pressure class CL, set DEATH[CL] to the number of registers
1596 in that class that die in INSN. */
1599 calculate_reg_deaths (rtx insn
, int *death
)
1602 struct reg_use_data
*use
;
1604 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1605 death
[ira_pressure_classes
[i
]] = 0;
1606 for (use
= INSN_REG_USE_LIST (insn
); use
!= NULL
; use
= use
->next_insn_use
)
1607 if (dying_use_p (use
))
1608 mark_regno_birth_or_death (0, death
, use
->regno
, true);
1611 /* Setup info about the current register pressure impact of scheduling
1612 INSN at the current scheduling point. */
1614 setup_insn_reg_pressure_info (rtx insn
)
1616 int i
, change
, before
, after
, hard_regno
;
1617 int excess_cost_change
;
1618 enum machine_mode mode
;
1620 struct reg_pressure_data
*pressure_info
;
1621 int *max_reg_pressure
;
1622 static int death
[N_REG_CLASSES
];
1624 gcc_checking_assert (!DEBUG_INSN_P (insn
));
1626 excess_cost_change
= 0;
1627 calculate_reg_deaths (insn
, death
);
1628 pressure_info
= INSN_REG_PRESSURE (insn
);
1629 max_reg_pressure
= INSN_MAX_REG_PRESSURE (insn
);
1630 gcc_assert (pressure_info
!= NULL
&& max_reg_pressure
!= NULL
);
1631 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1633 cl
= ira_pressure_classes
[i
];
1634 gcc_assert (curr_reg_pressure
[cl
] >= 0);
1635 change
= (int) pressure_info
[i
].set_increase
- death
[cl
];
1636 before
= MAX (0, max_reg_pressure
[i
] - ira_class_hard_regs_num
[cl
]);
1637 after
= MAX (0, max_reg_pressure
[i
] + change
1638 - ira_class_hard_regs_num
[cl
]);
1639 hard_regno
= ira_class_hard_regs
[cl
][0];
1640 gcc_assert (hard_regno
>= 0);
1641 mode
= reg_raw_mode
[hard_regno
];
1642 excess_cost_change
+= ((after
- before
)
1643 * (ira_memory_move_cost
[mode
][cl
][0]
1644 + ira_memory_move_cost
[mode
][cl
][1]));
1646 INSN_REG_PRESSURE_EXCESS_COST_CHANGE (insn
) = excess_cost_change
;
1649 /* This is the first page of code related to SCHED_PRESSURE_MODEL.
1650 It tries to make the scheduler take register pressure into account
1651 without introducing too many unnecessary stalls. It hooks into the
1652 main scheduling algorithm at several points:
1654 - Before scheduling starts, model_start_schedule constructs a
1655 "model schedule" for the current block. This model schedule is
1656 chosen solely to keep register pressure down. It does not take the
1657 target's pipeline or the original instruction order into account,
1658 except as a tie-breaker. It also doesn't work to a particular
1661 This model schedule gives us an idea of what pressure can be
1662 achieved for the block and gives us an example of a schedule that
1663 keeps to that pressure. It also makes the final schedule less
1664 dependent on the original instruction order. This is important
1665 because the original order can either be "wide" (many values live
1666 at once, such as in user-scheduled code) or "narrow" (few values
1667 live at once, such as after loop unrolling, where several
1668 iterations are executed sequentially).
1670 We do not apply this model schedule to the rtx stream. We simply
1671 record it in model_schedule. We also compute the maximum pressure,
1672 MP, that was seen during this schedule.
1674 - Instructions are added to the ready queue even if they require
1675 a stall. The length of the stall is instead computed as:
1677 MAX (INSN_TICK (INSN) - clock_var, 0)
1679 (= insn_delay). This allows rank_for_schedule to choose between
1680 introducing a deliberate stall or increasing pressure.
1682 - Before sorting the ready queue, model_set_excess_costs assigns
1683 a pressure-based cost to each ready instruction in the queue.
1684 This is the instruction's INSN_REG_PRESSURE_EXCESS_COST_CHANGE
1685 (ECC for short) and is effectively measured in cycles.
1687 - rank_for_schedule ranks instructions based on:
1689 ECC (insn) + insn_delay (insn)
1695 So, for example, an instruction X1 with an ECC of 1 that can issue
1696 now will win over an instruction X0 with an ECC of zero that would
1697 introduce a stall of one cycle. However, an instruction X2 with an
1698 ECC of 2 that can issue now will lose to both X0 and X1.
1700 - When an instruction is scheduled, model_recompute updates the model
1701 schedule with the new pressures (some of which might now exceed the
1702 original maximum pressure MP). model_update_limit_points then searches
1703 for the new point of maximum pressure, if not already known. */
1705 /* Used to separate high-verbosity debug information for SCHED_PRESSURE_MODEL
1706 from surrounding debug information. */
1708 ";;\t\t+------------------------------------------------------\n"
1710 /* Information about the pressure on a particular register class at a
1711 particular point of the model schedule. */
1712 struct model_pressure_data
{
1713 /* The pressure at this point of the model schedule, or -1 if the
1714 point is associated with an instruction that has already been
1718 /* The maximum pressure during or after this point of the model schedule. */
1722 /* Per-instruction information that is used while building the model
1723 schedule. Here, "schedule" refers to the model schedule rather
1724 than the main schedule. */
1725 struct model_insn_info
{
1726 /* The instruction itself. */
1729 /* If this instruction is in model_worklist, these fields link to the
1730 previous (higher-priority) and next (lower-priority) instructions
1732 struct model_insn_info
*prev
;
1733 struct model_insn_info
*next
;
1735 /* While constructing the schedule, QUEUE_INDEX describes whether an
1736 instruction has already been added to the schedule (QUEUE_SCHEDULED),
1737 is in model_worklist (QUEUE_READY), or neither (QUEUE_NOWHERE).
1738 old_queue records the value that QUEUE_INDEX had before scheduling
1739 started, so that we can restore it once the schedule is complete. */
1742 /* The relative importance of an unscheduled instruction. Higher
1743 values indicate greater importance. */
1744 unsigned int model_priority
;
1746 /* The length of the longest path of satisfied true dependencies
1747 that leads to this instruction. */
1750 /* The length of the longest path of dependencies of any kind
1751 that leads from this instruction. */
1754 /* The number of predecessor nodes that must still be scheduled. */
1755 int unscheduled_preds
;
1758 /* Information about the pressure limit for a particular register class.
1759 This structure is used when applying a model schedule to the main
1761 struct model_pressure_limit
{
1762 /* The maximum register pressure seen in the original model schedule. */
1765 /* The maximum register pressure seen in the current model schedule
1766 (which excludes instructions that have already been scheduled). */
1769 /* The point of the current model schedule at which PRESSURE is first
1770 reached. It is set to -1 if the value needs to be recomputed. */
1774 /* Describes a particular way of measuring register pressure. */
1775 struct model_pressure_group
{
1776 /* Index PCI describes the maximum pressure on ira_pressure_classes[PCI]. */
1777 struct model_pressure_limit limits
[N_REG_CLASSES
];
1779 /* Index (POINT * ira_num_pressure_classes + PCI) describes the pressure
1780 on register class ira_pressure_classes[PCI] at point POINT of the
1781 current model schedule. A POINT of model_num_insns describes the
1782 pressure at the end of the schedule. */
1783 struct model_pressure_data
*model
;
1786 /* Index POINT gives the instruction at point POINT of the model schedule.
1787 This array doesn't change during main scheduling. */
1788 static VEC (rtx
, heap
) *model_schedule
;
1790 /* The list of instructions in the model worklist, sorted in order of
1791 decreasing priority. */
1792 static struct model_insn_info
*model_worklist
;
1794 /* Index I describes the instruction with INSN_LUID I. */
1795 static struct model_insn_info
*model_insns
;
1797 /* The number of instructions in the model schedule. */
1798 static int model_num_insns
;
1800 /* The index of the first instruction in model_schedule that hasn't yet been
1801 added to the main schedule, or model_num_insns if all of them have. */
1802 static int model_curr_point
;
1804 /* Describes the pressure before each instruction in the model schedule. */
1805 static struct model_pressure_group model_before_pressure
;
1807 /* The first unused model_priority value (as used in model_insn_info). */
1808 static unsigned int model_next_priority
;
1811 /* The model_pressure_data for ira_pressure_classes[PCI] in GROUP
1812 at point POINT of the model schedule. */
1813 #define MODEL_PRESSURE_DATA(GROUP, POINT, PCI) \
1814 (&(GROUP)->model[(POINT) * ira_pressure_classes_num + (PCI)])
1816 /* The maximum pressure on ira_pressure_classes[PCI] in GROUP at or
1817 after point POINT of the model schedule. */
1818 #define MODEL_MAX_PRESSURE(GROUP, POINT, PCI) \
1819 (MODEL_PRESSURE_DATA (GROUP, POINT, PCI)->max_pressure)
1821 /* The pressure on ira_pressure_classes[PCI] in GROUP at point POINT
1822 of the model schedule. */
1823 #define MODEL_REF_PRESSURE(GROUP, POINT, PCI) \
1824 (MODEL_PRESSURE_DATA (GROUP, POINT, PCI)->ref_pressure)
1826 /* Information about INSN that is used when creating the model schedule. */
1827 #define MODEL_INSN_INFO(INSN) \
1828 (&model_insns[INSN_LUID (INSN)])
1830 /* The instruction at point POINT of the model schedule. */
1831 #define MODEL_INSN(POINT) \
1832 (VEC_index (rtx, model_schedule, POINT))
1835 /* Return INSN's index in the model schedule, or model_num_insns if it
1836 doesn't belong to that schedule. */
1839 model_index (rtx insn
)
1841 if (INSN_MODEL_INDEX (insn
) == 0)
1842 return model_num_insns
;
1843 return INSN_MODEL_INDEX (insn
) - 1;
1846 /* Make sure that GROUP->limits is up-to-date for the current point
1847 of the model schedule. */
1850 model_update_limit_points_in_group (struct model_pressure_group
*group
)
1852 int pci
, max_pressure
, point
;
1854 for (pci
= 0; pci
< ira_pressure_classes_num
; pci
++)
1856 /* We may have passed the final point at which the pressure in
1857 group->limits[pci].pressure was reached. Update the limit if so. */
1858 max_pressure
= MODEL_MAX_PRESSURE (group
, model_curr_point
, pci
);
1859 group
->limits
[pci
].pressure
= max_pressure
;
1861 /* Find the point at which MAX_PRESSURE is first reached. We need
1862 to search in three cases:
1864 - We've already moved past the previous pressure point.
1865 In this case we search forward from model_curr_point.
1867 - We scheduled the previous point of maximum pressure ahead of
1868 its position in the model schedule, but doing so didn't bring
1869 the pressure point earlier. In this case we search forward
1870 from that previous pressure point.
1872 - Scheduling an instruction early caused the maximum pressure
1873 to decrease. In this case we will have set the pressure
1874 point to -1, and we search forward from model_curr_point. */
1875 point
= MAX (group
->limits
[pci
].point
, model_curr_point
);
1876 while (point
< model_num_insns
1877 && MODEL_REF_PRESSURE (group
, point
, pci
) < max_pressure
)
1879 group
->limits
[pci
].point
= point
;
1881 gcc_assert (MODEL_REF_PRESSURE (group
, point
, pci
) == max_pressure
);
1882 gcc_assert (MODEL_MAX_PRESSURE (group
, point
, pci
) == max_pressure
);
1886 /* Make sure that all register-pressure limits are up-to-date for the
1887 current position in the model schedule. */
1890 model_update_limit_points (void)
1892 model_update_limit_points_in_group (&model_before_pressure
);
1895 /* Return the model_index of the last unscheduled use in chain USE
1896 outside of USE's instruction. Return -1 if there are no other uses,
1897 or model_num_insns if the register is live at the end of the block. */
1900 model_last_use_except (struct reg_use_data
*use
)
1902 struct reg_use_data
*next
;
1906 for (next
= use
->next_regno_use
; next
!= use
; next
= next
->next_regno_use
)
1907 if (NONDEBUG_INSN_P (next
->insn
)
1908 && QUEUE_INDEX (next
->insn
) != QUEUE_SCHEDULED
)
1910 index
= model_index (next
->insn
);
1911 if (index
== model_num_insns
)
1912 return model_num_insns
;
1919 /* An instruction with model_index POINT has just been scheduled, and it
1920 adds DELTA to the pressure on ira_pressure_classes[PCI] after POINT - 1.
1921 Update MODEL_REF_PRESSURE (GROUP, POINT, PCI) and
1922 MODEL_MAX_PRESSURE (GROUP, POINT, PCI) accordingly. */
1925 model_start_update_pressure (struct model_pressure_group
*group
,
1926 int point
, int pci
, int delta
)
1928 int next_max_pressure
;
1930 if (point
== model_num_insns
)
1932 /* The instruction wasn't part of the model schedule; it was moved
1933 from a different block. Update the pressure for the end of
1934 the model schedule. */
1935 MODEL_REF_PRESSURE (group
, point
, pci
) += delta
;
1936 MODEL_MAX_PRESSURE (group
, point
, pci
) += delta
;
1940 /* Record that this instruction has been scheduled. Nothing now
1941 changes between POINT and POINT + 1, so get the maximum pressure
1942 from the latter. If the maximum pressure decreases, the new
1943 pressure point may be before POINT. */
1944 MODEL_REF_PRESSURE (group
, point
, pci
) = -1;
1945 next_max_pressure
= MODEL_MAX_PRESSURE (group
, point
+ 1, pci
);
1946 if (MODEL_MAX_PRESSURE (group
, point
, pci
) > next_max_pressure
)
1948 MODEL_MAX_PRESSURE (group
, point
, pci
) = next_max_pressure
;
1949 if (group
->limits
[pci
].point
== point
)
1950 group
->limits
[pci
].point
= -1;
1955 /* Record that scheduling a later instruction has changed the pressure
1956 at point POINT of the model schedule by DELTA (which might be 0).
1957 Update GROUP accordingly. Return nonzero if these changes might
1958 trigger changes to previous points as well. */
1961 model_update_pressure (struct model_pressure_group
*group
,
1962 int point
, int pci
, int delta
)
1964 int ref_pressure
, max_pressure
, next_max_pressure
;
1966 /* If POINT hasn't yet been scheduled, update its pressure. */
1967 ref_pressure
= MODEL_REF_PRESSURE (group
, point
, pci
);
1968 if (ref_pressure
>= 0 && delta
!= 0)
1970 ref_pressure
+= delta
;
1971 MODEL_REF_PRESSURE (group
, point
, pci
) = ref_pressure
;
1973 /* Check whether the maximum pressure in the overall schedule
1974 has increased. (This means that the MODEL_MAX_PRESSURE of
1975 every point <= POINT will need to increae too; see below.) */
1976 if (group
->limits
[pci
].pressure
< ref_pressure
)
1977 group
->limits
[pci
].pressure
= ref_pressure
;
1979 /* If we are at maximum pressure, and the maximum pressure
1980 point was previously unknown or later than POINT,
1981 bring it forward. */
1982 if (group
->limits
[pci
].pressure
== ref_pressure
1983 && !IN_RANGE (group
->limits
[pci
].point
, 0, point
))
1984 group
->limits
[pci
].point
= point
;
1986 /* If POINT used to be the point of maximum pressure, but isn't
1987 any longer, we need to recalculate it using a forward walk. */
1988 if (group
->limits
[pci
].pressure
> ref_pressure
1989 && group
->limits
[pci
].point
== point
)
1990 group
->limits
[pci
].point
= -1;
1993 /* Update the maximum pressure at POINT. Changes here might also
1994 affect the maximum pressure at POINT - 1. */
1995 next_max_pressure
= MODEL_MAX_PRESSURE (group
, point
+ 1, pci
);
1996 max_pressure
= MAX (ref_pressure
, next_max_pressure
);
1997 if (MODEL_MAX_PRESSURE (group
, point
, pci
) != max_pressure
)
1999 MODEL_MAX_PRESSURE (group
, point
, pci
) = max_pressure
;
2005 /* INSN has just been scheduled. Update the model schedule accordingly. */
2008 model_recompute (rtx insn
)
2013 } uses
[FIRST_PSEUDO_REGISTER
+ MAX_RECOG_OPERANDS
];
2014 struct reg_use_data
*use
;
2015 struct reg_pressure_data
*reg_pressure
;
2016 int delta
[N_REG_CLASSES
];
2017 int pci
, point
, mix
, new_last
, cl
, ref_pressure
, queue
;
2018 unsigned int i
, num_uses
, num_pending_births
;
2021 /* The destinations of INSN were previously live from POINT onwards, but are
2022 now live from model_curr_point onwards. Set up DELTA accordingly. */
2023 point
= model_index (insn
);
2024 reg_pressure
= INSN_REG_PRESSURE (insn
);
2025 for (pci
= 0; pci
< ira_pressure_classes_num
; pci
++)
2027 cl
= ira_pressure_classes
[pci
];
2028 delta
[cl
] = reg_pressure
[pci
].set_increase
;
2031 /* Record which registers previously died at POINT, but which now die
2032 before POINT. Adjust DELTA so that it represents the effect of
2033 this change after POINT - 1. Set NUM_PENDING_BIRTHS to the number of
2034 registers that will be born in the range [model_curr_point, POINT). */
2036 num_pending_births
= 0;
2037 for (use
= INSN_REG_USE_LIST (insn
); use
!= NULL
; use
= use
->next_insn_use
)
2039 new_last
= model_last_use_except (use
);
2040 if (new_last
< point
)
2042 gcc_assert (num_uses
< ARRAY_SIZE (uses
));
2043 uses
[num_uses
].last_use
= new_last
;
2044 uses
[num_uses
].regno
= use
->regno
;
2045 /* This register is no longer live after POINT - 1. */
2046 mark_regno_birth_or_death (NULL
, delta
, use
->regno
, false);
2049 num_pending_births
++;
2053 /* Update the MODEL_REF_PRESSURE and MODEL_MAX_PRESSURE for POINT.
2054 Also set each group pressure limit for POINT. */
2055 for (pci
= 0; pci
< ira_pressure_classes_num
; pci
++)
2057 cl
= ira_pressure_classes
[pci
];
2058 model_start_update_pressure (&model_before_pressure
,
2059 point
, pci
, delta
[cl
]);
2062 /* Walk the model schedule backwards, starting immediately before POINT. */
2064 if (point
!= model_curr_point
)
2068 insn
= MODEL_INSN (point
);
2069 queue
= QUEUE_INDEX (insn
);
2071 if (queue
!= QUEUE_SCHEDULED
)
2073 /* DELTA describes the effect of the move on the register pressure
2074 after POINT. Make it describe the effect on the pressure
2077 while (i
< num_uses
)
2079 if (uses
[i
].last_use
== point
)
2081 /* This register is now live again. */
2082 mark_regno_birth_or_death (NULL
, delta
,
2083 uses
[i
].regno
, true);
2085 /* Remove this use from the array. */
2086 uses
[i
] = uses
[num_uses
- 1];
2088 num_pending_births
--;
2094 if (sched_verbose
>= 5)
2100 fprintf (sched_dump
, MODEL_BAR
);
2101 fprintf (sched_dump
, ";;\t\t| New pressure for model"
2103 fprintf (sched_dump
, MODEL_BAR
);
2107 print_pattern (buf
, PATTERN (insn
), 0);
2108 fprintf (sched_dump
, ";;\t\t| %3d %4d %-30s ",
2109 point
, INSN_UID (insn
), buf
);
2110 for (pci
= 0; pci
< ira_pressure_classes_num
; pci
++)
2112 cl
= ira_pressure_classes
[pci
];
2113 ref_pressure
= MODEL_REF_PRESSURE (&model_before_pressure
,
2115 fprintf (sched_dump
, " %s:[%d->%d]",
2116 reg_class_names
[ira_pressure_classes
[pci
]],
2117 ref_pressure
, ref_pressure
+ delta
[cl
]);
2119 fprintf (sched_dump
, "\n");
2123 /* Adjust the pressure at POINT. Set MIX to nonzero if POINT - 1
2124 might have changed as well. */
2125 mix
= num_pending_births
;
2126 for (pci
= 0; pci
< ira_pressure_classes_num
; pci
++)
2128 cl
= ira_pressure_classes
[pci
];
2130 mix
|= model_update_pressure (&model_before_pressure
,
2131 point
, pci
, delta
[cl
]);
2134 while (mix
&& point
> model_curr_point
);
2137 fprintf (sched_dump
, MODEL_BAR
);
2140 /* model_spill_cost (CL, P, P') returns the cost of increasing the
2141 pressure on CL from P to P'. We use this to calculate a "base ECC",
2142 baseECC (CL, X), for each pressure class CL and each instruction X.
2143 Supposing X changes the pressure on CL from P to P', and that the
2144 maximum pressure on CL in the current model schedule is MP', then:
2146 * if X occurs before or at the next point of maximum pressure in
2147 the model schedule and P' > MP', then:
2149 baseECC (CL, X) = model_spill_cost (CL, MP, P')
2151 The idea is that the pressure after scheduling a fixed set of
2152 instructions -- in this case, the set up to and including the
2153 next maximum pressure point -- is going to be the same regardless
2154 of the order; we simply want to keep the intermediate pressure
2155 under control. Thus X has a cost of zero unless scheduling it
2156 now would exceed MP'.
2158 If all increases in the set are by the same amount, no zero-cost
2159 instruction will ever cause the pressure to exceed MP'. However,
2160 if X is instead moved past an instruction X' with pressure in the
2161 range (MP' - (P' - P), MP'), the pressure at X' will increase
2162 beyond MP'. Since baseECC is very much a heuristic anyway,
2163 it doesn't seem worth the overhead of tracking cases like these.
2165 The cost of exceeding MP' is always based on the original maximum
2166 pressure MP. This is so that going 2 registers over the original
2167 limit has the same cost regardless of whether it comes from two
2168 separate +1 deltas or from a single +2 delta.
2170 * if X occurs after the next point of maximum pressure in the model
2171 schedule and P' > P, then:
2173 baseECC (CL, X) = model_spill_cost (CL, MP, MP' + (P' - P))
2175 That is, if we move X forward across a point of maximum pressure,
2176 and if X increases the pressure by P' - P, then we conservatively
2177 assume that scheduling X next would increase the maximum pressure
2178 by P' - P. Again, the cost of doing this is based on the original
2179 maximum pressure MP, for the same reason as above.
2181 * if P' < P, P > MP, and X occurs at or after the next point of
2182 maximum pressure, then:
2184 baseECC (CL, X) = -model_spill_cost (CL, MAX (MP, P'), P)
2186 That is, if we have already exceeded the original maximum pressure MP,
2187 and if X might reduce the maximum pressure again -- or at least push
2188 it further back, and thus allow more scheduling freedom -- it is given
2189 a negative cost to reflect the improvement.
2195 In this case, X is not expected to affect the maximum pressure MP',
2196 so it has zero cost.
2198 We then create a combined value baseECC (X) that is the sum of
2199 baseECC (CL, X) for each pressure class CL.
2201 baseECC (X) could itself be used as the ECC value described above.
2202 However, this is often too conservative, in the sense that it
2203 tends to make high-priority instructions that increase pressure
2204 wait too long in cases where introducing a spill would be better.
2205 For this reason the final ECC is a priority-adjusted form of
2206 baseECC (X). Specifically, we calculate:
2208 P (X) = INSN_PRIORITY (X) - insn_delay (X) - baseECC (X)
2209 baseP = MAX { P (X) | baseECC (X) <= 0 }
2213 ECC (X) = MAX (MIN (baseP - P (X), baseECC (X)), 0)
2215 Thus an instruction's effect on pressure is ignored if it has a high
2216 enough priority relative to the ones that don't increase pressure.
2217 Negative values of baseECC (X) do not increase the priority of X
2218 itself, but they do make it harder for other instructions to
2219 increase the pressure further.
2221 This pressure cost is deliberately timid. The intention has been
2222 to choose a heuristic that rarely interferes with the normal list
2223 scheduler in cases where that scheduler would produce good code.
2224 We simply want to curb some of its worst excesses. */
2226 /* Return the cost of increasing the pressure in class CL from FROM to TO.
2228 Here we use the very simplistic cost model that every register above
2229 ira_class_hard_regs_num[CL] has a spill cost of 1. We could use other
2230 measures instead, such as one based on MEMORY_MOVE_COST. However:
2232 (1) In order for an instruction to be scheduled, the higher cost
2233 would need to be justified in a single saving of that many stalls.
2234 This is overly pessimistic, because the benefit of spilling is
2235 often to avoid a sequence of several short stalls rather than
2238 (2) The cost is still arbitrary. Because we are not allocating
2239 registers during scheduling, we have no way of knowing for
2240 sure how many memory accesses will be required by each spill,
2241 where the spills will be placed within the block, or even
2242 which block(s) will contain the spills.
2244 So a higher cost than 1 is often too conservative in practice,
2245 forcing blocks to contain unnecessary stalls instead of spill code.
2246 The simple cost below seems to be the best compromise. It reduces
2247 the interference with the normal list scheduler, which helps make
2248 it more suitable for a default-on option. */
2251 model_spill_cost (int cl
, int from
, int to
)
2253 from
= MAX (from
, ira_class_hard_regs_num
[cl
]);
2254 return MAX (to
, from
) - from
;
2257 /* Return baseECC (ira_pressure_classes[PCI], POINT), given that
2258 P = curr_reg_pressure[ira_pressure_classes[PCI]] and that
2262 model_excess_group_cost (struct model_pressure_group
*group
,
2263 int point
, int pci
, int delta
)
2267 cl
= ira_pressure_classes
[pci
];
2268 if (delta
< 0 && point
>= group
->limits
[pci
].point
)
2270 pressure
= MAX (group
->limits
[pci
].orig_pressure
,
2271 curr_reg_pressure
[cl
] + delta
);
2272 return -model_spill_cost (cl
, pressure
, curr_reg_pressure
[cl
]);
2277 if (point
> group
->limits
[pci
].point
)
2278 pressure
= group
->limits
[pci
].pressure
+ delta
;
2280 pressure
= curr_reg_pressure
[cl
] + delta
;
2282 if (pressure
> group
->limits
[pci
].pressure
)
2283 return model_spill_cost (cl
, group
->limits
[pci
].orig_pressure
,
2290 /* Return baseECC (MODEL_INSN (INSN)). Dump the costs to sched_dump
2294 model_excess_cost (rtx insn
, bool print_p
)
2296 int point
, pci
, cl
, cost
, this_cost
, delta
;
2297 struct reg_pressure_data
*insn_reg_pressure
;
2298 int insn_death
[N_REG_CLASSES
];
2300 calculate_reg_deaths (insn
, insn_death
);
2301 point
= model_index (insn
);
2302 insn_reg_pressure
= INSN_REG_PRESSURE (insn
);
2306 fprintf (sched_dump
, ";;\t\t| %3d %4d | %4d %+3d |", point
,
2307 INSN_UID (insn
), INSN_PRIORITY (insn
), insn_delay (insn
));
2309 /* Sum up the individual costs for each register class. */
2310 for (pci
= 0; pci
< ira_pressure_classes_num
; pci
++)
2312 cl
= ira_pressure_classes
[pci
];
2313 delta
= insn_reg_pressure
[pci
].set_increase
- insn_death
[cl
];
2314 this_cost
= model_excess_group_cost (&model_before_pressure
,
2318 fprintf (sched_dump
, " %s:[%d base cost %d]",
2319 reg_class_names
[cl
], delta
, this_cost
);
2323 fprintf (sched_dump
, "\n");
2328 /* Dump the next points of maximum pressure for GROUP. */
2331 model_dump_pressure_points (struct model_pressure_group
*group
)
2335 fprintf (sched_dump
, ";;\t\t| pressure points");
2336 for (pci
= 0; pci
< ira_pressure_classes_num
; pci
++)
2338 cl
= ira_pressure_classes
[pci
];
2339 fprintf (sched_dump
, " %s:[%d->%d at ", reg_class_names
[cl
],
2340 curr_reg_pressure
[cl
], group
->limits
[pci
].pressure
);
2341 if (group
->limits
[pci
].point
< model_num_insns
)
2342 fprintf (sched_dump
, "%d:%d]", group
->limits
[pci
].point
,
2343 INSN_UID (MODEL_INSN (group
->limits
[pci
].point
)));
2345 fprintf (sched_dump
, "end]");
2347 fprintf (sched_dump
, "\n");
2350 /* Set INSN_REG_PRESSURE_EXCESS_COST_CHANGE for INSNS[0...COUNT-1]. */
2353 model_set_excess_costs (rtx
*insns
, int count
)
2355 int i
, cost
, priority_base
, priority
;
2358 /* Record the baseECC value for each instruction in the model schedule,
2359 except that negative costs are converted to zero ones now rather thatn
2360 later. Do not assign a cost to debug instructions, since they must
2361 not change code-generation decisions. Experiments suggest we also
2362 get better results by not assigning a cost to instructions from
2365 Set PRIORITY_BASE to baseP in the block comment above. This is the
2366 maximum priority of the "cheap" instructions, which should always
2367 include the next model instruction. */
2370 for (i
= 0; i
< count
; i
++)
2371 if (INSN_MODEL_INDEX (insns
[i
]))
2373 if (sched_verbose
>= 6 && !print_p
)
2375 fprintf (sched_dump
, MODEL_BAR
);
2376 fprintf (sched_dump
, ";;\t\t| Pressure costs for ready queue\n");
2377 model_dump_pressure_points (&model_before_pressure
);
2378 fprintf (sched_dump
, MODEL_BAR
);
2381 cost
= model_excess_cost (insns
[i
], print_p
);
2384 priority
= INSN_PRIORITY (insns
[i
]) - insn_delay (insns
[i
]) - cost
;
2385 priority_base
= MAX (priority_base
, priority
);
2388 INSN_REG_PRESSURE_EXCESS_COST_CHANGE (insns
[i
]) = cost
;
2391 fprintf (sched_dump
, MODEL_BAR
);
2393 /* Use MAX (baseECC, 0) and baseP to calculcate ECC for each
2395 for (i
= 0; i
< count
; i
++)
2397 cost
= INSN_REG_PRESSURE_EXCESS_COST_CHANGE (insns
[i
]);
2398 priority
= INSN_PRIORITY (insns
[i
]) - insn_delay (insns
[i
]);
2399 if (cost
> 0 && priority
> priority_base
)
2401 cost
+= priority_base
- priority
;
2402 INSN_REG_PRESSURE_EXCESS_COST_CHANGE (insns
[i
]) = MAX (cost
, 0);
2407 /* Returns a positive value if x is preferred; returns a negative value if
2408 y is preferred. Should never return 0, since that will make the sort
2412 rank_for_schedule (const void *x
, const void *y
)
2414 rtx tmp
= *(const rtx
*) y
;
2415 rtx tmp2
= *(const rtx
*) x
;
2416 int tmp_class
, tmp2_class
;
2417 int val
, priority_val
, info_val
;
2419 if (MAY_HAVE_DEBUG_INSNS
)
2421 /* Schedule debug insns as early as possible. */
2422 if (DEBUG_INSN_P (tmp
) && !DEBUG_INSN_P (tmp2
))
2424 else if (!DEBUG_INSN_P (tmp
) && DEBUG_INSN_P (tmp2
))
2426 else if (DEBUG_INSN_P (tmp
) && DEBUG_INSN_P (tmp2
))
2427 return INSN_LUID (tmp
) - INSN_LUID (tmp2
);
2430 /* The insn in a schedule group should be issued the first. */
2431 if (flag_sched_group_heuristic
&&
2432 SCHED_GROUP_P (tmp
) != SCHED_GROUP_P (tmp2
))
2433 return SCHED_GROUP_P (tmp2
) ? 1 : -1;
2435 /* Make sure that priority of TMP and TMP2 are initialized. */
2436 gcc_assert (INSN_PRIORITY_KNOWN (tmp
) && INSN_PRIORITY_KNOWN (tmp2
));
2438 if (sched_pressure
!= SCHED_PRESSURE_NONE
)
2442 /* Prefer insn whose scheduling results in the smallest register
2444 if ((diff
= (INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp
)
2446 - INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp2
)
2447 - insn_delay (tmp2
))))
2451 if (sched_pressure
!= SCHED_PRESSURE_NONE
2452 && (INSN_TICK (tmp2
) > clock_var
|| INSN_TICK (tmp
) > clock_var
))
2454 if (INSN_TICK (tmp
) <= clock_var
)
2456 else if (INSN_TICK (tmp2
) <= clock_var
)
2459 return INSN_TICK (tmp
) - INSN_TICK (tmp2
);
2462 /* If we are doing backtracking in this schedule, prefer insns that
2463 have forward dependencies with negative cost against an insn that
2464 was already scheduled. */
2465 if (current_sched_info
->flags
& DO_BACKTRACKING
)
2467 priority_val
= FEEDS_BACKTRACK_INSN (tmp2
) - FEEDS_BACKTRACK_INSN (tmp
);
2469 return priority_val
;
2472 /* Prefer insn with higher priority. */
2473 priority_val
= INSN_PRIORITY (tmp2
) - INSN_PRIORITY (tmp
);
2475 if (flag_sched_critical_path_heuristic
&& priority_val
)
2476 return priority_val
;
2478 /* Prefer speculative insn with greater dependencies weakness. */
2479 if (flag_sched_spec_insn_heuristic
&& spec_info
)
2485 ds1
= TODO_SPEC (tmp
) & SPECULATIVE
;
2487 dw1
= ds_weak (ds1
);
2491 ds2
= TODO_SPEC (tmp2
) & SPECULATIVE
;
2493 dw2
= ds_weak (ds2
);
2498 if (dw
> (NO_DEP_WEAK
/ 8) || dw
< -(NO_DEP_WEAK
/ 8))
2502 info_val
= (*current_sched_info
->rank
) (tmp
, tmp2
);
2503 if(flag_sched_rank_heuristic
&& info_val
)
2506 /* Compare insns based on their relation to the last scheduled
2508 if (flag_sched_last_insn_heuristic
&& last_nondebug_scheduled_insn
)
2512 rtx last
= last_nondebug_scheduled_insn
;
2514 /* Classify the instructions into three classes:
2515 1) Data dependent on last schedule insn.
2516 2) Anti/Output dependent on last scheduled insn.
2517 3) Independent of last scheduled insn, or has latency of one.
2518 Choose the insn from the highest numbered class if different. */
2519 dep1
= sd_find_dep_between (last
, tmp
, true);
2521 if (dep1
== NULL
|| dep_cost (dep1
) == 1)
2523 else if (/* Data dependence. */
2524 DEP_TYPE (dep1
) == REG_DEP_TRUE
)
2529 dep2
= sd_find_dep_between (last
, tmp2
, true);
2531 if (dep2
== NULL
|| dep_cost (dep2
) == 1)
2533 else if (/* Data dependence. */
2534 DEP_TYPE (dep2
) == REG_DEP_TRUE
)
2539 if ((val
= tmp2_class
- tmp_class
))
2543 /* Prefer instructions that occur earlier in the model schedule. */
2544 if (sched_pressure
== SCHED_PRESSURE_MODEL
)
2548 diff
= model_index (tmp
) - model_index (tmp2
);
2553 /* Prefer the insn which has more later insns that depend on it.
2554 This gives the scheduler more freedom when scheduling later
2555 instructions at the expense of added register pressure. */
2557 val
= (dep_list_size (tmp2
, SD_LIST_FORW
)
2558 - dep_list_size (tmp
, SD_LIST_FORW
));
2560 if (flag_sched_dep_count_heuristic
&& val
!= 0)
2563 /* If insns are equally good, sort by INSN_LUID (original insn order),
2564 so that we make the sort stable. This minimizes instruction movement,
2565 thus minimizing sched's effect on debugging and cross-jumping. */
2566 return INSN_LUID (tmp
) - INSN_LUID (tmp2
);
2569 /* Resort the array A in which only element at index N may be out of order. */
2571 HAIFA_INLINE
static void
2572 swap_sort (rtx
*a
, int n
)
2574 rtx insn
= a
[n
- 1];
2577 while (i
>= 0 && rank_for_schedule (a
+ i
, &insn
) >= 0)
2585 /* Add INSN to the insn queue so that it can be executed at least
2586 N_CYCLES after the currently executing insn. Preserve insns
2587 chain for debugging purposes. REASON will be printed in debugging
2590 HAIFA_INLINE
static void
2591 queue_insn (rtx insn
, int n_cycles
, const char *reason
)
2593 int next_q
= NEXT_Q_AFTER (q_ptr
, n_cycles
);
2594 rtx link
= alloc_INSN_LIST (insn
, insn_queue
[next_q
]);
2597 gcc_assert (n_cycles
<= max_insn_queue_index
);
2598 gcc_assert (!DEBUG_INSN_P (insn
));
2600 insn_queue
[next_q
] = link
;
2603 if (sched_verbose
>= 2)
2605 fprintf (sched_dump
, ";;\t\tReady-->Q: insn %s: ",
2606 (*current_sched_info
->print_insn
) (insn
, 0));
2608 fprintf (sched_dump
, "queued for %d cycles (%s).\n", n_cycles
, reason
);
2611 QUEUE_INDEX (insn
) = next_q
;
2613 if (current_sched_info
->flags
& DO_BACKTRACKING
)
2615 new_tick
= clock_var
+ n_cycles
;
2616 if (INSN_TICK (insn
) == INVALID_TICK
|| INSN_TICK (insn
) < new_tick
)
2617 INSN_TICK (insn
) = new_tick
;
2619 if (INSN_EXACT_TICK (insn
) != INVALID_TICK
2620 && INSN_EXACT_TICK (insn
) < clock_var
+ n_cycles
)
2622 must_backtrack
= true;
2623 if (sched_verbose
>= 2)
2624 fprintf (sched_dump
, ";;\t\tcausing a backtrack.\n");
2629 /* Remove INSN from queue. */
2631 queue_remove (rtx insn
)
2633 gcc_assert (QUEUE_INDEX (insn
) >= 0);
2634 remove_free_INSN_LIST_elem (insn
, &insn_queue
[QUEUE_INDEX (insn
)]);
2636 QUEUE_INDEX (insn
) = QUEUE_NOWHERE
;
2639 /* Return a pointer to the bottom of the ready list, i.e. the insn
2640 with the lowest priority. */
2643 ready_lastpos (struct ready_list
*ready
)
2645 gcc_assert (ready
->n_ready
>= 1);
2646 return ready
->vec
+ ready
->first
- ready
->n_ready
+ 1;
2649 /* Add an element INSN to the ready list so that it ends up with the
2650 lowest/highest priority depending on FIRST_P. */
2652 HAIFA_INLINE
static void
2653 ready_add (struct ready_list
*ready
, rtx insn
, bool first_p
)
2657 if (ready
->first
== ready
->n_ready
)
2659 memmove (ready
->vec
+ ready
->veclen
- ready
->n_ready
,
2660 ready_lastpos (ready
),
2661 ready
->n_ready
* sizeof (rtx
));
2662 ready
->first
= ready
->veclen
- 1;
2664 ready
->vec
[ready
->first
- ready
->n_ready
] = insn
;
2668 if (ready
->first
== ready
->veclen
- 1)
2671 /* ready_lastpos() fails when called with (ready->n_ready == 0). */
2672 memmove (ready
->vec
+ ready
->veclen
- ready
->n_ready
- 1,
2673 ready_lastpos (ready
),
2674 ready
->n_ready
* sizeof (rtx
));
2675 ready
->first
= ready
->veclen
- 2;
2677 ready
->vec
[++(ready
->first
)] = insn
;
2681 if (DEBUG_INSN_P (insn
))
2684 gcc_assert (QUEUE_INDEX (insn
) != QUEUE_READY
);
2685 QUEUE_INDEX (insn
) = QUEUE_READY
;
2687 if (INSN_EXACT_TICK (insn
) != INVALID_TICK
2688 && INSN_EXACT_TICK (insn
) < clock_var
)
2690 must_backtrack
= true;
2694 /* Remove the element with the highest priority from the ready list and
2697 HAIFA_INLINE
static rtx
2698 ready_remove_first (struct ready_list
*ready
)
2702 gcc_assert (ready
->n_ready
);
2703 t
= ready
->vec
[ready
->first
--];
2705 if (DEBUG_INSN_P (t
))
2707 /* If the queue becomes empty, reset it. */
2708 if (ready
->n_ready
== 0)
2709 ready
->first
= ready
->veclen
- 1;
2711 gcc_assert (QUEUE_INDEX (t
) == QUEUE_READY
);
2712 QUEUE_INDEX (t
) = QUEUE_NOWHERE
;
2717 /* The following code implements multi-pass scheduling for the first
2718 cycle. In other words, we will try to choose ready insn which
2719 permits to start maximum number of insns on the same cycle. */
2721 /* Return a pointer to the element INDEX from the ready. INDEX for
2722 insn with the highest priority is 0, and the lowest priority has
2726 ready_element (struct ready_list
*ready
, int index
)
2728 gcc_assert (ready
->n_ready
&& index
< ready
->n_ready
);
2730 return ready
->vec
[ready
->first
- index
];
2733 /* Remove the element INDEX from the ready list and return it. INDEX
2734 for insn with the highest priority is 0, and the lowest priority
2737 HAIFA_INLINE
static rtx
2738 ready_remove (struct ready_list
*ready
, int index
)
2744 return ready_remove_first (ready
);
2745 gcc_assert (ready
->n_ready
&& index
< ready
->n_ready
);
2746 t
= ready
->vec
[ready
->first
- index
];
2748 if (DEBUG_INSN_P (t
))
2750 for (i
= index
; i
< ready
->n_ready
; i
++)
2751 ready
->vec
[ready
->first
- i
] = ready
->vec
[ready
->first
- i
- 1];
2752 QUEUE_INDEX (t
) = QUEUE_NOWHERE
;
2756 /* Remove INSN from the ready list. */
2758 ready_remove_insn (rtx insn
)
2762 for (i
= 0; i
< readyp
->n_ready
; i
++)
2763 if (ready_element (readyp
, i
) == insn
)
2765 ready_remove (readyp
, i
);
2771 /* Sort the ready list READY by ascending priority, using the SCHED_SORT
2775 ready_sort (struct ready_list
*ready
)
2778 rtx
*first
= ready_lastpos (ready
);
2780 if (sched_pressure
== SCHED_PRESSURE_WEIGHTED
)
2782 for (i
= 0; i
< ready
->n_ready
; i
++)
2783 if (!DEBUG_INSN_P (first
[i
]))
2784 setup_insn_reg_pressure_info (first
[i
]);
2786 if (sched_pressure
== SCHED_PRESSURE_MODEL
2787 && model_curr_point
< model_num_insns
)
2788 model_set_excess_costs (first
, ready
->n_ready
);
2789 SCHED_SORT (first
, ready
->n_ready
);
2792 /* PREV is an insn that is ready to execute. Adjust its priority if that
2793 will help shorten or lengthen register lifetimes as appropriate. Also
2794 provide a hook for the target to tweak itself. */
2796 HAIFA_INLINE
static void
2797 adjust_priority (rtx prev
)
2799 /* ??? There used to be code here to try and estimate how an insn
2800 affected register lifetimes, but it did it by looking at REG_DEAD
2801 notes, which we removed in schedule_region. Nor did it try to
2802 take into account register pressure or anything useful like that.
2804 Revisit when we have a machine model to work with and not before. */
2806 if (targetm
.sched
.adjust_priority
)
2807 INSN_PRIORITY (prev
) =
2808 targetm
.sched
.adjust_priority (prev
, INSN_PRIORITY (prev
));
2811 /* Advance DFA state STATE on one cycle. */
2813 advance_state (state_t state
)
2815 if (targetm
.sched
.dfa_pre_advance_cycle
)
2816 targetm
.sched
.dfa_pre_advance_cycle ();
2818 if (targetm
.sched
.dfa_pre_cycle_insn
)
2819 state_transition (state
,
2820 targetm
.sched
.dfa_pre_cycle_insn ());
2822 state_transition (state
, NULL
);
2824 if (targetm
.sched
.dfa_post_cycle_insn
)
2825 state_transition (state
,
2826 targetm
.sched
.dfa_post_cycle_insn ());
2828 if (targetm
.sched
.dfa_post_advance_cycle
)
2829 targetm
.sched
.dfa_post_advance_cycle ();
2832 /* Advance time on one cycle. */
2833 HAIFA_INLINE
static void
2834 advance_one_cycle (void)
2836 advance_state (curr_state
);
2837 if (sched_verbose
>= 6)
2838 fprintf (sched_dump
, ";;\tAdvanced a state.\n");
2841 /* Update register pressure after scheduling INSN. */
2843 update_register_pressure (rtx insn
)
2845 struct reg_use_data
*use
;
2846 struct reg_set_data
*set
;
2848 gcc_checking_assert (!DEBUG_INSN_P (insn
));
2850 for (use
= INSN_REG_USE_LIST (insn
); use
!= NULL
; use
= use
->next_insn_use
)
2851 if (dying_use_p (use
))
2852 mark_regno_birth_or_death (curr_reg_live
, curr_reg_pressure
,
2854 for (set
= INSN_REG_SET_LIST (insn
); set
!= NULL
; set
= set
->next_insn_set
)
2855 mark_regno_birth_or_death (curr_reg_live
, curr_reg_pressure
,
2859 /* Set up or update (if UPDATE_P) max register pressure (see its
2860 meaning in sched-int.h::_haifa_insn_data) for all current BB insns
2861 after insn AFTER. */
2863 setup_insn_max_reg_pressure (rtx after
, bool update_p
)
2868 static int max_reg_pressure
[N_REG_CLASSES
];
2870 save_reg_pressure ();
2871 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
2872 max_reg_pressure
[ira_pressure_classes
[i
]]
2873 = curr_reg_pressure
[ira_pressure_classes
[i
]];
2874 for (insn
= NEXT_INSN (after
);
2875 insn
!= NULL_RTX
&& ! BARRIER_P (insn
)
2876 && BLOCK_FOR_INSN (insn
) == BLOCK_FOR_INSN (after
);
2877 insn
= NEXT_INSN (insn
))
2878 if (NONDEBUG_INSN_P (insn
))
2881 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
2883 p
= max_reg_pressure
[ira_pressure_classes
[i
]];
2884 if (INSN_MAX_REG_PRESSURE (insn
)[i
] != p
)
2887 INSN_MAX_REG_PRESSURE (insn
)[i
]
2888 = max_reg_pressure
[ira_pressure_classes
[i
]];
2891 if (update_p
&& eq_p
)
2893 update_register_pressure (insn
);
2894 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
2895 if (max_reg_pressure
[ira_pressure_classes
[i
]]
2896 < curr_reg_pressure
[ira_pressure_classes
[i
]])
2897 max_reg_pressure
[ira_pressure_classes
[i
]]
2898 = curr_reg_pressure
[ira_pressure_classes
[i
]];
2900 restore_reg_pressure ();
2903 /* Update the current register pressure after scheduling INSN. Update
2904 also max register pressure for unscheduled insns of the current
2907 update_reg_and_insn_max_reg_pressure (rtx insn
)
2910 int before
[N_REG_CLASSES
];
2912 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
2913 before
[i
] = curr_reg_pressure
[ira_pressure_classes
[i
]];
2914 update_register_pressure (insn
);
2915 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
2916 if (curr_reg_pressure
[ira_pressure_classes
[i
]] != before
[i
])
2918 if (i
< ira_pressure_classes_num
)
2919 setup_insn_max_reg_pressure (insn
, true);
2922 /* Set up register pressure at the beginning of basic block BB whose
2923 insns starting after insn AFTER. Set up also max register pressure
2924 for all insns of the basic block. */
2926 sched_setup_bb_reg_pressure_info (basic_block bb
, rtx after
)
2928 gcc_assert (sched_pressure
== SCHED_PRESSURE_WEIGHTED
);
2929 initiate_bb_reg_pressure_info (bb
);
2930 setup_insn_max_reg_pressure (after
, false);
2933 /* If doing predication while scheduling, verify whether INSN, which
2934 has just been scheduled, clobbers the conditions of any
2935 instructions that must be predicated in order to break their
2936 dependencies. If so, remove them from the queues so that they will
2937 only be scheduled once their control dependency is resolved. */
2940 check_clobbered_conditions (rtx insn
)
2945 if ((current_sched_info
->flags
& DO_PREDICATION
) == 0)
2948 find_all_hard_reg_sets (insn
, &t
);
2951 for (i
= 0; i
< ready
.n_ready
; i
++)
2953 rtx x
= ready_element (&ready
, i
);
2954 if (TODO_SPEC (x
) == DEP_CONTROL
&& cond_clobbered_p (x
, t
))
2956 ready_remove_insn (x
);
2960 for (i
= 0; i
<= max_insn_queue_index
; i
++)
2963 int q
= NEXT_Q_AFTER (q_ptr
, i
);
2966 for (link
= insn_queue
[q
]; link
; link
= XEXP (link
, 1))
2968 rtx x
= XEXP (link
, 0);
2969 if (TODO_SPEC (x
) == DEP_CONTROL
&& cond_clobbered_p (x
, t
))
2978 /* Return (in order):
2980 - positive if INSN adversely affects the pressure on one
2983 - negative if INSN reduces the pressure on one register class
2985 - 0 if INSN doesn't affect the pressure on any register class. */
2988 model_classify_pressure (struct model_insn_info
*insn
)
2990 struct reg_pressure_data
*reg_pressure
;
2991 int death
[N_REG_CLASSES
];
2994 calculate_reg_deaths (insn
->insn
, death
);
2995 reg_pressure
= INSN_REG_PRESSURE (insn
->insn
);
2997 for (pci
= 0; pci
< ira_pressure_classes_num
; pci
++)
2999 cl
= ira_pressure_classes
[pci
];
3000 if (death
[cl
] < reg_pressure
[pci
].set_increase
)
3002 sum
+= reg_pressure
[pci
].set_increase
- death
[cl
];
3007 /* Return true if INSN1 should come before INSN2 in the model schedule. */
3010 model_order_p (struct model_insn_info
*insn1
, struct model_insn_info
*insn2
)
3012 unsigned int height1
, height2
;
3013 unsigned int priority1
, priority2
;
3015 /* Prefer instructions with a higher model priority. */
3016 if (insn1
->model_priority
!= insn2
->model_priority
)
3017 return insn1
->model_priority
> insn2
->model_priority
;
3019 /* Combine the length of the longest path of satisfied true dependencies
3020 that leads to each instruction (depth) with the length of the longest
3021 path of any dependencies that leads from the instruction (alap).
3022 Prefer instructions with the greatest combined length. If the combined
3023 lengths are equal, prefer instructions with the greatest depth.
3025 The idea is that, if we have a set S of "equal" instructions that each
3026 have ALAP value X, and we pick one such instruction I, any true-dependent
3027 successors of I that have ALAP value X - 1 should be preferred over S.
3028 This encourages the schedule to be "narrow" rather than "wide".
3029 However, if I is a low-priority instruction that we decided to
3030 schedule because of its model_classify_pressure, and if there
3031 is a set of higher-priority instructions T, the aforementioned
3032 successors of I should not have the edge over T. */
3033 height1
= insn1
->depth
+ insn1
->alap
;
3034 height2
= insn2
->depth
+ insn2
->alap
;
3035 if (height1
!= height2
)
3036 return height1
> height2
;
3037 if (insn1
->depth
!= insn2
->depth
)
3038 return insn1
->depth
> insn2
->depth
;
3040 /* We have no real preference between INSN1 an INSN2 as far as attempts
3041 to reduce pressure go. Prefer instructions with higher priorities. */
3042 priority1
= INSN_PRIORITY (insn1
->insn
);
3043 priority2
= INSN_PRIORITY (insn2
->insn
);
3044 if (priority1
!= priority2
)
3045 return priority1
> priority2
;
3047 /* Use the original rtl sequence as a tie-breaker. */
3048 return insn1
< insn2
;
3051 /* Add INSN to the model worklist immediately after PREV. Add it to the
3052 beginning of the list if PREV is null. */
3055 model_add_to_worklist_at (struct model_insn_info
*insn
,
3056 struct model_insn_info
*prev
)
3058 gcc_assert (QUEUE_INDEX (insn
->insn
) == QUEUE_NOWHERE
);
3059 QUEUE_INDEX (insn
->insn
) = QUEUE_READY
;
3064 insn
->next
= prev
->next
;
3069 insn
->next
= model_worklist
;
3070 model_worklist
= insn
;
3073 insn
->next
->prev
= insn
;
3076 /* Remove INSN from the model worklist. */
3079 model_remove_from_worklist (struct model_insn_info
*insn
)
3081 gcc_assert (QUEUE_INDEX (insn
->insn
) == QUEUE_READY
);
3082 QUEUE_INDEX (insn
->insn
) = QUEUE_NOWHERE
;
3085 insn
->prev
->next
= insn
->next
;
3087 model_worklist
= insn
->next
;
3089 insn
->next
->prev
= insn
->prev
;
3092 /* Add INSN to the model worklist. Start looking for a suitable position
3093 between neighbors PREV and NEXT, testing at most MAX_SCHED_READY_INSNS
3094 insns either side. A null PREV indicates the beginning of the list and
3095 a null NEXT indicates the end. */
3098 model_add_to_worklist (struct model_insn_info
*insn
,
3099 struct model_insn_info
*prev
,
3100 struct model_insn_info
*next
)
3104 count
= MAX_SCHED_READY_INSNS
;
3105 if (count
> 0 && prev
&& model_order_p (insn
, prev
))
3111 while (count
> 0 && prev
&& model_order_p (insn
, prev
));
3113 while (count
> 0 && next
&& model_order_p (next
, insn
))
3119 model_add_to_worklist_at (insn
, prev
);
3122 /* INSN may now have a higher priority (in the model_order_p sense)
3123 than before. Move it up the worklist if necessary. */
3126 model_promote_insn (struct model_insn_info
*insn
)
3128 struct model_insn_info
*prev
;
3132 count
= MAX_SCHED_READY_INSNS
;
3133 while (count
> 0 && prev
&& model_order_p (insn
, prev
))
3138 if (prev
!= insn
->prev
)
3140 model_remove_from_worklist (insn
);
3141 model_add_to_worklist_at (insn
, prev
);
3145 /* Add INSN to the end of the model schedule. */
3148 model_add_to_schedule (rtx insn
)
3152 gcc_assert (QUEUE_INDEX (insn
) == QUEUE_NOWHERE
);
3153 QUEUE_INDEX (insn
) = QUEUE_SCHEDULED
;
3155 point
= VEC_length (rtx
, model_schedule
);
3156 VEC_quick_push (rtx
, model_schedule
, insn
);
3157 INSN_MODEL_INDEX (insn
) = point
+ 1;
3160 /* Analyze the instructions that are to be scheduled, setting up
3161 MODEL_INSN_INFO (...) and model_num_insns accordingly. Add ready
3162 instructions to model_worklist. */
3165 model_analyze_insns (void)
3167 rtx start
, end
, iter
;
3168 sd_iterator_def sd_it
;
3170 struct model_insn_info
*insn
, *con
;
3172 model_num_insns
= 0;
3173 start
= PREV_INSN (current_sched_info
->next_tail
);
3174 end
= current_sched_info
->prev_head
;
3175 for (iter
= start
; iter
!= end
; iter
= PREV_INSN (iter
))
3176 if (NONDEBUG_INSN_P (iter
))
3178 insn
= MODEL_INSN_INFO (iter
);
3180 FOR_EACH_DEP (iter
, SD_LIST_FORW
, sd_it
, dep
)
3182 con
= MODEL_INSN_INFO (DEP_CON (dep
));
3183 if (con
->insn
&& insn
->alap
< con
->alap
+ 1)
3184 insn
->alap
= con
->alap
+ 1;
3187 insn
->old_queue
= QUEUE_INDEX (iter
);
3188 QUEUE_INDEX (iter
) = QUEUE_NOWHERE
;
3190 insn
->unscheduled_preds
= dep_list_size (iter
, SD_LIST_HARD_BACK
);
3191 if (insn
->unscheduled_preds
== 0)
3192 model_add_to_worklist (insn
, NULL
, model_worklist
);
3198 /* The global state describes the register pressure at the start of the
3199 model schedule. Initialize GROUP accordingly. */
3202 model_init_pressure_group (struct model_pressure_group
*group
)
3206 for (pci
= 0; pci
< ira_pressure_classes_num
; pci
++)
3208 cl
= ira_pressure_classes
[pci
];
3209 group
->limits
[pci
].pressure
= curr_reg_pressure
[cl
];
3210 group
->limits
[pci
].point
= 0;
3212 /* Use index model_num_insns to record the state after the last
3213 instruction in the model schedule. */
3214 group
->model
= XNEWVEC (struct model_pressure_data
,
3215 (model_num_insns
+ 1) * ira_pressure_classes_num
);
3218 /* Record that MODEL_REF_PRESSURE (GROUP, POINT, PCI) is PRESSURE.
3219 Update the maximum pressure for the whole schedule. */
3222 model_record_pressure (struct model_pressure_group
*group
,
3223 int point
, int pci
, int pressure
)
3225 MODEL_REF_PRESSURE (group
, point
, pci
) = pressure
;
3226 if (group
->limits
[pci
].pressure
< pressure
)
3228 group
->limits
[pci
].pressure
= pressure
;
3229 group
->limits
[pci
].point
= point
;
3233 /* INSN has just been added to the end of the model schedule. Record its
3234 register-pressure information. */
3237 model_record_pressures (struct model_insn_info
*insn
)
3239 struct reg_pressure_data
*reg_pressure
;
3240 int point
, pci
, cl
, delta
;
3241 int death
[N_REG_CLASSES
];
3243 point
= model_index (insn
->insn
);
3244 if (sched_verbose
>= 2)
3250 fprintf (sched_dump
, "\n;;\tModel schedule:\n;;\n");
3251 fprintf (sched_dump
, ";;\t| idx insn | mpri hght dpth prio |\n");
3253 print_pattern (buf
, PATTERN (insn
->insn
), 0);
3254 fprintf (sched_dump
, ";;\t| %3d %4d | %4d %4d %4d %4d | %-30s ",
3255 point
, INSN_UID (insn
->insn
), insn
->model_priority
,
3256 insn
->depth
+ insn
->alap
, insn
->depth
,
3257 INSN_PRIORITY (insn
->insn
), buf
);
3259 calculate_reg_deaths (insn
->insn
, death
);
3260 reg_pressure
= INSN_REG_PRESSURE (insn
->insn
);
3261 for (pci
= 0; pci
< ira_pressure_classes_num
; pci
++)
3263 cl
= ira_pressure_classes
[pci
];
3264 delta
= reg_pressure
[pci
].set_increase
- death
[cl
];
3265 if (sched_verbose
>= 2)
3266 fprintf (sched_dump
, " %s:[%d,%+d]", reg_class_names
[cl
],
3267 curr_reg_pressure
[cl
], delta
);
3268 model_record_pressure (&model_before_pressure
, point
, pci
,
3269 curr_reg_pressure
[cl
]);
3271 if (sched_verbose
>= 2)
3272 fprintf (sched_dump
, "\n");
3275 /* All instructions have been added to the model schedule. Record the
3276 final register pressure in GROUP and set up all MODEL_MAX_PRESSUREs. */
3279 model_record_final_pressures (struct model_pressure_group
*group
)
3281 int point
, pci
, max_pressure
, ref_pressure
, cl
;
3283 for (pci
= 0; pci
< ira_pressure_classes_num
; pci
++)
3285 /* Record the final pressure for this class. */
3286 cl
= ira_pressure_classes
[pci
];
3287 point
= model_num_insns
;
3288 ref_pressure
= curr_reg_pressure
[cl
];
3289 model_record_pressure (group
, point
, pci
, ref_pressure
);
3291 /* Record the original maximum pressure. */
3292 group
->limits
[pci
].orig_pressure
= group
->limits
[pci
].pressure
;
3294 /* Update the MODEL_MAX_PRESSURE for every point of the schedule. */
3295 max_pressure
= ref_pressure
;
3296 MODEL_MAX_PRESSURE (group
, point
, pci
) = max_pressure
;
3300 ref_pressure
= MODEL_REF_PRESSURE (group
, point
, pci
);
3301 max_pressure
= MAX (max_pressure
, ref_pressure
);
3302 MODEL_MAX_PRESSURE (group
, point
, pci
) = max_pressure
;
3307 /* Update all successors of INSN, given that INSN has just been scheduled. */
3310 model_add_successors_to_worklist (struct model_insn_info
*insn
)
3312 sd_iterator_def sd_it
;
3313 struct model_insn_info
*con
;
3316 FOR_EACH_DEP (insn
->insn
, SD_LIST_FORW
, sd_it
, dep
)
3318 con
= MODEL_INSN_INFO (DEP_CON (dep
));
3319 /* Ignore debug instructions, and instructions from other blocks. */
3322 con
->unscheduled_preds
--;
3324 /* Update the depth field of each true-dependent successor.
3325 Increasing the depth gives them a higher priority than
3327 if (DEP_TYPE (dep
) == REG_DEP_TRUE
&& con
->depth
< insn
->depth
+ 1)
3329 con
->depth
= insn
->depth
+ 1;
3330 if (QUEUE_INDEX (con
->insn
) == QUEUE_READY
)
3331 model_promote_insn (con
);
3334 /* If this is a true dependency, or if there are no remaining
3335 dependencies for CON (meaning that CON only had non-true
3336 dependencies), make sure that CON is on the worklist.
3337 We don't bother otherwise because it would tend to fill the
3338 worklist with a lot of low-priority instructions that are not
3339 yet ready to issue. */
3340 if ((con
->depth
> 0 || con
->unscheduled_preds
== 0)
3341 && QUEUE_INDEX (con
->insn
) == QUEUE_NOWHERE
)
3342 model_add_to_worklist (con
, insn
, insn
->next
);
3347 /* Give INSN a higher priority than any current instruction, then give
3348 unscheduled predecessors of INSN a higher priority still. If any of
3349 those predecessors are not on the model worklist, do the same for its
3350 predecessors, and so on. */
3353 model_promote_predecessors (struct model_insn_info
*insn
)
3355 struct model_insn_info
*pro
, *first
;
3356 sd_iterator_def sd_it
;
3359 if (sched_verbose
>= 7)
3360 fprintf (sched_dump
, ";;\t+--- priority of %d = %d, priority of",
3361 INSN_UID (insn
->insn
), model_next_priority
);
3362 insn
->model_priority
= model_next_priority
++;
3363 model_remove_from_worklist (insn
);
3364 model_add_to_worklist_at (insn
, NULL
);
3369 FOR_EACH_DEP (insn
->insn
, SD_LIST_HARD_BACK
, sd_it
, dep
)
3371 pro
= MODEL_INSN_INFO (DEP_PRO (dep
));
3372 /* The first test is to ignore debug instructions, and instructions
3373 from other blocks. */
3375 && pro
->model_priority
!= model_next_priority
3376 && QUEUE_INDEX (pro
->insn
) != QUEUE_SCHEDULED
)
3378 pro
->model_priority
= model_next_priority
;
3379 if (sched_verbose
>= 7)
3380 fprintf (sched_dump
, " %d", INSN_UID (pro
->insn
));
3381 if (QUEUE_INDEX (pro
->insn
) == QUEUE_READY
)
3383 /* PRO is already in the worklist, but it now has
3384 a higher priority than before. Move it at the
3385 appropriate place. */
3386 model_remove_from_worklist (pro
);
3387 model_add_to_worklist (pro
, NULL
, model_worklist
);
3391 /* PRO isn't in the worklist. Recursively process
3392 its predecessors until we find one that is. */
3403 if (sched_verbose
>= 7)
3404 fprintf (sched_dump
, " = %d\n", model_next_priority
);
3405 model_next_priority
++;
3408 /* Pick one instruction from model_worklist and process it. */
3411 model_choose_insn (void)
3413 struct model_insn_info
*insn
, *fallback
;
3416 if (sched_verbose
>= 7)
3418 fprintf (sched_dump
, ";;\t+--- worklist:\n");
3419 insn
= model_worklist
;
3420 count
= MAX_SCHED_READY_INSNS
;
3421 while (count
> 0 && insn
)
3423 fprintf (sched_dump
, ";;\t+--- %d [%d, %d, %d, %d]\n",
3424 INSN_UID (insn
->insn
), insn
->model_priority
,
3425 insn
->depth
+ insn
->alap
, insn
->depth
,
3426 INSN_PRIORITY (insn
->insn
));
3432 /* Look for a ready instruction whose model_classify_priority is zero
3433 or negative, picking the highest-priority one. Adding such an
3434 instruction to the schedule now should do no harm, and may actually
3437 Failing that, see whether there is an instruction with the highest
3438 extant model_priority that is not yet ready, but which would reduce
3439 pressure if it became ready. This is designed to catch cases like:
3441 (set (mem (reg R1)) (reg R2))
3443 where the instruction is the last remaining use of R1 and where the
3444 value of R2 is not yet available (or vice versa). The death of R1
3445 means that this instruction already reduces pressure. It is of
3446 course possible that the computation of R2 involves other registers
3447 that are hard to kill, but such cases are rare enough for this
3448 heuristic to be a win in general.
3450 Failing that, just pick the highest-priority instruction in the
3452 count
= MAX_SCHED_READY_INSNS
;
3453 insn
= model_worklist
;
3457 if (count
== 0 || !insn
)
3459 insn
= fallback
? fallback
: model_worklist
;
3462 if (insn
->unscheduled_preds
)
3464 if (model_worklist
->model_priority
== insn
->model_priority
3466 && model_classify_pressure (insn
) < 0)
3471 if (model_classify_pressure (insn
) <= 0)
3478 if (sched_verbose
>= 7 && insn
!= model_worklist
)
3480 if (insn
->unscheduled_preds
)
3481 fprintf (sched_dump
, ";;\t+--- promoting insn %d, with dependencies\n",
3482 INSN_UID (insn
->insn
));
3484 fprintf (sched_dump
, ";;\t+--- promoting insn %d, which is ready\n",
3485 INSN_UID (insn
->insn
));
3487 if (insn
->unscheduled_preds
)
3488 /* INSN isn't yet ready to issue. Give all its predecessors the
3489 highest priority. */
3490 model_promote_predecessors (insn
);
3493 /* INSN is ready. Add it to the end of model_schedule and
3494 process its successors. */
3495 model_add_successors_to_worklist (insn
);
3496 model_remove_from_worklist (insn
);
3497 model_add_to_schedule (insn
->insn
);
3498 model_record_pressures (insn
);
3499 update_register_pressure (insn
->insn
);
3503 /* Restore all QUEUE_INDEXs to the values that they had before
3504 model_start_schedule was called. */
3507 model_reset_queue_indices (void)
3512 FOR_EACH_VEC_ELT (rtx
, model_schedule
, i
, insn
)
3513 QUEUE_INDEX (insn
) = MODEL_INSN_INFO (insn
)->old_queue
;
3516 /* We have calculated the model schedule and spill costs. Print a summary
3520 model_dump_pressure_summary (void)
3524 fprintf (sched_dump
, ";; Pressure summary:");
3525 for (pci
= 0; pci
< ira_pressure_classes_num
; pci
++)
3527 cl
= ira_pressure_classes
[pci
];
3528 fprintf (sched_dump
, " %s:%d", reg_class_names
[cl
],
3529 model_before_pressure
.limits
[pci
].pressure
);
3531 fprintf (sched_dump
, "\n\n");
3534 /* Initialize the SCHED_PRESSURE_MODEL information for the current
3535 scheduling region. */
3538 model_start_schedule (void)
3542 model_next_priority
= 1;
3543 model_schedule
= VEC_alloc (rtx
, heap
, sched_max_luid
);
3544 model_insns
= XCNEWVEC (struct model_insn_info
, sched_max_luid
);
3546 bb
= BLOCK_FOR_INSN (NEXT_INSN (current_sched_info
->prev_head
));
3547 initiate_reg_pressure_info (df_get_live_in (bb
));
3549 model_analyze_insns ();
3550 model_init_pressure_group (&model_before_pressure
);
3551 while (model_worklist
)
3552 model_choose_insn ();
3553 gcc_assert (model_num_insns
== (int) VEC_length (rtx
, model_schedule
));
3554 if (sched_verbose
>= 2)
3555 fprintf (sched_dump
, "\n");
3557 model_record_final_pressures (&model_before_pressure
);
3558 model_reset_queue_indices ();
3560 XDELETEVEC (model_insns
);
3562 model_curr_point
= 0;
3563 initiate_reg_pressure_info (df_get_live_in (bb
));
3564 if (sched_verbose
>= 1)
3565 model_dump_pressure_summary ();
3568 /* Free the information associated with GROUP. */
3571 model_finalize_pressure_group (struct model_pressure_group
*group
)
3573 XDELETEVEC (group
->model
);
3576 /* Free the information created by model_start_schedule. */
3579 model_end_schedule (void)
3581 model_finalize_pressure_group (&model_before_pressure
);
3582 VEC_free (rtx
, heap
, model_schedule
);
3585 /* A structure that holds local state for the loop in schedule_block. */
3586 struct sched_block_state
3588 /* True if no real insns have been scheduled in the current cycle. */
3589 bool first_cycle_insn_p
;
3590 /* True if a shadow insn has been scheduled in the current cycle, which
3591 means that no more normal insns can be issued. */
3592 bool shadows_only_p
;
3593 /* True if we're winding down a modulo schedule, which means that we only
3594 issue insns with INSN_EXACT_TICK set. */
3595 bool modulo_epilogue
;
3596 /* Initialized with the machine's issue rate every cycle, and updated
3597 by calls to the variable_issue hook. */
3601 /* INSN is the "currently executing insn". Launch each insn which was
3602 waiting on INSN. READY is the ready list which contains the insns
3603 that are ready to fire. CLOCK is the current cycle. The function
3604 returns necessary cycle advance after issuing the insn (it is not
3605 zero for insns in a schedule group). */
3608 schedule_insn (rtx insn
)
3610 sd_iterator_def sd_it
;
3615 if (sched_verbose
>= 1)
3617 struct reg_pressure_data
*pressure_info
;
3620 print_insn (buf
, insn
, 0);
3622 fprintf (sched_dump
, ";;\t%3i--> %-40s:", clock_var
, buf
);
3624 if (recog_memoized (insn
) < 0)
3625 fprintf (sched_dump
, "nothing");
3627 print_reservation (sched_dump
, insn
);
3628 pressure_info
= INSN_REG_PRESSURE (insn
);
3629 if (pressure_info
!= NULL
)
3631 fputc (':', sched_dump
);
3632 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
3633 fprintf (sched_dump
, "%s%+d(%d)",
3634 reg_class_names
[ira_pressure_classes
[i
]],
3635 pressure_info
[i
].set_increase
, pressure_info
[i
].change
);
3637 if (sched_pressure
== SCHED_PRESSURE_MODEL
3638 && model_curr_point
< model_num_insns
3639 && model_index (insn
) == model_curr_point
)
3640 fprintf (sched_dump
, ":model %d", model_curr_point
);
3641 fputc ('\n', sched_dump
);
3644 if (sched_pressure
== SCHED_PRESSURE_WEIGHTED
&& !DEBUG_INSN_P (insn
))
3645 update_reg_and_insn_max_reg_pressure (insn
);
3647 /* Scheduling instruction should have all its dependencies resolved and
3648 should have been removed from the ready list. */
3649 gcc_assert (sd_lists_empty_p (insn
, SD_LIST_HARD_BACK
));
3651 /* Reset debug insns invalidated by moving this insn. */
3652 if (MAY_HAVE_DEBUG_INSNS
&& !DEBUG_INSN_P (insn
))
3653 for (sd_it
= sd_iterator_start (insn
, SD_LIST_BACK
);
3654 sd_iterator_cond (&sd_it
, &dep
);)
3656 rtx dbg
= DEP_PRO (dep
);
3657 struct reg_use_data
*use
, *next
;
3659 if (DEP_STATUS (dep
) & DEP_CANCELLED
)
3661 sd_iterator_next (&sd_it
);
3665 gcc_assert (DEBUG_INSN_P (dbg
));
3667 if (sched_verbose
>= 6)
3668 fprintf (sched_dump
, ";;\t\tresetting: debug insn %d\n",
3671 /* ??? Rather than resetting the debug insn, we might be able
3672 to emit a debug temp before the just-scheduled insn, but
3673 this would involve checking that the expression at the
3674 point of the debug insn is equivalent to the expression
3675 before the just-scheduled insn. They might not be: the
3676 expression in the debug insn may depend on other insns not
3677 yet scheduled that set MEMs, REGs or even other debug
3678 insns. It's not clear that attempting to preserve debug
3679 information in these cases is worth the effort, given how
3680 uncommon these resets are and the likelihood that the debug
3681 temps introduced won't survive the schedule change. */
3682 INSN_VAR_LOCATION_LOC (dbg
) = gen_rtx_UNKNOWN_VAR_LOC ();
3683 df_insn_rescan (dbg
);
3685 /* Unknown location doesn't use any registers. */
3686 for (use
= INSN_REG_USE_LIST (dbg
); use
!= NULL
; use
= next
)
3688 struct reg_use_data
*prev
= use
;
3690 /* Remove use from the cyclic next_regno_use chain first. */
3691 while (prev
->next_regno_use
!= use
)
3692 prev
= prev
->next_regno_use
;
3693 prev
->next_regno_use
= use
->next_regno_use
;
3694 next
= use
->next_insn_use
;
3697 INSN_REG_USE_LIST (dbg
) = NULL
;
3699 /* We delete rather than resolve these deps, otherwise we
3700 crash in sched_free_deps(), because forward deps are
3701 expected to be released before backward deps. */
3702 sd_delete_dep (sd_it
);
3705 gcc_assert (QUEUE_INDEX (insn
) == QUEUE_NOWHERE
);
3706 QUEUE_INDEX (insn
) = QUEUE_SCHEDULED
;
3708 if (sched_pressure
== SCHED_PRESSURE_MODEL
3709 && model_curr_point
< model_num_insns
3710 && NONDEBUG_INSN_P (insn
))
3712 if (model_index (insn
) == model_curr_point
)
3715 while (model_curr_point
< model_num_insns
3716 && (QUEUE_INDEX (MODEL_INSN (model_curr_point
))
3717 == QUEUE_SCHEDULED
));
3719 model_recompute (insn
);
3720 model_update_limit_points ();
3721 update_register_pressure (insn
);
3722 if (sched_verbose
>= 2)
3723 print_curr_reg_pressure ();
3726 gcc_assert (INSN_TICK (insn
) >= MIN_TICK
);
3727 if (INSN_TICK (insn
) > clock_var
)
3728 /* INSN has been prematurely moved from the queue to the ready list.
3729 This is possible only if following flag is set. */
3730 gcc_assert (flag_sched_stalled_insns
);
3732 /* ??? Probably, if INSN is scheduled prematurely, we should leave
3733 INSN_TICK untouched. This is a machine-dependent issue, actually. */
3734 INSN_TICK (insn
) = clock_var
;
3736 check_clobbered_conditions (insn
);
3738 /* Update dependent instructions. */
3739 for (sd_it
= sd_iterator_start (insn
, SD_LIST_FORW
);
3740 sd_iterator_cond (&sd_it
, &dep
);)
3742 rtx next
= DEP_CON (dep
);
3743 bool cancelled
= (DEP_STATUS (dep
) & DEP_CANCELLED
) != 0;
3745 /* Resolve the dependence between INSN and NEXT.
3746 sd_resolve_dep () moves current dep to another list thus
3747 advancing the iterator. */
3748 sd_resolve_dep (sd_it
);
3752 if (QUEUE_INDEX (next
) != QUEUE_SCHEDULED
)
3754 int tick
= INSN_TICK (next
);
3755 gcc_assert (ORIG_PAT (next
) != NULL_RTX
);
3756 haifa_change_pattern (next
, ORIG_PAT (next
));
3757 INSN_TICK (next
) = tick
;
3758 if (sd_lists_empty_p (next
, SD_LIST_BACK
))
3759 TODO_SPEC (next
) = 0;
3760 else if (!sd_lists_empty_p (next
, SD_LIST_HARD_BACK
))
3761 TODO_SPEC (next
) = HARD_DEP
;
3766 /* Don't bother trying to mark next as ready if insn is a debug
3767 insn. If insn is the last hard dependency, it will have
3768 already been discounted. */
3769 if (DEBUG_INSN_P (insn
) && !DEBUG_INSN_P (next
))
3772 if (!IS_SPECULATION_BRANCHY_CHECK_P (insn
))
3776 effective_cost
= try_ready (next
);
3778 if (effective_cost
>= 0
3779 && SCHED_GROUP_P (next
)
3780 && advance
< effective_cost
)
3781 advance
= effective_cost
;
3784 /* Check always has only one forward dependence (to the first insn in
3785 the recovery block), therefore, this will be executed only once. */
3787 gcc_assert (sd_lists_empty_p (insn
, SD_LIST_FORW
));
3788 fix_recovery_deps (RECOVERY_BLOCK (insn
));
3792 /* Annotate the instruction with issue information -- TImode
3793 indicates that the instruction is expected not to be able
3794 to issue on the same cycle as the previous insn. A machine
3795 may use this information to decide how the instruction should
3798 && GET_CODE (PATTERN (insn
)) != USE
3799 && GET_CODE (PATTERN (insn
)) != CLOBBER
3800 && !DEBUG_INSN_P (insn
))
3802 if (reload_completed
)
3803 PUT_MODE (insn
, clock_var
> last_clock_var
? TImode
: VOIDmode
);
3804 last_clock_var
= clock_var
;
3810 /* Functions for handling of notes. */
3812 /* Add note list that ends on FROM_END to the end of TO_ENDP. */
3814 concat_note_lists (rtx from_end
, rtx
*to_endp
)
3818 /* It's easy when have nothing to concat. */
3819 if (from_end
== NULL
)
3822 /* It's also easy when destination is empty. */
3823 if (*to_endp
== NULL
)
3825 *to_endp
= from_end
;
3829 from_start
= from_end
;
3830 while (PREV_INSN (from_start
) != NULL
)
3831 from_start
= PREV_INSN (from_start
);
3833 PREV_INSN (from_start
) = *to_endp
;
3834 NEXT_INSN (*to_endp
) = from_start
;
3835 *to_endp
= from_end
;
3838 /* Delete notes between HEAD and TAIL and put them in the chain
3839 of notes ended by NOTE_LIST. */
3841 remove_notes (rtx head
, rtx tail
)
3843 rtx next_tail
, insn
, next
;
3846 if (head
== tail
&& !INSN_P (head
))
3849 next_tail
= NEXT_INSN (tail
);
3850 for (insn
= head
; insn
!= next_tail
; insn
= next
)
3852 next
= NEXT_INSN (insn
);
3856 switch (NOTE_KIND (insn
))
3858 case NOTE_INSN_BASIC_BLOCK
:
3861 case NOTE_INSN_EPILOGUE_BEG
:
3865 add_reg_note (next
, REG_SAVE_NOTE
,
3866 GEN_INT (NOTE_INSN_EPILOGUE_BEG
));
3874 /* Add the note to list that ends at NOTE_LIST. */
3875 PREV_INSN (insn
) = note_list
;
3876 NEXT_INSN (insn
) = NULL_RTX
;
3878 NEXT_INSN (note_list
) = insn
;
3883 gcc_assert ((sel_sched_p () || insn
!= tail
) && insn
!= head
);
3887 /* A structure to record enough data to allow us to backtrack the scheduler to
3888 a previous state. */
3889 struct haifa_saved_data
3891 /* Next entry on the list. */
3892 struct haifa_saved_data
*next
;
3894 /* Backtracking is associated with scheduling insns that have delay slots.
3895 DELAY_PAIR points to the structure that contains the insns involved, and
3896 the number of cycles between them. */
3897 struct delay_pair
*delay_pair
;
3899 /* Data used by the frontend (e.g. sched-ebb or sched-rgn). */
3900 void *fe_saved_data
;
3901 /* Data used by the backend. */
3902 void *be_saved_data
;
3904 /* Copies of global state. */
3905 int clock_var
, last_clock_var
;
3906 struct ready_list ready
;
3909 rtx last_scheduled_insn
;
3910 rtx last_nondebug_scheduled_insn
;
3911 int cycle_issued_insns
;
3913 /* Copies of state used in the inner loop of schedule_block. */
3914 struct sched_block_state sched_block
;
3916 /* We don't need to save q_ptr, as its value is arbitrary and we can set it
3917 to 0 when restoring. */
3922 /* A record, in reverse order, of all scheduled insns which have delay slots
3923 and may require backtracking. */
3924 static struct haifa_saved_data
*backtrack_queue
;
3926 /* For every dependency of INSN, set the FEEDS_BACKTRACK_INSN bit according
3929 mark_backtrack_feeds (rtx insn
, int set_p
)
3931 sd_iterator_def sd_it
;
3933 FOR_EACH_DEP (insn
, SD_LIST_HARD_BACK
, sd_it
, dep
)
3935 FEEDS_BACKTRACK_INSN (DEP_PRO (dep
)) = set_p
;
3939 /* Save the current scheduler state so that we can backtrack to it
3940 later if necessary. PAIR gives the insns that make it necessary to
3941 save this point. SCHED_BLOCK is the local state of schedule_block
3942 that need to be saved. */
3944 save_backtrack_point (struct delay_pair
*pair
,
3945 struct sched_block_state sched_block
)
3948 struct haifa_saved_data
*save
= XNEW (struct haifa_saved_data
);
3950 save
->curr_state
= xmalloc (dfa_state_size
);
3951 memcpy (save
->curr_state
, curr_state
, dfa_state_size
);
3953 save
->ready
.first
= ready
.first
;
3954 save
->ready
.n_ready
= ready
.n_ready
;
3955 save
->ready
.n_debug
= ready
.n_debug
;
3956 save
->ready
.veclen
= ready
.veclen
;
3957 save
->ready
.vec
= XNEWVEC (rtx
, ready
.veclen
);
3958 memcpy (save
->ready
.vec
, ready
.vec
, ready
.veclen
* sizeof (rtx
));
3960 save
->insn_queue
= XNEWVEC (rtx
, max_insn_queue_index
+ 1);
3961 save
->q_size
= q_size
;
3962 for (i
= 0; i
<= max_insn_queue_index
; i
++)
3964 int q
= NEXT_Q_AFTER (q_ptr
, i
);
3965 save
->insn_queue
[i
] = copy_INSN_LIST (insn_queue
[q
]);
3968 save
->clock_var
= clock_var
;
3969 save
->last_clock_var
= last_clock_var
;
3970 save
->cycle_issued_insns
= cycle_issued_insns
;
3971 save
->last_scheduled_insn
= last_scheduled_insn
;
3972 save
->last_nondebug_scheduled_insn
= last_nondebug_scheduled_insn
;
3974 save
->sched_block
= sched_block
;
3976 if (current_sched_info
->save_state
)
3977 save
->fe_saved_data
= (*current_sched_info
->save_state
) ();
3979 if (targetm
.sched
.alloc_sched_context
)
3981 save
->be_saved_data
= targetm
.sched
.alloc_sched_context ();
3982 targetm
.sched
.init_sched_context (save
->be_saved_data
, false);
3985 save
->be_saved_data
= NULL
;
3987 save
->delay_pair
= pair
;
3989 save
->next
= backtrack_queue
;
3990 backtrack_queue
= save
;
3994 mark_backtrack_feeds (pair
->i2
, 1);
3995 INSN_TICK (pair
->i2
) = INVALID_TICK
;
3996 INSN_EXACT_TICK (pair
->i2
) = clock_var
+ pair_delay (pair
);
3997 SHADOW_P (pair
->i2
) = pair
->stages
== 0;
3998 pair
= pair
->next_same_i1
;
4002 /* Walk the ready list and all queues. If any insns have unresolved backwards
4003 dependencies, these must be cancelled deps, broken by predication. Set or
4004 clear (depending on SET) the DEP_CANCELLED bit in DEP_STATUS. */
4007 toggle_cancelled_flags (bool set
)
4010 sd_iterator_def sd_it
;
4013 if (ready
.n_ready
> 0)
4015 rtx
*first
= ready_lastpos (&ready
);
4016 for (i
= 0; i
< ready
.n_ready
; i
++)
4017 FOR_EACH_DEP (first
[i
], SD_LIST_BACK
, sd_it
, dep
)
4018 if (!DEBUG_INSN_P (DEP_PRO (dep
)))
4021 DEP_STATUS (dep
) |= DEP_CANCELLED
;
4023 DEP_STATUS (dep
) &= ~DEP_CANCELLED
;
4026 for (i
= 0; i
<= max_insn_queue_index
; i
++)
4028 int q
= NEXT_Q_AFTER (q_ptr
, i
);
4030 for (link
= insn_queue
[q
]; link
; link
= XEXP (link
, 1))
4032 rtx insn
= XEXP (link
, 0);
4033 FOR_EACH_DEP (insn
, SD_LIST_BACK
, sd_it
, dep
)
4034 if (!DEBUG_INSN_P (DEP_PRO (dep
)))
4037 DEP_STATUS (dep
) |= DEP_CANCELLED
;
4039 DEP_STATUS (dep
) &= ~DEP_CANCELLED
;
4045 /* Pop entries from the SCHEDULED_INSNS vector up to and including INSN.
4046 Restore their dependencies to an unresolved state, and mark them as
4050 unschedule_insns_until (rtx insn
)
4052 VEC (rtx
, heap
) *recompute_vec
;
4054 recompute_vec
= VEC_alloc (rtx
, heap
, 0);
4056 /* Make two passes over the insns to be unscheduled. First, we clear out
4057 dependencies and other trivial bookkeeping. */
4061 sd_iterator_def sd_it
;
4064 last
= VEC_pop (rtx
, scheduled_insns
);
4066 /* This will be changed by restore_backtrack_point if the insn is in
4068 QUEUE_INDEX (last
) = QUEUE_NOWHERE
;
4070 INSN_TICK (last
) = INVALID_TICK
;
4072 if (modulo_ii
> 0 && INSN_UID (last
) < modulo_iter0_max_uid
)
4073 modulo_insns_scheduled
--;
4075 for (sd_it
= sd_iterator_start (last
, SD_LIST_RES_FORW
);
4076 sd_iterator_cond (&sd_it
, &dep
);)
4078 rtx con
= DEP_CON (dep
);
4079 sd_unresolve_dep (sd_it
);
4080 if (!MUST_RECOMPUTE_SPEC_P (con
))
4082 MUST_RECOMPUTE_SPEC_P (con
) = 1;
4083 VEC_safe_push (rtx
, heap
, recompute_vec
, con
);
4091 /* A second pass, to update ready and speculation status for insns
4092 depending on the unscheduled ones. The first pass must have
4093 popped the scheduled_insns vector up to the point where we
4094 restart scheduling, as recompute_todo_spec requires it to be
4096 while (!VEC_empty (rtx
, recompute_vec
))
4100 con
= VEC_pop (rtx
, recompute_vec
);
4101 MUST_RECOMPUTE_SPEC_P (con
) = 0;
4102 if (!sd_lists_empty_p (con
, SD_LIST_HARD_BACK
))
4104 TODO_SPEC (con
) = HARD_DEP
;
4105 INSN_TICK (con
) = INVALID_TICK
;
4106 if (PREDICATED_PAT (con
) != NULL_RTX
)
4107 haifa_change_pattern (con
, ORIG_PAT (con
));
4109 else if (QUEUE_INDEX (con
) != QUEUE_SCHEDULED
)
4110 TODO_SPEC (con
) = recompute_todo_spec (con
);
4112 VEC_free (rtx
, heap
, recompute_vec
);
4115 /* Restore scheduler state from the topmost entry on the backtracking queue.
4116 PSCHED_BLOCK_P points to the local data of schedule_block that we must
4117 overwrite with the saved data.
4118 The caller must already have called unschedule_insns_until. */
4121 restore_last_backtrack_point (struct sched_block_state
*psched_block
)
4125 struct haifa_saved_data
*save
= backtrack_queue
;
4127 backtrack_queue
= save
->next
;
4129 if (current_sched_info
->restore_state
)
4130 (*current_sched_info
->restore_state
) (save
->fe_saved_data
);
4132 if (targetm
.sched
.alloc_sched_context
)
4134 targetm
.sched
.set_sched_context (save
->be_saved_data
);
4135 targetm
.sched
.free_sched_context (save
->be_saved_data
);
4138 /* Clear the QUEUE_INDEX of everything in the ready list or one
4140 if (ready
.n_ready
> 0)
4142 rtx
*first
= ready_lastpos (&ready
);
4143 for (i
= 0; i
< ready
.n_ready
; i
++)
4145 rtx insn
= first
[i
];
4146 QUEUE_INDEX (insn
) = QUEUE_NOWHERE
;
4147 INSN_TICK (insn
) = INVALID_TICK
;
4150 for (i
= 0; i
<= max_insn_queue_index
; i
++)
4152 int q
= NEXT_Q_AFTER (q_ptr
, i
);
4154 for (link
= insn_queue
[q
]; link
; link
= XEXP (link
, 1))
4156 rtx x
= XEXP (link
, 0);
4157 QUEUE_INDEX (x
) = QUEUE_NOWHERE
;
4158 INSN_TICK (x
) = INVALID_TICK
;
4160 free_INSN_LIST_list (&insn_queue
[q
]);
4164 ready
= save
->ready
;
4166 if (ready
.n_ready
> 0)
4168 rtx
*first
= ready_lastpos (&ready
);
4169 for (i
= 0; i
< ready
.n_ready
; i
++)
4171 rtx insn
= first
[i
];
4172 QUEUE_INDEX (insn
) = QUEUE_READY
;
4173 TODO_SPEC (insn
) = recompute_todo_spec (insn
);
4174 INSN_TICK (insn
) = save
->clock_var
;
4179 q_size
= save
->q_size
;
4180 for (i
= 0; i
<= max_insn_queue_index
; i
++)
4182 int q
= NEXT_Q_AFTER (q_ptr
, i
);
4184 insn_queue
[q
] = save
->insn_queue
[q
];
4186 for (link
= insn_queue
[q
]; link
; link
= XEXP (link
, 1))
4188 rtx x
= XEXP (link
, 0);
4189 QUEUE_INDEX (x
) = i
;
4190 TODO_SPEC (x
) = recompute_todo_spec (x
);
4191 INSN_TICK (x
) = save
->clock_var
+ i
;
4194 free (save
->insn_queue
);
4196 toggle_cancelled_flags (true);
4198 clock_var
= save
->clock_var
;
4199 last_clock_var
= save
->last_clock_var
;
4200 cycle_issued_insns
= save
->cycle_issued_insns
;
4201 last_scheduled_insn
= save
->last_scheduled_insn
;
4202 last_nondebug_scheduled_insn
= save
->last_nondebug_scheduled_insn
;
4204 *psched_block
= save
->sched_block
;
4206 memcpy (curr_state
, save
->curr_state
, dfa_state_size
);
4207 free (save
->curr_state
);
4209 mark_backtrack_feeds (save
->delay_pair
->i2
, 0);
4213 for (save
= backtrack_queue
; save
; save
= save
->next
)
4215 mark_backtrack_feeds (save
->delay_pair
->i2
, 1);
4219 /* Discard all data associated with the topmost entry in the backtrack
4220 queue. If RESET_TICK is false, we just want to free the data. If true,
4221 we are doing this because we discovered a reason to backtrack. In the
4222 latter case, also reset the INSN_TICK for the shadow insn. */
4224 free_topmost_backtrack_point (bool reset_tick
)
4226 struct haifa_saved_data
*save
= backtrack_queue
;
4229 backtrack_queue
= save
->next
;
4233 struct delay_pair
*pair
= save
->delay_pair
;
4236 INSN_TICK (pair
->i2
) = INVALID_TICK
;
4237 INSN_EXACT_TICK (pair
->i2
) = INVALID_TICK
;
4238 pair
= pair
->next_same_i1
;
4241 if (targetm
.sched
.free_sched_context
)
4242 targetm
.sched
.free_sched_context (save
->be_saved_data
);
4243 if (current_sched_info
->restore_state
)
4244 free (save
->fe_saved_data
);
4245 for (i
= 0; i
<= max_insn_queue_index
; i
++)
4246 free_INSN_LIST_list (&save
->insn_queue
[i
]);
4247 free (save
->insn_queue
);
4248 free (save
->curr_state
);
4249 free (save
->ready
.vec
);
4253 /* Free the entire backtrack queue. */
4255 free_backtrack_queue (void)
4257 while (backtrack_queue
)
4258 free_topmost_backtrack_point (false);
4261 /* Compute INSN_TICK_ESTIMATE for INSN. PROCESSED is a bitmap of
4262 instructions we've previously encountered, a set bit prevents
4263 recursion. BUDGET is a limit on how far ahead we look, it is
4264 reduced on recursive calls. Return true if we produced a good
4265 estimate, or false if we exceeded the budget. */
4267 estimate_insn_tick (bitmap processed
, rtx insn
, int budget
)
4269 sd_iterator_def sd_it
;
4271 int earliest
= INSN_TICK (insn
);
4273 FOR_EACH_DEP (insn
, SD_LIST_BACK
, sd_it
, dep
)
4275 rtx pro
= DEP_PRO (dep
);
4278 if (DEP_STATUS (dep
) & DEP_CANCELLED
)
4281 if (QUEUE_INDEX (pro
) == QUEUE_SCHEDULED
)
4282 gcc_assert (INSN_TICK (pro
) + dep_cost (dep
) <= INSN_TICK (insn
));
4285 int cost
= dep_cost (dep
);
4288 if (!bitmap_bit_p (processed
, INSN_LUID (pro
)))
4290 if (!estimate_insn_tick (processed
, pro
, budget
- cost
))
4293 gcc_assert (INSN_TICK_ESTIMATE (pro
) != INVALID_TICK
);
4294 t
= INSN_TICK_ESTIMATE (pro
) + cost
;
4295 if (earliest
== INVALID_TICK
|| t
> earliest
)
4299 bitmap_set_bit (processed
, INSN_LUID (insn
));
4300 INSN_TICK_ESTIMATE (insn
) = earliest
;
4304 /* Examine the pair of insns in P, and estimate (optimistically, assuming
4305 infinite resources) the cycle in which the delayed shadow can be issued.
4306 Return the number of cycles that must pass before the real insn can be
4307 issued in order to meet this constraint. */
4309 estimate_shadow_tick (struct delay_pair
*p
)
4311 bitmap_head processed
;
4314 bitmap_initialize (&processed
, 0);
4316 cutoff
= !estimate_insn_tick (&processed
, p
->i2
,
4317 max_insn_queue_index
+ pair_delay (p
));
4318 bitmap_clear (&processed
);
4320 return max_insn_queue_index
;
4321 t
= INSN_TICK_ESTIMATE (p
->i2
) - (clock_var
+ pair_delay (p
) + 1);
4327 /* If INSN has no unresolved backwards dependencies, add it to the schedule and
4328 recursively resolve all its forward dependencies. */
4330 resolve_dependencies (rtx insn
)
4332 sd_iterator_def sd_it
;
4335 /* Don't use sd_lists_empty_p; it ignores debug insns. */
4336 if (DEPS_LIST_FIRST (INSN_HARD_BACK_DEPS (insn
)) != NULL
4337 || DEPS_LIST_FIRST (INSN_SPEC_BACK_DEPS (insn
)) != NULL
)
4340 if (sched_verbose
>= 4)
4341 fprintf (sched_dump
, ";;\tquickly resolving %d\n", INSN_UID (insn
));
4343 if (QUEUE_INDEX (insn
) >= 0)
4344 queue_remove (insn
);
4346 VEC_safe_push (rtx
, heap
, scheduled_insns
, insn
);
4348 /* Update dependent instructions. */
4349 for (sd_it
= sd_iterator_start (insn
, SD_LIST_FORW
);
4350 sd_iterator_cond (&sd_it
, &dep
);)
4352 rtx next
= DEP_CON (dep
);
4354 if (sched_verbose
>= 4)
4355 fprintf (sched_dump
, ";;\t\tdep %d against %d\n", INSN_UID (insn
),
4358 /* Resolve the dependence between INSN and NEXT.
4359 sd_resolve_dep () moves current dep to another list thus
4360 advancing the iterator. */
4361 sd_resolve_dep (sd_it
);
4363 if (!IS_SPECULATION_BRANCHY_CHECK_P (insn
))
4365 resolve_dependencies (next
);
4368 /* Check always has only one forward dependence (to the first insn in
4369 the recovery block), therefore, this will be executed only once. */
4371 gcc_assert (sd_lists_empty_p (insn
, SD_LIST_FORW
));
4377 /* Return the head and tail pointers of ebb starting at BEG and ending
4380 get_ebb_head_tail (basic_block beg
, basic_block end
, rtx
*headp
, rtx
*tailp
)
4382 rtx beg_head
= BB_HEAD (beg
);
4383 rtx beg_tail
= BB_END (beg
);
4384 rtx end_head
= BB_HEAD (end
);
4385 rtx end_tail
= BB_END (end
);
4387 /* Don't include any notes or labels at the beginning of the BEG
4388 basic block, or notes at the end of the END basic blocks. */
4390 if (LABEL_P (beg_head
))
4391 beg_head
= NEXT_INSN (beg_head
);
4393 while (beg_head
!= beg_tail
)
4394 if (NOTE_P (beg_head
))
4395 beg_head
= NEXT_INSN (beg_head
);
4396 else if (DEBUG_INSN_P (beg_head
))
4400 for (note
= NEXT_INSN (beg_head
);
4404 next
= NEXT_INSN (note
);
4407 if (sched_verbose
>= 9)
4408 fprintf (sched_dump
, "reorder %i\n", INSN_UID (note
));
4410 reorder_insns_nobb (note
, note
, PREV_INSN (beg_head
));
4412 if (BLOCK_FOR_INSN (note
) != beg
)
4413 df_insn_change_bb (note
, beg
);
4415 else if (!DEBUG_INSN_P (note
))
4427 end_head
= beg_head
;
4428 else if (LABEL_P (end_head
))
4429 end_head
= NEXT_INSN (end_head
);
4431 while (end_head
!= end_tail
)
4432 if (NOTE_P (end_tail
))
4433 end_tail
= PREV_INSN (end_tail
);
4434 else if (DEBUG_INSN_P (end_tail
))
4438 for (note
= PREV_INSN (end_tail
);
4442 prev
= PREV_INSN (note
);
4445 if (sched_verbose
>= 9)
4446 fprintf (sched_dump
, "reorder %i\n", INSN_UID (note
));
4448 reorder_insns_nobb (note
, note
, end_tail
);
4450 if (end_tail
== BB_END (end
))
4451 BB_END (end
) = note
;
4453 if (BLOCK_FOR_INSN (note
) != end
)
4454 df_insn_change_bb (note
, end
);
4456 else if (!DEBUG_INSN_P (note
))
4468 /* Return nonzero if there are no real insns in the range [ HEAD, TAIL ]. */
4471 no_real_insns_p (const_rtx head
, const_rtx tail
)
4473 while (head
!= NEXT_INSN (tail
))
4475 if (!NOTE_P (head
) && !LABEL_P (head
))
4477 head
= NEXT_INSN (head
);
4482 /* Restore-other-notes: NOTE_LIST is the end of a chain of notes
4483 previously found among the insns. Insert them just before HEAD. */
4485 restore_other_notes (rtx head
, basic_block head_bb
)
4489 rtx note_head
= note_list
;
4492 head_bb
= BLOCK_FOR_INSN (head
);
4494 head
= NEXT_INSN (bb_note (head_bb
));
4496 while (PREV_INSN (note_head
))
4498 set_block_for_insn (note_head
, head_bb
);
4499 note_head
= PREV_INSN (note_head
);
4501 /* In the above cycle we've missed this note. */
4502 set_block_for_insn (note_head
, head_bb
);
4504 PREV_INSN (note_head
) = PREV_INSN (head
);
4505 NEXT_INSN (PREV_INSN (head
)) = note_head
;
4506 PREV_INSN (head
) = note_list
;
4507 NEXT_INSN (note_list
) = head
;
4509 if (BLOCK_FOR_INSN (head
) != head_bb
)
4510 BB_END (head_bb
) = note_list
;
4518 /* Move insns that became ready to fire from queue to ready list. */
4521 queue_to_ready (struct ready_list
*ready
)
4527 q_ptr
= NEXT_Q (q_ptr
);
4529 if (dbg_cnt (sched_insn
) == false)
4531 /* If debug counter is activated do not requeue the first
4532 nonscheduled insn. */
4533 skip_insn
= nonscheduled_insns_begin
;
4536 skip_insn
= next_nonnote_nondebug_insn (skip_insn
);
4538 while (QUEUE_INDEX (skip_insn
) == QUEUE_SCHEDULED
);
4541 skip_insn
= NULL_RTX
;
4543 /* Add all pending insns that can be scheduled without stalls to the
4545 for (link
= insn_queue
[q_ptr
]; link
; link
= XEXP (link
, 1))
4547 insn
= XEXP (link
, 0);
4550 if (sched_verbose
>= 2)
4551 fprintf (sched_dump
, ";;\t\tQ-->Ready: insn %s: ",
4552 (*current_sched_info
->print_insn
) (insn
, 0));
4554 /* If the ready list is full, delay the insn for 1 cycle.
4555 See the comment in schedule_block for the rationale. */
4556 if (!reload_completed
4557 && (ready
->n_ready
- ready
->n_debug
> MAX_SCHED_READY_INSNS
4558 || (sched_pressure
== SCHED_PRESSURE_MODEL
4559 /* Limit pressure recalculations to MAX_SCHED_READY_INSNS
4560 instructions too. */
4561 && model_index (insn
) > (model_curr_point
4562 + MAX_SCHED_READY_INSNS
)))
4563 && !(sched_pressure
== SCHED_PRESSURE_MODEL
4564 && model_curr_point
< model_num_insns
4565 /* Always allow the next model instruction to issue. */
4566 && model_index (insn
) == model_curr_point
)
4567 && !SCHED_GROUP_P (insn
)
4568 && insn
!= skip_insn
)
4569 queue_insn (insn
, 1, "ready full");
4572 ready_add (ready
, insn
, false);
4573 if (sched_verbose
>= 2)
4574 fprintf (sched_dump
, "moving to ready without stalls\n");
4577 free_INSN_LIST_list (&insn_queue
[q_ptr
]);
4579 /* If there are no ready insns, stall until one is ready and add all
4580 of the pending insns at that point to the ready list. */
4581 if (ready
->n_ready
== 0)
4585 for (stalls
= 1; stalls
<= max_insn_queue_index
; stalls
++)
4587 if ((link
= insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)]))
4589 for (; link
; link
= XEXP (link
, 1))
4591 insn
= XEXP (link
, 0);
4594 if (sched_verbose
>= 2)
4595 fprintf (sched_dump
, ";;\t\tQ-->Ready: insn %s: ",
4596 (*current_sched_info
->print_insn
) (insn
, 0));
4598 ready_add (ready
, insn
, false);
4599 if (sched_verbose
>= 2)
4600 fprintf (sched_dump
, "moving to ready with %d stalls\n", stalls
);
4602 free_INSN_LIST_list (&insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)]);
4604 advance_one_cycle ();
4609 advance_one_cycle ();
4612 q_ptr
= NEXT_Q_AFTER (q_ptr
, stalls
);
4613 clock_var
+= stalls
;
4617 /* Used by early_queue_to_ready. Determines whether it is "ok" to
4618 prematurely move INSN from the queue to the ready list. Currently,
4619 if a target defines the hook 'is_costly_dependence', this function
4620 uses the hook to check whether there exist any dependences which are
4621 considered costly by the target, between INSN and other insns that
4622 have already been scheduled. Dependences are checked up to Y cycles
4623 back, with default Y=1; The flag -fsched-stalled-insns-dep=Y allows
4624 controlling this value.
4625 (Other considerations could be taken into account instead (or in
4626 addition) depending on user flags and target hooks. */
4629 ok_for_early_queue_removal (rtx insn
)
4631 if (targetm
.sched
.is_costly_dependence
)
4635 int i
= VEC_length (rtx
, scheduled_insns
);
4636 for (n_cycles
= flag_sched_stalled_insns_dep
; n_cycles
; n_cycles
--)
4642 prev_insn
= VEC_index (rtx
, scheduled_insns
, i
);
4644 if (!NOTE_P (prev_insn
))
4648 dep
= sd_find_dep_between (prev_insn
, insn
, true);
4652 cost
= dep_cost (dep
);
4654 if (targetm
.sched
.is_costly_dependence (dep
, cost
,
4655 flag_sched_stalled_insns_dep
- n_cycles
))
4660 if (GET_MODE (prev_insn
) == TImode
) /* end of dispatch group */
4673 /* Remove insns from the queue, before they become "ready" with respect
4674 to FU latency considerations. */
4677 early_queue_to_ready (state_t state
, struct ready_list
*ready
)
4685 state_t temp_state
= alloca (dfa_state_size
);
4687 int insns_removed
= 0;
4690 Flag '-fsched-stalled-insns=X' determines the aggressiveness of this
4693 X == 0: There is no limit on how many queued insns can be removed
4694 prematurely. (flag_sched_stalled_insns = -1).
4696 X >= 1: Only X queued insns can be removed prematurely in each
4697 invocation. (flag_sched_stalled_insns = X).
4699 Otherwise: Early queue removal is disabled.
4700 (flag_sched_stalled_insns = 0)
4703 if (! flag_sched_stalled_insns
)
4706 for (stalls
= 0; stalls
<= max_insn_queue_index
; stalls
++)
4708 if ((link
= insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)]))
4710 if (sched_verbose
> 6)
4711 fprintf (sched_dump
, ";; look at index %d + %d\n", q_ptr
, stalls
);
4716 next_link
= XEXP (link
, 1);
4717 insn
= XEXP (link
, 0);
4718 if (insn
&& sched_verbose
> 6)
4719 print_rtl_single (sched_dump
, insn
);
4721 memcpy (temp_state
, state
, dfa_state_size
);
4722 if (recog_memoized (insn
) < 0)
4723 /* non-negative to indicate that it's not ready
4724 to avoid infinite Q->R->Q->R... */
4727 cost
= state_transition (temp_state
, insn
);
4729 if (sched_verbose
>= 6)
4730 fprintf (sched_dump
, "transition cost = %d\n", cost
);
4732 move_to_ready
= false;
4735 move_to_ready
= ok_for_early_queue_removal (insn
);
4736 if (move_to_ready
== true)
4738 /* move from Q to R */
4740 ready_add (ready
, insn
, false);
4743 XEXP (prev_link
, 1) = next_link
;
4745 insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)] = next_link
;
4747 free_INSN_LIST_node (link
);
4749 if (sched_verbose
>= 2)
4750 fprintf (sched_dump
, ";;\t\tEarly Q-->Ready: insn %s\n",
4751 (*current_sched_info
->print_insn
) (insn
, 0));
4754 if (insns_removed
== flag_sched_stalled_insns
)
4755 /* Remove no more than flag_sched_stalled_insns insns
4756 from Q at a time. */
4757 return insns_removed
;
4761 if (move_to_ready
== false)
4768 } /* for stalls.. */
4770 return insns_removed
;
4774 /* Print the ready list for debugging purposes. Callable from debugger. */
4777 debug_ready_list (struct ready_list
*ready
)
4782 if (ready
->n_ready
== 0)
4784 fprintf (sched_dump
, "\n");
4788 p
= ready_lastpos (ready
);
4789 for (i
= 0; i
< ready
->n_ready
; i
++)
4791 fprintf (sched_dump
, " %s:%d",
4792 (*current_sched_info
->print_insn
) (p
[i
], 0),
4794 if (sched_pressure
!= SCHED_PRESSURE_NONE
)
4795 fprintf (sched_dump
, "(cost=%d",
4796 INSN_REG_PRESSURE_EXCESS_COST_CHANGE (p
[i
]));
4797 if (INSN_TICK (p
[i
]) > clock_var
)
4798 fprintf (sched_dump
, ":delay=%d", INSN_TICK (p
[i
]) - clock_var
);
4799 if (sched_pressure
!= SCHED_PRESSURE_NONE
)
4800 fprintf (sched_dump
, ")");
4802 fprintf (sched_dump
, "\n");
4805 /* Search INSN for REG_SAVE_NOTE notes and convert them back into insn
4806 NOTEs. This is used for NOTE_INSN_EPILOGUE_BEG, so that sched-ebb
4807 replaces the epilogue note in the correct basic block. */
4809 reemit_notes (rtx insn
)
4811 rtx note
, last
= insn
;
4813 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
4815 if (REG_NOTE_KIND (note
) == REG_SAVE_NOTE
)
4817 enum insn_note note_type
= (enum insn_note
) INTVAL (XEXP (note
, 0));
4819 last
= emit_note_before (note_type
, last
);
4820 remove_note (insn
, note
);
4825 /* Move INSN. Reemit notes if needed. Update CFG, if needed. */
4827 move_insn (rtx insn
, rtx last
, rtx nt
)
4829 if (PREV_INSN (insn
) != last
)
4835 bb
= BLOCK_FOR_INSN (insn
);
4837 /* BB_HEAD is either LABEL or NOTE. */
4838 gcc_assert (BB_HEAD (bb
) != insn
);
4840 if (BB_END (bb
) == insn
)
4841 /* If this is last instruction in BB, move end marker one
4844 /* Jumps are always placed at the end of basic block. */
4845 jump_p
= control_flow_insn_p (insn
);
4848 || ((common_sched_info
->sched_pass_id
== SCHED_RGN_PASS
)
4849 && IS_SPECULATION_BRANCHY_CHECK_P (insn
))
4850 || (common_sched_info
->sched_pass_id
4851 == SCHED_EBB_PASS
));
4853 gcc_assert (BLOCK_FOR_INSN (PREV_INSN (insn
)) == bb
);
4855 BB_END (bb
) = PREV_INSN (insn
);
4858 gcc_assert (BB_END (bb
) != last
);
4861 /* We move the block note along with jump. */
4865 note
= NEXT_INSN (insn
);
4866 while (NOTE_NOT_BB_P (note
) && note
!= nt
)
4867 note
= NEXT_INSN (note
);
4871 || BARRIER_P (note
)))
4872 note
= NEXT_INSN (note
);
4874 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
4879 NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (note
);
4880 PREV_INSN (NEXT_INSN (note
)) = PREV_INSN (insn
);
4882 NEXT_INSN (note
) = NEXT_INSN (last
);
4883 PREV_INSN (NEXT_INSN (last
)) = note
;
4885 NEXT_INSN (last
) = insn
;
4886 PREV_INSN (insn
) = last
;
4888 bb
= BLOCK_FOR_INSN (last
);
4892 fix_jump_move (insn
);
4894 if (BLOCK_FOR_INSN (insn
) != bb
)
4895 move_block_after_check (insn
);
4897 gcc_assert (BB_END (bb
) == last
);
4900 df_insn_change_bb (insn
, bb
);
4902 /* Update BB_END, if needed. */
4903 if (BB_END (bb
) == last
)
4907 SCHED_GROUP_P (insn
) = 0;
4910 /* Return true if scheduling INSN will finish current clock cycle. */
4912 insn_finishes_cycle_p (rtx insn
)
4914 if (SCHED_GROUP_P (insn
))
4915 /* After issuing INSN, rest of the sched_group will be forced to issue
4916 in order. Don't make any plans for the rest of cycle. */
4919 /* Finishing the block will, apparently, finish the cycle. */
4920 if (current_sched_info
->insn_finishes_block_p
4921 && current_sched_info
->insn_finishes_block_p (insn
))
4927 /* Define type for target data used in multipass scheduling. */
4928 #ifndef TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DATA_T
4929 # define TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DATA_T int
4931 typedef TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DATA_T first_cycle_multipass_data_t
;
4933 /* The following structure describe an entry of the stack of choices. */
4936 /* Ordinal number of the issued insn in the ready queue. */
4938 /* The number of the rest insns whose issues we should try. */
4940 /* The number of issued essential insns. */
4942 /* State after issuing the insn. */
4944 /* Target-specific data. */
4945 first_cycle_multipass_data_t target_data
;
4948 /* The following array is used to implement a stack of choices used in
4949 function max_issue. */
4950 static struct choice_entry
*choice_stack
;
4952 /* This holds the value of the target dfa_lookahead hook. */
4955 /* The following variable value is maximal number of tries of issuing
4956 insns for the first cycle multipass insn scheduling. We define
4957 this value as constant*(DFA_LOOKAHEAD**ISSUE_RATE). We would not
4958 need this constraint if all real insns (with non-negative codes)
4959 had reservations because in this case the algorithm complexity is
4960 O(DFA_LOOKAHEAD**ISSUE_RATE). Unfortunately, the dfa descriptions
4961 might be incomplete and such insn might occur. For such
4962 descriptions, the complexity of algorithm (without the constraint)
4963 could achieve DFA_LOOKAHEAD ** N , where N is the queue length. */
4964 static int max_lookahead_tries
;
4966 /* The following value is value of hook
4967 `first_cycle_multipass_dfa_lookahead' at the last call of
4969 static int cached_first_cycle_multipass_dfa_lookahead
= 0;
4971 /* The following value is value of `issue_rate' at the last call of
4973 static int cached_issue_rate
= 0;
4975 /* The following function returns maximal (or close to maximal) number
4976 of insns which can be issued on the same cycle and one of which
4977 insns is insns with the best rank (the first insn in READY). To
4978 make this function tries different samples of ready insns. READY
4979 is current queue `ready'. Global array READY_TRY reflects what
4980 insns are already issued in this try. The function stops immediately,
4981 if it reached the such a solution, that all instruction can be issued.
4982 INDEX will contain index of the best insn in READY. The following
4983 function is used only for first cycle multipass scheduling.
4987 This function expects recognized insns only. All USEs,
4988 CLOBBERs, etc must be filtered elsewhere. */
4990 max_issue (struct ready_list
*ready
, int privileged_n
, state_t state
,
4991 bool first_cycle_insn_p
, int *index
)
4993 int n
, i
, all
, n_ready
, best
, delay
, tries_num
;
4995 struct choice_entry
*top
;
4998 n_ready
= ready
->n_ready
;
4999 gcc_assert (dfa_lookahead
>= 1 && privileged_n
>= 0
5000 && privileged_n
<= n_ready
);
5002 /* Init MAX_LOOKAHEAD_TRIES. */
5003 if (cached_first_cycle_multipass_dfa_lookahead
!= dfa_lookahead
)
5005 cached_first_cycle_multipass_dfa_lookahead
= dfa_lookahead
;
5006 max_lookahead_tries
= 100;
5007 for (i
= 0; i
< issue_rate
; i
++)
5008 max_lookahead_tries
*= dfa_lookahead
;
5011 /* Init max_points. */
5012 more_issue
= issue_rate
- cycle_issued_insns
;
5013 gcc_assert (more_issue
>= 0);
5015 /* The number of the issued insns in the best solution. */
5020 /* Set initial state of the search. */
5021 memcpy (top
->state
, state
, dfa_state_size
);
5022 top
->rest
= dfa_lookahead
;
5024 if (targetm
.sched
.first_cycle_multipass_begin
)
5025 targetm
.sched
.first_cycle_multipass_begin (&top
->target_data
,
5027 first_cycle_insn_p
);
5029 /* Count the number of the insns to search among. */
5030 for (all
= i
= 0; i
< n_ready
; i
++)
5034 /* I is the index of the insn to try next. */
5039 if (/* If we've reached a dead end or searched enough of what we have
5042 /* or have nothing else to try... */
5044 /* or should not issue more. */
5045 || top
->n
>= more_issue
)
5047 /* ??? (... || i == n_ready). */
5048 gcc_assert (i
<= n_ready
);
5050 /* We should not issue more than issue_rate instructions. */
5051 gcc_assert (top
->n
<= more_issue
);
5053 if (top
== choice_stack
)
5056 if (best
< top
- choice_stack
)
5061 /* Try to find issued privileged insn. */
5062 while (n
&& !ready_try
[--n
])
5066 if (/* If all insns are equally good... */
5068 /* Or a privileged insn will be issued. */
5070 /* Then we have a solution. */
5072 best
= top
- choice_stack
;
5073 /* This is the index of the insn issued first in this
5075 *index
= choice_stack
[1].index
;
5076 if (top
->n
== more_issue
|| best
== all
)
5081 /* Set ready-list index to point to the last insn
5082 ('i++' below will advance it to the next insn). */
5088 if (targetm
.sched
.first_cycle_multipass_backtrack
)
5089 targetm
.sched
.first_cycle_multipass_backtrack (&top
->target_data
,
5090 ready_try
, n_ready
);
5093 memcpy (state
, top
->state
, dfa_state_size
);
5095 else if (!ready_try
[i
])
5098 if (tries_num
> max_lookahead_tries
)
5100 insn
= ready_element (ready
, i
);
5101 delay
= state_transition (state
, insn
);
5104 if (state_dead_lock_p (state
)
5105 || insn_finishes_cycle_p (insn
))
5106 /* We won't issue any more instructions in the next
5113 if (memcmp (top
->state
, state
, dfa_state_size
) != 0)
5116 /* Advance to the next choice_entry. */
5118 /* Initialize it. */
5119 top
->rest
= dfa_lookahead
;
5122 memcpy (top
->state
, state
, dfa_state_size
);
5125 if (targetm
.sched
.first_cycle_multipass_issue
)
5126 targetm
.sched
.first_cycle_multipass_issue (&top
->target_data
,
5136 /* Increase ready-list index. */
5140 if (targetm
.sched
.first_cycle_multipass_end
)
5141 targetm
.sched
.first_cycle_multipass_end (best
!= 0
5142 ? &choice_stack
[1].target_data
5145 /* Restore the original state of the DFA. */
5146 memcpy (state
, choice_stack
->state
, dfa_state_size
);
5151 /* The following function chooses insn from READY and modifies
5152 READY. The following function is used only for first
5153 cycle multipass scheduling.
5155 -1 if cycle should be advanced,
5156 0 if INSN_PTR is set to point to the desirable insn,
5157 1 if choose_ready () should be restarted without advancing the cycle. */
5159 choose_ready (struct ready_list
*ready
, bool first_cycle_insn_p
,
5164 if (dbg_cnt (sched_insn
) == false)
5166 rtx insn
= nonscheduled_insns_begin
;
5169 insn
= next_nonnote_insn (insn
);
5171 while (QUEUE_INDEX (insn
) == QUEUE_SCHEDULED
);
5173 if (QUEUE_INDEX (insn
) == QUEUE_READY
)
5174 /* INSN is in the ready_list. */
5176 nonscheduled_insns_begin
= insn
;
5177 ready_remove_insn (insn
);
5182 /* INSN is in the queue. Advance cycle to move it to the ready list. */
5188 if (targetm
.sched
.first_cycle_multipass_dfa_lookahead
)
5189 lookahead
= targetm
.sched
.first_cycle_multipass_dfa_lookahead ();
5190 if (lookahead
<= 0 || SCHED_GROUP_P (ready_element (ready
, 0))
5191 || DEBUG_INSN_P (ready_element (ready
, 0)))
5193 if (targetm
.sched
.dispatch (NULL_RTX
, IS_DISPATCH_ON
))
5194 *insn_ptr
= ready_remove_first_dispatch (ready
);
5196 *insn_ptr
= ready_remove_first (ready
);
5202 /* Try to choose the better insn. */
5203 int index
= 0, i
, n
;
5205 int try_data
= 1, try_control
= 1;
5208 insn
= ready_element (ready
, 0);
5209 if (INSN_CODE (insn
) < 0)
5211 *insn_ptr
= ready_remove_first (ready
);
5216 && spec_info
->flags
& (PREFER_NON_DATA_SPEC
5217 | PREFER_NON_CONTROL_SPEC
))
5219 for (i
= 0, n
= ready
->n_ready
; i
< n
; i
++)
5224 x
= ready_element (ready
, i
);
5227 if (spec_info
->flags
& PREFER_NON_DATA_SPEC
5228 && !(s
& DATA_SPEC
))
5231 if (!(spec_info
->flags
& PREFER_NON_CONTROL_SPEC
)
5236 if (spec_info
->flags
& PREFER_NON_CONTROL_SPEC
5237 && !(s
& CONTROL_SPEC
))
5240 if (!(spec_info
->flags
& PREFER_NON_DATA_SPEC
) || !try_data
)
5246 ts
= TODO_SPEC (insn
);
5247 if ((ts
& SPECULATIVE
)
5248 && (((!try_data
&& (ts
& DATA_SPEC
))
5249 || (!try_control
&& (ts
& CONTROL_SPEC
)))
5250 || (targetm
.sched
.first_cycle_multipass_dfa_lookahead_guard_spec
5252 .first_cycle_multipass_dfa_lookahead_guard_spec (insn
))))
5253 /* Discard speculative instruction that stands first in the ready
5256 change_queue_index (insn
, 1);
5262 for (i
= 1; i
< ready
->n_ready
; i
++)
5264 insn
= ready_element (ready
, i
);
5267 = ((!try_data
&& (TODO_SPEC (insn
) & DATA_SPEC
))
5268 || (!try_control
&& (TODO_SPEC (insn
) & CONTROL_SPEC
)));
5271 /* Let the target filter the search space. */
5272 for (i
= 1; i
< ready
->n_ready
; i
++)
5275 insn
= ready_element (ready
, i
);
5277 /* If this insn is recognizable we should have already
5278 recognized it earlier.
5279 ??? Not very clear where this is supposed to be done.
5281 gcc_checking_assert (INSN_CODE (insn
) >= 0
5282 || recog_memoized (insn
) < 0);
5285 = (/* INSN_CODE check can be omitted here as it is also done later
5287 INSN_CODE (insn
) < 0
5288 || (targetm
.sched
.first_cycle_multipass_dfa_lookahead_guard
5289 && !targetm
.sched
.first_cycle_multipass_dfa_lookahead_guard
5293 if (max_issue (ready
, 1, curr_state
, first_cycle_insn_p
, &index
) == 0)
5295 *insn_ptr
= ready_remove_first (ready
);
5296 if (sched_verbose
>= 4)
5297 fprintf (sched_dump
, ";;\t\tChosen insn (but can't issue) : %s \n",
5298 (*current_sched_info
->print_insn
) (*insn_ptr
, 0));
5303 if (sched_verbose
>= 4)
5304 fprintf (sched_dump
, ";;\t\tChosen insn : %s\n",
5305 (*current_sched_info
->print_insn
)
5306 (ready_element (ready
, index
), 0));
5308 *insn_ptr
= ready_remove (ready
, index
);
5314 /* This function is called when we have successfully scheduled a
5315 block. It uses the schedule stored in the scheduled_insns vector
5316 to rearrange the RTL. PREV_HEAD is used as the anchor to which we
5317 append the scheduled insns; TAIL is the insn after the scheduled
5318 block. TARGET_BB is the argument passed to schedule_block. */
5321 commit_schedule (rtx prev_head
, rtx tail
, basic_block
*target_bb
)
5326 last_scheduled_insn
= prev_head
;
5328 VEC_iterate (rtx
, scheduled_insns
, i
, insn
);
5331 if (control_flow_insn_p (last_scheduled_insn
)
5332 || current_sched_info
->advance_target_bb (*target_bb
, insn
))
5334 *target_bb
= current_sched_info
->advance_target_bb (*target_bb
, 0);
5340 x
= next_real_insn (last_scheduled_insn
);
5342 dump_new_block_header (1, *target_bb
, x
, tail
);
5345 last_scheduled_insn
= bb_note (*target_bb
);
5348 if (current_sched_info
->begin_move_insn
)
5349 (*current_sched_info
->begin_move_insn
) (insn
, last_scheduled_insn
);
5350 move_insn (insn
, last_scheduled_insn
,
5351 current_sched_info
->next_tail
);
5352 if (!DEBUG_INSN_P (insn
))
5353 reemit_notes (insn
);
5354 last_scheduled_insn
= insn
;
5357 VEC_truncate (rtx
, scheduled_insns
, 0);
5360 /* Examine all insns on the ready list and queue those which can't be
5361 issued in this cycle. TEMP_STATE is temporary scheduler state we
5362 can use as scratch space. If FIRST_CYCLE_INSN_P is true, no insns
5363 have been issued for the current cycle, which means it is valid to
5364 issue an asm statement.
5366 If SHADOWS_ONLY_P is true, we eliminate all real insns and only
5367 leave those for which SHADOW_P is true. If MODULO_EPILOGUE is true,
5368 we only leave insns which have an INSN_EXACT_TICK. */
5371 prune_ready_list (state_t temp_state
, bool first_cycle_insn_p
,
5372 bool shadows_only_p
, bool modulo_epilogue_p
)
5375 bool sched_group_found
= false;
5376 int min_cost_group
= 1;
5378 for (i
= 0; i
< ready
.n_ready
; i
++)
5380 rtx insn
= ready_element (&ready
, i
);
5381 if (SCHED_GROUP_P (insn
))
5383 sched_group_found
= true;
5388 /* Make two passes if there's a SCHED_GROUP_P insn; make sure to handle
5389 such an insn first and note its cost, then schedule all other insns
5390 for one cycle later. */
5391 for (pass
= sched_group_found
? 0 : 1; pass
< 2; )
5393 int n
= ready
.n_ready
;
5394 for (i
= 0; i
< n
; i
++)
5396 rtx insn
= ready_element (&ready
, i
);
5398 const char *reason
= "resource conflict";
5400 if (DEBUG_INSN_P (insn
))
5403 if (sched_group_found
&& !SCHED_GROUP_P (insn
))
5407 cost
= min_cost_group
;
5408 reason
= "not in sched group";
5410 else if (modulo_epilogue_p
5411 && INSN_EXACT_TICK (insn
) == INVALID_TICK
)
5413 cost
= max_insn_queue_index
;
5414 reason
= "not an epilogue insn";
5416 else if (shadows_only_p
&& !SHADOW_P (insn
))
5419 reason
= "not a shadow";
5421 else if (recog_memoized (insn
) < 0)
5423 if (!first_cycle_insn_p
5424 && (GET_CODE (PATTERN (insn
)) == ASM_INPUT
5425 || asm_noperands (PATTERN (insn
)) >= 0))
5429 else if (sched_pressure
!= SCHED_PRESSURE_NONE
)
5431 if (sched_pressure
== SCHED_PRESSURE_MODEL
5432 && INSN_TICK (insn
) <= clock_var
)
5434 memcpy (temp_state
, curr_state
, dfa_state_size
);
5435 if (state_transition (temp_state
, insn
) >= 0)
5436 INSN_TICK (insn
) = clock_var
+ 1;
5446 struct delay_pair
*delay_entry
;
5448 = (struct delay_pair
*)htab_find_with_hash (delay_htab
, insn
,
5449 htab_hash_pointer (insn
));
5450 while (delay_entry
&& delay_cost
== 0)
5452 delay_cost
= estimate_shadow_tick (delay_entry
);
5453 if (delay_cost
> max_insn_queue_index
)
5454 delay_cost
= max_insn_queue_index
;
5455 delay_entry
= delay_entry
->next_same_i1
;
5459 memcpy (temp_state
, curr_state
, dfa_state_size
);
5460 cost
= state_transition (temp_state
, insn
);
5465 if (cost
< delay_cost
)
5468 reason
= "shadow tick";
5473 if (SCHED_GROUP_P (insn
) && cost
> min_cost_group
)
5474 min_cost_group
= cost
;
5475 ready_remove (&ready
, i
);
5476 queue_insn (insn
, cost
, reason
);
5486 /* Called when we detect that the schedule is impossible. We examine the
5487 backtrack queue to find the earliest insn that caused this condition. */
5489 static struct haifa_saved_data
*
5490 verify_shadows (void)
5492 struct haifa_saved_data
*save
, *earliest_fail
= NULL
;
5493 for (save
= backtrack_queue
; save
; save
= save
->next
)
5496 struct delay_pair
*pair
= save
->delay_pair
;
5499 for (; pair
; pair
= pair
->next_same_i1
)
5503 if (QUEUE_INDEX (i2
) == QUEUE_SCHEDULED
)
5506 t
= INSN_TICK (i1
) + pair_delay (pair
);
5509 if (sched_verbose
>= 2)
5510 fprintf (sched_dump
,
5511 ";;\t\tfailed delay requirements for %d/%d (%d->%d)"
5513 INSN_UID (pair
->i1
), INSN_UID (pair
->i2
),
5514 INSN_TICK (pair
->i1
), INSN_EXACT_TICK (pair
->i2
));
5515 earliest_fail
= save
;
5518 if (QUEUE_INDEX (i2
) >= 0)
5520 int queued_for
= INSN_TICK (i2
);
5524 if (sched_verbose
>= 2)
5525 fprintf (sched_dump
,
5526 ";;\t\tfailed delay requirements for %d/%d"
5527 " (%d->%d), queued too late\n",
5528 INSN_UID (pair
->i1
), INSN_UID (pair
->i2
),
5529 INSN_TICK (pair
->i1
), INSN_EXACT_TICK (pair
->i2
));
5530 earliest_fail
= save
;
5537 return earliest_fail
;
5540 /* Use forward list scheduling to rearrange insns of block pointed to by
5541 TARGET_BB, possibly bringing insns from subsequent blocks in the same
5545 schedule_block (basic_block
*target_bb
)
5548 bool success
= modulo_ii
== 0;
5549 struct sched_block_state ls
;
5550 state_t temp_state
= NULL
; /* It is used for multipass scheduling. */
5551 int sort_p
, advance
, start_clock_var
;
5553 /* Head/tail info for this block. */
5554 rtx prev_head
= current_sched_info
->prev_head
;
5555 rtx next_tail
= current_sched_info
->next_tail
;
5556 rtx head
= NEXT_INSN (prev_head
);
5557 rtx tail
= PREV_INSN (next_tail
);
5559 /* We used to have code to avoid getting parameters moved from hard
5560 argument registers into pseudos.
5562 However, it was removed when it proved to be of marginal benefit
5563 and caused problems because schedule_block and compute_forward_dependences
5564 had different notions of what the "head" insn was. */
5566 gcc_assert (head
!= tail
|| INSN_P (head
));
5568 haifa_recovery_bb_recently_added_p
= false;
5570 backtrack_queue
= NULL
;
5574 dump_new_block_header (0, *target_bb
, head
, tail
);
5576 state_reset (curr_state
);
5578 /* Clear the ready list. */
5579 ready
.first
= ready
.veclen
- 1;
5583 /* It is used for first cycle multipass scheduling. */
5584 temp_state
= alloca (dfa_state_size
);
5586 if (targetm
.sched
.init
)
5587 targetm
.sched
.init (sched_dump
, sched_verbose
, ready
.veclen
);
5589 /* We start inserting insns after PREV_HEAD. */
5590 last_scheduled_insn
= nonscheduled_insns_begin
= prev_head
;
5591 last_nondebug_scheduled_insn
= NULL_RTX
;
5593 gcc_assert ((NOTE_P (last_scheduled_insn
)
5594 || DEBUG_INSN_P (last_scheduled_insn
))
5595 && BLOCK_FOR_INSN (last_scheduled_insn
) == *target_bb
);
5597 /* Initialize INSN_QUEUE. Q_SIZE is the total number of insns in the
5602 insn_queue
= XALLOCAVEC (rtx
, max_insn_queue_index
+ 1);
5603 memset (insn_queue
, 0, (max_insn_queue_index
+ 1) * sizeof (rtx
));
5605 /* Start just before the beginning of time. */
5608 /* We need queue and ready lists and clock_var be initialized
5609 in try_ready () (which is called through init_ready_list ()). */
5610 (*current_sched_info
->init_ready_list
) ();
5612 if (sched_pressure
== SCHED_PRESSURE_MODEL
)
5613 model_start_schedule ();
5615 /* The algorithm is O(n^2) in the number of ready insns at any given
5616 time in the worst case. Before reload we are more likely to have
5617 big lists so truncate them to a reasonable size. */
5618 if (!reload_completed
5619 && ready
.n_ready
- ready
.n_debug
> MAX_SCHED_READY_INSNS
)
5621 ready_sort (&ready
);
5623 /* Find first free-standing insn past MAX_SCHED_READY_INSNS.
5624 If there are debug insns, we know they're first. */
5625 for (i
= MAX_SCHED_READY_INSNS
+ ready
.n_debug
; i
< ready
.n_ready
; i
++)
5626 if (!SCHED_GROUP_P (ready_element (&ready
, i
)))
5629 if (sched_verbose
>= 2)
5631 fprintf (sched_dump
,
5632 ";;\t\tReady list on entry: %d insns\n", ready
.n_ready
);
5633 fprintf (sched_dump
,
5634 ";;\t\t before reload => truncated to %d insns\n", i
);
5637 /* Delay all insns past it for 1 cycle. If debug counter is
5638 activated make an exception for the insn right after
5639 nonscheduled_insns_begin. */
5643 if (dbg_cnt (sched_insn
) == false)
5644 skip_insn
= next_nonnote_insn (nonscheduled_insns_begin
);
5646 skip_insn
= NULL_RTX
;
5648 while (i
< ready
.n_ready
)
5652 insn
= ready_remove (&ready
, i
);
5654 if (insn
!= skip_insn
)
5655 queue_insn (insn
, 1, "list truncated");
5658 ready_add (&ready
, skip_insn
, true);
5662 /* Now we can restore basic block notes and maintain precise cfg. */
5663 restore_bb_notes (*target_bb
);
5665 last_clock_var
= -1;
5669 gcc_assert (VEC_length (rtx
, scheduled_insns
) == 0);
5671 must_backtrack
= false;
5672 modulo_insns_scheduled
= 0;
5674 ls
.modulo_epilogue
= false;
5676 /* Loop until all the insns in BB are scheduled. */
5677 while ((*current_sched_info
->schedule_more_p
) ())
5681 start_clock_var
= clock_var
;
5685 advance_one_cycle ();
5687 /* Add to the ready list all pending insns that can be issued now.
5688 If there are no ready insns, increment clock until one
5689 is ready and add all pending insns at that point to the ready
5691 queue_to_ready (&ready
);
5693 gcc_assert (ready
.n_ready
);
5695 if (sched_verbose
>= 2)
5697 fprintf (sched_dump
, ";;\t\tReady list after queue_to_ready: ");
5698 debug_ready_list (&ready
);
5700 advance
-= clock_var
- start_clock_var
;
5702 while (advance
> 0);
5704 if (ls
.modulo_epilogue
)
5706 int stage
= clock_var
/ modulo_ii
;
5707 if (stage
> modulo_last_stage
* 2 + 2)
5709 if (sched_verbose
>= 2)
5710 fprintf (sched_dump
,
5711 ";;\t\tmodulo scheduled succeeded at II %d\n",
5717 else if (modulo_ii
> 0)
5719 int stage
= clock_var
/ modulo_ii
;
5720 if (stage
> modulo_max_stages
)
5722 if (sched_verbose
>= 2)
5723 fprintf (sched_dump
,
5724 ";;\t\tfailing schedule due to excessive stages\n");
5727 if (modulo_n_insns
== modulo_insns_scheduled
5728 && stage
> modulo_last_stage
)
5730 if (sched_verbose
>= 2)
5731 fprintf (sched_dump
,
5732 ";;\t\tfound kernel after %d stages, II %d\n",
5734 ls
.modulo_epilogue
= true;
5738 prune_ready_list (temp_state
, true, false, ls
.modulo_epilogue
);
5739 if (ready
.n_ready
== 0)
5744 ls
.first_cycle_insn_p
= true;
5745 ls
.shadows_only_p
= false;
5746 cycle_issued_insns
= 0;
5747 ls
.can_issue_more
= issue_rate
;
5754 if (sort_p
&& ready
.n_ready
> 0)
5756 /* Sort the ready list based on priority. This must be
5757 done every iteration through the loop, as schedule_insn
5758 may have readied additional insns that will not be
5759 sorted correctly. */
5760 ready_sort (&ready
);
5762 if (sched_verbose
>= 2)
5764 fprintf (sched_dump
, ";;\t\tReady list after ready_sort: ");
5765 debug_ready_list (&ready
);
5769 /* We don't want md sched reorder to even see debug isns, so put
5770 them out right away. */
5771 if (ready
.n_ready
&& DEBUG_INSN_P (ready_element (&ready
, 0))
5772 && (*current_sched_info
->schedule_more_p
) ())
5774 while (ready
.n_ready
&& DEBUG_INSN_P (ready_element (&ready
, 0)))
5776 rtx insn
= ready_remove_first (&ready
);
5777 gcc_assert (DEBUG_INSN_P (insn
));
5778 (*current_sched_info
->begin_schedule_ready
) (insn
);
5779 VEC_safe_push (rtx
, heap
, scheduled_insns
, insn
);
5780 last_scheduled_insn
= insn
;
5781 advance
= schedule_insn (insn
);
5782 gcc_assert (advance
== 0);
5783 if (ready
.n_ready
> 0)
5784 ready_sort (&ready
);
5788 if (ls
.first_cycle_insn_p
&& !ready
.n_ready
)
5791 resume_after_backtrack
:
5792 /* Allow the target to reorder the list, typically for
5793 better instruction bundling. */
5795 && (ready
.n_ready
== 0
5796 || !SCHED_GROUP_P (ready_element (&ready
, 0))))
5798 if (ls
.first_cycle_insn_p
&& targetm
.sched
.reorder
)
5800 = targetm
.sched
.reorder (sched_dump
, sched_verbose
,
5801 ready_lastpos (&ready
),
5802 &ready
.n_ready
, clock_var
);
5803 else if (!ls
.first_cycle_insn_p
&& targetm
.sched
.reorder2
)
5805 = targetm
.sched
.reorder2 (sched_dump
, sched_verbose
,
5807 ? ready_lastpos (&ready
) : NULL
,
5808 &ready
.n_ready
, clock_var
);
5811 restart_choose_ready
:
5812 if (sched_verbose
>= 2)
5814 fprintf (sched_dump
, ";;\tReady list (t = %3d): ",
5816 debug_ready_list (&ready
);
5817 if (sched_pressure
== SCHED_PRESSURE_WEIGHTED
)
5818 print_curr_reg_pressure ();
5821 if (ready
.n_ready
== 0
5822 && ls
.can_issue_more
5823 && reload_completed
)
5825 /* Allow scheduling insns directly from the queue in case
5826 there's nothing better to do (ready list is empty) but
5827 there are still vacant dispatch slots in the current cycle. */
5828 if (sched_verbose
>= 6)
5829 fprintf (sched_dump
,";;\t\tSecond chance\n");
5830 memcpy (temp_state
, curr_state
, dfa_state_size
);
5831 if (early_queue_to_ready (temp_state
, &ready
))
5832 ready_sort (&ready
);
5835 if (ready
.n_ready
== 0
5836 || !ls
.can_issue_more
5837 || state_dead_lock_p (curr_state
)
5838 || !(*current_sched_info
->schedule_more_p
) ())
5841 /* Select and remove the insn from the ready list. */
5847 res
= choose_ready (&ready
, ls
.first_cycle_insn_p
, &insn
);
5853 goto restart_choose_ready
;
5855 gcc_assert (insn
!= NULL_RTX
);
5858 insn
= ready_remove_first (&ready
);
5860 if (sched_pressure
!= SCHED_PRESSURE_NONE
5861 && INSN_TICK (insn
) > clock_var
)
5863 ready_add (&ready
, insn
, true);
5868 if (targetm
.sched
.dfa_new_cycle
5869 && targetm
.sched
.dfa_new_cycle (sched_dump
, sched_verbose
,
5870 insn
, last_clock_var
,
5871 clock_var
, &sort_p
))
5872 /* SORT_P is used by the target to override sorting
5873 of the ready list. This is needed when the target
5874 has modified its internal structures expecting that
5875 the insn will be issued next. As we need the insn
5876 to have the highest priority (so it will be returned by
5877 the ready_remove_first call above), we invoke
5878 ready_add (&ready, insn, true).
5879 But, still, there is one issue: INSN can be later
5880 discarded by scheduler's front end through
5881 current_sched_info->can_schedule_ready_p, hence, won't
5884 ready_add (&ready
, insn
, true);
5890 if (current_sched_info
->can_schedule_ready_p
5891 && ! (*current_sched_info
->can_schedule_ready_p
) (insn
))
5892 /* We normally get here only if we don't want to move
5893 insn from the split block. */
5895 TODO_SPEC (insn
) = HARD_DEP
;
5896 goto restart_choose_ready
;
5901 /* If this insn is the first part of a delay-slot pair, record a
5903 struct delay_pair
*delay_entry
;
5905 = (struct delay_pair
*)htab_find_with_hash (delay_htab
, insn
,
5906 htab_hash_pointer (insn
));
5909 save_backtrack_point (delay_entry
, ls
);
5910 if (sched_verbose
>= 2)
5911 fprintf (sched_dump
, ";;\t\tsaving backtrack point\n");
5915 /* DECISION is made. */
5917 if (modulo_ii
> 0 && INSN_UID (insn
) < modulo_iter0_max_uid
)
5919 modulo_insns_scheduled
++;
5920 modulo_last_stage
= clock_var
/ modulo_ii
;
5922 if (TODO_SPEC (insn
) & SPECULATIVE
)
5923 generate_recovery_code (insn
);
5925 if (targetm
.sched
.dispatch (NULL_RTX
, IS_DISPATCH_ON
))
5926 targetm
.sched
.dispatch_do (insn
, ADD_TO_DISPATCH_WINDOW
);
5928 /* Update counters, etc in the scheduler's front end. */
5929 (*current_sched_info
->begin_schedule_ready
) (insn
);
5930 VEC_safe_push (rtx
, heap
, scheduled_insns
, insn
);
5931 gcc_assert (NONDEBUG_INSN_P (insn
));
5932 last_nondebug_scheduled_insn
= last_scheduled_insn
= insn
;
5934 if (recog_memoized (insn
) >= 0)
5936 memcpy (temp_state
, curr_state
, dfa_state_size
);
5937 cost
= state_transition (curr_state
, insn
);
5938 if (sched_pressure
!= SCHED_PRESSURE_WEIGHTED
)
5939 gcc_assert (cost
< 0);
5940 if (memcmp (temp_state
, curr_state
, dfa_state_size
) != 0)
5941 cycle_issued_insns
++;
5945 asm_p
= (GET_CODE (PATTERN (insn
)) == ASM_INPUT
5946 || asm_noperands (PATTERN (insn
)) >= 0);
5948 if (targetm
.sched
.variable_issue
)
5950 targetm
.sched
.variable_issue (sched_dump
, sched_verbose
,
5951 insn
, ls
.can_issue_more
);
5952 /* A naked CLOBBER or USE generates no instruction, so do
5953 not count them against the issue rate. */
5954 else if (GET_CODE (PATTERN (insn
)) != USE
5955 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
5956 ls
.can_issue_more
--;
5957 advance
= schedule_insn (insn
);
5959 if (SHADOW_P (insn
))
5960 ls
.shadows_only_p
= true;
5962 /* After issuing an asm insn we should start a new cycle. */
5963 if (advance
== 0 && asm_p
)
5972 ls
.first_cycle_insn_p
= false;
5973 if (ready
.n_ready
> 0)
5974 prune_ready_list (temp_state
, false, ls
.shadows_only_p
,
5975 ls
.modulo_epilogue
);
5979 if (!must_backtrack
)
5980 for (i
= 0; i
< ready
.n_ready
; i
++)
5982 rtx insn
= ready_element (&ready
, i
);
5983 if (INSN_EXACT_TICK (insn
) == clock_var
)
5985 must_backtrack
= true;
5990 if (must_backtrack
&& modulo_ii
> 0)
5992 if (modulo_backtracks_left
== 0)
5994 modulo_backtracks_left
--;
5996 while (must_backtrack
)
5998 struct haifa_saved_data
*failed
;
6001 must_backtrack
= false;
6002 failed
= verify_shadows ();
6003 gcc_assert (failed
);
6005 failed_insn
= failed
->delay_pair
->i1
;
6006 toggle_cancelled_flags (false);
6007 unschedule_insns_until (failed_insn
);
6008 while (failed
!= backtrack_queue
)
6009 free_topmost_backtrack_point (true);
6010 restore_last_backtrack_point (&ls
);
6011 if (sched_verbose
>= 2)
6012 fprintf (sched_dump
, ";;\t\trewind to cycle %d\n", clock_var
);
6013 /* Delay by at least a cycle. This could cause additional
6015 queue_insn (failed_insn
, 1, "backtracked");
6019 if (ready
.n_ready
> 0)
6020 goto resume_after_backtrack
;
6023 if (clock_var
== 0 && ls
.first_cycle_insn_p
)
6030 if (ls
.modulo_epilogue
)
6035 /* Once again, debug insn suckiness: they can be on the ready list
6036 even if they have unresolved dependencies. To make our view
6037 of the world consistent, remove such "ready" insns. */
6038 restart_debug_insn_loop
:
6039 for (i
= ready
.n_ready
- 1; i
>= 0; i
--)
6043 x
= ready_element (&ready
, i
);
6044 if (DEPS_LIST_FIRST (INSN_HARD_BACK_DEPS (x
)) != NULL
6045 || DEPS_LIST_FIRST (INSN_SPEC_BACK_DEPS (x
)) != NULL
)
6047 ready_remove (&ready
, i
);
6048 goto restart_debug_insn_loop
;
6051 for (i
= ready
.n_ready
- 1; i
>= 0; i
--)
6055 x
= ready_element (&ready
, i
);
6056 resolve_dependencies (x
);
6058 for (i
= 0; i
<= max_insn_queue_index
; i
++)
6061 while ((link
= insn_queue
[i
]) != NULL
)
6063 rtx x
= XEXP (link
, 0);
6064 insn_queue
[i
] = XEXP (link
, 1);
6065 QUEUE_INDEX (x
) = QUEUE_NOWHERE
;
6066 free_INSN_LIST_node (link
);
6067 resolve_dependencies (x
);
6075 fprintf (sched_dump
, ";;\tReady list (final): ");
6076 debug_ready_list (&ready
);
6079 if (modulo_ii
== 0 && current_sched_info
->queue_must_finish_empty
)
6080 /* Sanity check -- queue must be empty now. Meaningless if region has
6082 gcc_assert (!q_size
&& !ready
.n_ready
&& !ready
.n_debug
);
6083 else if (modulo_ii
== 0)
6085 /* We must maintain QUEUE_INDEX between blocks in region. */
6086 for (i
= ready
.n_ready
- 1; i
>= 0; i
--)
6090 x
= ready_element (&ready
, i
);
6091 QUEUE_INDEX (x
) = QUEUE_NOWHERE
;
6092 TODO_SPEC (x
) = HARD_DEP
;
6096 for (i
= 0; i
<= max_insn_queue_index
; i
++)
6099 for (link
= insn_queue
[i
]; link
; link
= XEXP (link
, 1))
6104 QUEUE_INDEX (x
) = QUEUE_NOWHERE
;
6105 TODO_SPEC (x
) = HARD_DEP
;
6107 free_INSN_LIST_list (&insn_queue
[i
]);
6111 if (sched_pressure
== SCHED_PRESSURE_MODEL
)
6112 model_end_schedule ();
6116 commit_schedule (prev_head
, tail
, target_bb
);
6118 fprintf (sched_dump
, ";; total time = %d\n", clock_var
);
6121 last_scheduled_insn
= tail
;
6123 VEC_truncate (rtx
, scheduled_insns
, 0);
6125 if (!current_sched_info
->queue_must_finish_empty
6126 || haifa_recovery_bb_recently_added_p
)
6128 /* INSN_TICK (minimum clock tick at which the insn becomes
6129 ready) may be not correct for the insn in the subsequent
6130 blocks of the region. We should use a correct value of
6131 `clock_var' or modify INSN_TICK. It is better to keep
6132 clock_var value equal to 0 at the start of a basic block.
6133 Therefore we modify INSN_TICK here. */
6134 fix_inter_tick (NEXT_INSN (prev_head
), last_scheduled_insn
);
6137 if (targetm
.sched
.finish
)
6139 targetm
.sched
.finish (sched_dump
, sched_verbose
);
6140 /* Target might have added some instructions to the scheduled block
6141 in its md_finish () hook. These new insns don't have any data
6142 initialized and to identify them we extend h_i_d so that they'll
6144 sched_extend_luids ();
6148 fprintf (sched_dump
, ";; new head = %d\n;; new tail = %d\n\n",
6149 INSN_UID (head
), INSN_UID (tail
));
6151 /* Update head/tail boundaries. */
6152 head
= NEXT_INSN (prev_head
);
6153 tail
= last_scheduled_insn
;
6155 head
= restore_other_notes (head
, NULL
);
6157 current_sched_info
->head
= head
;
6158 current_sched_info
->tail
= tail
;
6160 free_backtrack_queue ();
6165 /* Set_priorities: compute priority of each insn in the block. */
6168 set_priorities (rtx head
, rtx tail
)
6172 int sched_max_insns_priority
=
6173 current_sched_info
->sched_max_insns_priority
;
6176 if (head
== tail
&& ! INSN_P (head
))
6181 prev_head
= PREV_INSN (head
);
6182 for (insn
= tail
; insn
!= prev_head
; insn
= PREV_INSN (insn
))
6188 (void) priority (insn
);
6190 gcc_assert (INSN_PRIORITY_KNOWN (insn
));
6192 sched_max_insns_priority
= MAX (sched_max_insns_priority
,
6193 INSN_PRIORITY (insn
));
6196 current_sched_info
->sched_max_insns_priority
= sched_max_insns_priority
;
6201 /* Set dump and sched_verbose for the desired debugging output. If no
6202 dump-file was specified, but -fsched-verbose=N (any N), print to stderr.
6203 For -fsched-verbose=N, N>=10, print everything to stderr. */
6205 setup_sched_dump (void)
6207 sched_verbose
= sched_verbose_param
;
6208 if (sched_verbose_param
== 0 && dump_file
)
6210 sched_dump
= ((sched_verbose_param
>= 10 || !dump_file
)
6211 ? stderr
: dump_file
);
6214 /* Initialize some global state for the scheduler. This function works
6215 with the common data shared between all the schedulers. It is called
6216 from the scheduler specific initialization routine. */
6221 /* Disable speculative loads in their presence if cc0 defined. */
6223 flag_schedule_speculative_load
= 0;
6226 if (targetm
.sched
.dispatch (NULL_RTX
, IS_DISPATCH_ON
))
6227 targetm
.sched
.dispatch_do (NULL_RTX
, DISPATCH_INIT
);
6229 if (flag_sched_pressure
6230 && !reload_completed
6231 && common_sched_info
->sched_pass_id
== SCHED_RGN_PASS
)
6232 sched_pressure
= flag_sched_pressure_algorithm
;
6234 sched_pressure
= SCHED_PRESSURE_NONE
;
6236 if (sched_pressure
!= SCHED_PRESSURE_NONE
)
6237 ira_setup_eliminable_regset ();
6239 /* Initialize SPEC_INFO. */
6240 if (targetm
.sched
.set_sched_flags
)
6242 spec_info
= &spec_info_var
;
6243 targetm
.sched
.set_sched_flags (spec_info
);
6245 if (spec_info
->mask
!= 0)
6247 spec_info
->data_weakness_cutoff
=
6248 (PARAM_VALUE (PARAM_SCHED_SPEC_PROB_CUTOFF
) * MAX_DEP_WEAK
) / 100;
6249 spec_info
->control_weakness_cutoff
=
6250 (PARAM_VALUE (PARAM_SCHED_SPEC_PROB_CUTOFF
)
6251 * REG_BR_PROB_BASE
) / 100;
6254 /* So we won't read anything accidentally. */
6259 /* So we won't read anything accidentally. */
6262 /* Initialize issue_rate. */
6263 if (targetm
.sched
.issue_rate
)
6264 issue_rate
= targetm
.sched
.issue_rate ();
6268 if (cached_issue_rate
!= issue_rate
)
6270 cached_issue_rate
= issue_rate
;
6271 /* To invalidate max_lookahead_tries: */
6272 cached_first_cycle_multipass_dfa_lookahead
= 0;
6275 if (targetm
.sched
.first_cycle_multipass_dfa_lookahead
)
6276 dfa_lookahead
= targetm
.sched
.first_cycle_multipass_dfa_lookahead ();
6280 if (targetm
.sched
.init_dfa_pre_cycle_insn
)
6281 targetm
.sched
.init_dfa_pre_cycle_insn ();
6283 if (targetm
.sched
.init_dfa_post_cycle_insn
)
6284 targetm
.sched
.init_dfa_post_cycle_insn ();
6287 dfa_state_size
= state_size ();
6289 init_alias_analysis ();
6292 df_set_flags (DF_LR_RUN_DCE
);
6293 df_note_add_problem ();
6295 /* More problems needed for interloop dep calculation in SMS. */
6296 if (common_sched_info
->sched_pass_id
== SCHED_SMS_PASS
)
6298 df_rd_add_problem ();
6299 df_chain_add_problem (DF_DU_CHAIN
+ DF_UD_CHAIN
);
6304 /* Do not run DCE after reload, as this can kill nops inserted
6306 if (reload_completed
)
6307 df_clear_flags (DF_LR_RUN_DCE
);
6309 regstat_compute_calls_crossed ();
6311 if (targetm
.sched
.init_global
)
6312 targetm
.sched
.init_global (sched_dump
, sched_verbose
, get_max_uid () + 1);
6314 if (sched_pressure
!= SCHED_PRESSURE_NONE
)
6316 int i
, max_regno
= max_reg_num ();
6318 if (sched_dump
!= NULL
)
6319 /* We need info about pseudos for rtl dumps about pseudo
6320 classes and costs. */
6321 regstat_init_n_sets_and_refs ();
6322 ira_set_pseudo_classes (sched_verbose
? sched_dump
: NULL
);
6323 sched_regno_pressure_class
6324 = (enum reg_class
*) xmalloc (max_regno
* sizeof (enum reg_class
));
6325 for (i
= 0; i
< max_regno
; i
++)
6326 sched_regno_pressure_class
[i
]
6327 = (i
< FIRST_PSEUDO_REGISTER
6328 ? ira_pressure_class_translate
[REGNO_REG_CLASS (i
)]
6329 : ira_pressure_class_translate
[reg_allocno_class (i
)]);
6330 curr_reg_live
= BITMAP_ALLOC (NULL
);
6331 if (sched_pressure
== SCHED_PRESSURE_WEIGHTED
)
6333 saved_reg_live
= BITMAP_ALLOC (NULL
);
6334 region_ref_regs
= BITMAP_ALLOC (NULL
);
6338 curr_state
= xmalloc (dfa_state_size
);
6341 static void haifa_init_only_bb (basic_block
, basic_block
);
6343 /* Initialize data structures specific to the Haifa scheduler. */
6345 haifa_sched_init (void)
6347 setup_sched_dump ();
6350 scheduled_insns
= VEC_alloc (rtx
, heap
, 0);
6352 if (spec_info
!= NULL
)
6354 sched_deps_info
->use_deps_list
= 1;
6355 sched_deps_info
->generate_spec_deps
= 1;
6358 /* Initialize luids, dependency caches, target and h_i_d for the
6361 bb_vec_t bbs
= VEC_alloc (basic_block
, heap
, n_basic_blocks
);
6367 VEC_quick_push (basic_block
, bbs
, bb
);
6368 sched_init_luids (bbs
);
6369 sched_deps_init (true);
6370 sched_extend_target ();
6371 haifa_init_h_i_d (bbs
);
6373 VEC_free (basic_block
, heap
, bbs
);
6376 sched_init_only_bb
= haifa_init_only_bb
;
6377 sched_split_block
= sched_split_block_1
;
6378 sched_create_empty_bb
= sched_create_empty_bb_1
;
6379 haifa_recovery_bb_ever_added_p
= false;
6381 nr_begin_data
= nr_begin_control
= nr_be_in_data
= nr_be_in_control
= 0;
6382 before_recovery
= 0;
6388 /* Finish work with the data specific to the Haifa scheduler. */
6390 haifa_sched_finish (void)
6392 sched_create_empty_bb
= NULL
;
6393 sched_split_block
= NULL
;
6394 sched_init_only_bb
= NULL
;
6396 if (spec_info
&& spec_info
->dump
)
6398 char c
= reload_completed
? 'a' : 'b';
6400 fprintf (spec_info
->dump
,
6401 ";; %s:\n", current_function_name ());
6403 fprintf (spec_info
->dump
,
6404 ";; Procedure %cr-begin-data-spec motions == %d\n",
6406 fprintf (spec_info
->dump
,
6407 ";; Procedure %cr-be-in-data-spec motions == %d\n",
6409 fprintf (spec_info
->dump
,
6410 ";; Procedure %cr-begin-control-spec motions == %d\n",
6411 c
, nr_begin_control
);
6412 fprintf (spec_info
->dump
,
6413 ";; Procedure %cr-be-in-control-spec motions == %d\n",
6414 c
, nr_be_in_control
);
6417 VEC_free (rtx
, heap
, scheduled_insns
);
6419 /* Finalize h_i_d, dependency caches, and luids for the whole
6420 function. Target will be finalized in md_global_finish (). */
6421 sched_deps_finish ();
6422 sched_finish_luids ();
6423 current_sched_info
= NULL
;
6427 /* Free global data used during insn scheduling. This function works with
6428 the common data shared between the schedulers. */
6433 haifa_finish_h_i_d ();
6434 if (sched_pressure
!= SCHED_PRESSURE_NONE
)
6436 if (regstat_n_sets_and_refs
!= NULL
)
6437 regstat_free_n_sets_and_refs ();
6438 if (sched_pressure
== SCHED_PRESSURE_WEIGHTED
)
6440 BITMAP_FREE (region_ref_regs
);
6441 BITMAP_FREE (saved_reg_live
);
6443 BITMAP_FREE (curr_reg_live
);
6444 free (sched_regno_pressure_class
);
6448 if (targetm
.sched
.finish_global
)
6449 targetm
.sched
.finish_global (sched_dump
, sched_verbose
);
6451 end_alias_analysis ();
6453 regstat_free_calls_crossed ();
6458 /* Free all delay_pair structures that were recorded. */
6460 free_delay_pairs (void)
6464 htab_empty (delay_htab
);
6465 htab_empty (delay_htab_i2
);
6469 /* Fix INSN_TICKs of the instructions in the current block as well as
6470 INSN_TICKs of their dependents.
6471 HEAD and TAIL are the begin and the end of the current scheduled block. */
6473 fix_inter_tick (rtx head
, rtx tail
)
6475 /* Set of instructions with corrected INSN_TICK. */
6476 bitmap_head processed
;
6477 /* ??? It is doubtful if we should assume that cycle advance happens on
6478 basic block boundaries. Basically insns that are unconditionally ready
6479 on the start of the block are more preferable then those which have
6480 a one cycle dependency over insn from the previous block. */
6481 int next_clock
= clock_var
+ 1;
6483 bitmap_initialize (&processed
, 0);
6485 /* Iterates over scheduled instructions and fix their INSN_TICKs and
6486 INSN_TICKs of dependent instructions, so that INSN_TICKs are consistent
6487 across different blocks. */
6488 for (tail
= NEXT_INSN (tail
); head
!= tail
; head
= NEXT_INSN (head
))
6493 sd_iterator_def sd_it
;
6496 tick
= INSN_TICK (head
);
6497 gcc_assert (tick
>= MIN_TICK
);
6499 /* Fix INSN_TICK of instruction from just scheduled block. */
6500 if (bitmap_set_bit (&processed
, INSN_LUID (head
)))
6504 if (tick
< MIN_TICK
)
6507 INSN_TICK (head
) = tick
;
6510 FOR_EACH_DEP (head
, SD_LIST_RES_FORW
, sd_it
, dep
)
6514 next
= DEP_CON (dep
);
6515 tick
= INSN_TICK (next
);
6517 if (tick
!= INVALID_TICK
6518 /* If NEXT has its INSN_TICK calculated, fix it.
6519 If not - it will be properly calculated from
6520 scratch later in fix_tick_ready. */
6521 && bitmap_set_bit (&processed
, INSN_LUID (next
)))
6525 if (tick
< MIN_TICK
)
6528 if (tick
> INTER_TICK (next
))
6529 INTER_TICK (next
) = tick
;
6531 tick
= INTER_TICK (next
);
6533 INSN_TICK (next
) = tick
;
6538 bitmap_clear (&processed
);
6541 /* Check if NEXT is ready to be added to the ready or queue list.
6542 If "yes", add it to the proper list.
6544 -1 - is not ready yet,
6545 0 - added to the ready list,
6546 0 < N - queued for N cycles. */
6548 try_ready (rtx next
)
6550 ds_t old_ts
, new_ts
;
6552 old_ts
= TODO_SPEC (next
);
6554 gcc_assert (!(old_ts
& ~(SPECULATIVE
| HARD_DEP
| DEP_CONTROL
))
6555 && ((old_ts
& HARD_DEP
)
6556 || (old_ts
& SPECULATIVE
)
6557 || (old_ts
& DEP_CONTROL
)));
6559 new_ts
= recompute_todo_spec (next
);
6561 if (new_ts
& HARD_DEP
)
6562 gcc_assert (new_ts
== old_ts
6563 && QUEUE_INDEX (next
) == QUEUE_NOWHERE
);
6564 else if (current_sched_info
->new_ready
)
6565 new_ts
= current_sched_info
->new_ready (next
, new_ts
);
6567 /* * if !(old_ts & SPECULATIVE) (e.g. HARD_DEP or 0), then insn might
6568 have its original pattern or changed (speculative) one. This is due
6569 to changing ebb in region scheduling.
6570 * But if (old_ts & SPECULATIVE), then we are pretty sure that insn
6571 has speculative pattern.
6573 We can't assert (!(new_ts & HARD_DEP) || new_ts == old_ts) here because
6574 control-speculative NEXT could have been discarded by sched-rgn.c
6575 (the same case as when discarded by can_schedule_ready_p ()). */
6577 if ((new_ts
& SPECULATIVE
)
6578 /* If (old_ts == new_ts), then (old_ts & SPECULATIVE) and we don't
6579 need to change anything. */
6580 && new_ts
!= old_ts
)
6585 gcc_assert ((new_ts
& SPECULATIVE
) && !(new_ts
& ~SPECULATIVE
));
6587 res
= haifa_speculate_insn (next
, new_ts
, &new_pat
);
6592 /* It would be nice to change DEP_STATUS of all dependences,
6593 which have ((DEP_STATUS & SPECULATIVE) == new_ts) to HARD_DEP,
6594 so we won't reanalyze anything. */
6599 /* We follow the rule, that every speculative insn
6600 has non-null ORIG_PAT. */
6601 if (!ORIG_PAT (next
))
6602 ORIG_PAT (next
) = PATTERN (next
);
6606 if (!ORIG_PAT (next
))
6607 /* If we gonna to overwrite the original pattern of insn,
6609 ORIG_PAT (next
) = PATTERN (next
);
6611 res
= haifa_change_pattern (next
, new_pat
);
6620 /* We need to restore pattern only if (new_ts == 0), because otherwise it is
6621 either correct (new_ts & SPECULATIVE),
6622 or we simply don't care (new_ts & HARD_DEP). */
6624 gcc_assert (!ORIG_PAT (next
)
6625 || !IS_SPECULATION_BRANCHY_CHECK_P (next
));
6627 TODO_SPEC (next
) = new_ts
;
6629 if (new_ts
& HARD_DEP
)
6631 /* We can't assert (QUEUE_INDEX (next) == QUEUE_NOWHERE) here because
6632 control-speculative NEXT could have been discarded by sched-rgn.c
6633 (the same case as when discarded by can_schedule_ready_p ()). */
6634 /*gcc_assert (QUEUE_INDEX (next) == QUEUE_NOWHERE);*/
6636 change_queue_index (next
, QUEUE_NOWHERE
);
6640 else if (!(new_ts
& BEGIN_SPEC
)
6641 && ORIG_PAT (next
) && PREDICATED_PAT (next
) == NULL_RTX
6642 && !IS_SPECULATION_CHECK_P (next
))
6643 /* We should change pattern of every previously speculative
6644 instruction - and we determine if NEXT was speculative by using
6645 ORIG_PAT field. Except one case - speculation checks have ORIG_PAT
6646 pat too, so skip them. */
6648 bool success
= haifa_change_pattern (next
, ORIG_PAT (next
));
6649 gcc_assert (success
);
6650 ORIG_PAT (next
) = 0;
6653 if (sched_verbose
>= 2)
6655 fprintf (sched_dump
, ";;\t\tdependencies resolved: insn %s",
6656 (*current_sched_info
->print_insn
) (next
, 0));
6658 if (spec_info
&& spec_info
->dump
)
6660 if (new_ts
& BEGIN_DATA
)
6661 fprintf (spec_info
->dump
, "; data-spec;");
6662 if (new_ts
& BEGIN_CONTROL
)
6663 fprintf (spec_info
->dump
, "; control-spec;");
6664 if (new_ts
& BE_IN_CONTROL
)
6665 fprintf (spec_info
->dump
, "; in-control-spec;");
6667 if (TODO_SPEC (next
) & DEP_CONTROL
)
6668 fprintf (sched_dump
, " predicated");
6669 fprintf (sched_dump
, "\n");
6672 adjust_priority (next
);
6674 return fix_tick_ready (next
);
6677 /* Calculate INSN_TICK of NEXT and add it to either ready or queue list. */
6679 fix_tick_ready (rtx next
)
6683 if (!DEBUG_INSN_P (next
) && !sd_lists_empty_p (next
, SD_LIST_RES_BACK
))
6686 sd_iterator_def sd_it
;
6689 tick
= INSN_TICK (next
);
6690 /* if tick is not equal to INVALID_TICK, then update
6691 INSN_TICK of NEXT with the most recent resolved dependence
6692 cost. Otherwise, recalculate from scratch. */
6693 full_p
= (tick
== INVALID_TICK
);
6695 FOR_EACH_DEP (next
, SD_LIST_RES_BACK
, sd_it
, dep
)
6697 rtx pro
= DEP_PRO (dep
);
6700 gcc_assert (INSN_TICK (pro
) >= MIN_TICK
);
6702 tick1
= INSN_TICK (pro
) + dep_cost (dep
);
6713 INSN_TICK (next
) = tick
;
6715 delay
= tick
- clock_var
;
6716 if (delay
<= 0 || sched_pressure
!= SCHED_PRESSURE_NONE
)
6717 delay
= QUEUE_READY
;
6719 change_queue_index (next
, delay
);
6724 /* Move NEXT to the proper queue list with (DELAY >= 1),
6725 or add it to the ready list (DELAY == QUEUE_READY),
6726 or remove it from ready and queue lists at all (DELAY == QUEUE_NOWHERE). */
6728 change_queue_index (rtx next
, int delay
)
6730 int i
= QUEUE_INDEX (next
);
6732 gcc_assert (QUEUE_NOWHERE
<= delay
&& delay
<= max_insn_queue_index
6734 gcc_assert (i
!= QUEUE_SCHEDULED
);
6736 if ((delay
> 0 && NEXT_Q_AFTER (q_ptr
, delay
) == i
)
6737 || (delay
< 0 && delay
== i
))
6738 /* We have nothing to do. */
6741 /* Remove NEXT from wherever it is now. */
6742 if (i
== QUEUE_READY
)
6743 ready_remove_insn (next
);
6745 queue_remove (next
);
6747 /* Add it to the proper place. */
6748 if (delay
== QUEUE_READY
)
6749 ready_add (readyp
, next
, false);
6750 else if (delay
>= 1)
6751 queue_insn (next
, delay
, "change queue index");
6753 if (sched_verbose
>= 2)
6755 fprintf (sched_dump
, ";;\t\ttick updated: insn %s",
6756 (*current_sched_info
->print_insn
) (next
, 0));
6758 if (delay
== QUEUE_READY
)
6759 fprintf (sched_dump
, " into ready\n");
6760 else if (delay
>= 1)
6761 fprintf (sched_dump
, " into queue with cost=%d\n", delay
);
6763 fprintf (sched_dump
, " removed from ready or queue lists\n");
6767 static int sched_ready_n_insns
= -1;
6769 /* Initialize per region data structures. */
6771 sched_extend_ready_list (int new_sched_ready_n_insns
)
6775 if (sched_ready_n_insns
== -1)
6776 /* At the first call we need to initialize one more choice_stack
6780 sched_ready_n_insns
= 0;
6781 VEC_reserve (rtx
, heap
, scheduled_insns
, new_sched_ready_n_insns
);
6784 i
= sched_ready_n_insns
+ 1;
6786 ready
.veclen
= new_sched_ready_n_insns
+ issue_rate
;
6787 ready
.vec
= XRESIZEVEC (rtx
, ready
.vec
, ready
.veclen
);
6789 gcc_assert (new_sched_ready_n_insns
>= sched_ready_n_insns
);
6791 ready_try
= (char *) xrecalloc (ready_try
, new_sched_ready_n_insns
,
6792 sched_ready_n_insns
, sizeof (*ready_try
));
6794 /* We allocate +1 element to save initial state in the choice_stack[0]
6796 choice_stack
= XRESIZEVEC (struct choice_entry
, choice_stack
,
6797 new_sched_ready_n_insns
+ 1);
6799 for (; i
<= new_sched_ready_n_insns
; i
++)
6801 choice_stack
[i
].state
= xmalloc (dfa_state_size
);
6803 if (targetm
.sched
.first_cycle_multipass_init
)
6804 targetm
.sched
.first_cycle_multipass_init (&(choice_stack
[i
]
6808 sched_ready_n_insns
= new_sched_ready_n_insns
;
6811 /* Free per region data structures. */
6813 sched_finish_ready_list (void)
6824 for (i
= 0; i
<= sched_ready_n_insns
; i
++)
6826 if (targetm
.sched
.first_cycle_multipass_fini
)
6827 targetm
.sched
.first_cycle_multipass_fini (&(choice_stack
[i
]
6830 free (choice_stack
[i
].state
);
6832 free (choice_stack
);
6833 choice_stack
= NULL
;
6835 sched_ready_n_insns
= -1;
6839 haifa_luid_for_non_insn (rtx x
)
6841 gcc_assert (NOTE_P (x
) || LABEL_P (x
));
6846 /* Generates recovery code for INSN. */
6848 generate_recovery_code (rtx insn
)
6850 if (TODO_SPEC (insn
) & BEGIN_SPEC
)
6851 begin_speculative_block (insn
);
6853 /* Here we have insn with no dependencies to
6854 instructions other then CHECK_SPEC ones. */
6856 if (TODO_SPEC (insn
) & BE_IN_SPEC
)
6857 add_to_speculative_block (insn
);
6861 Tries to add speculative dependencies of type FS between instructions
6862 in deps_list L and TWIN. */
6864 process_insn_forw_deps_be_in_spec (rtx insn
, rtx twin
, ds_t fs
)
6866 sd_iterator_def sd_it
;
6869 FOR_EACH_DEP (insn
, SD_LIST_FORW
, sd_it
, dep
)
6874 consumer
= DEP_CON (dep
);
6876 ds
= DEP_STATUS (dep
);
6878 if (/* If we want to create speculative dep. */
6880 /* And we can do that because this is a true dep. */
6881 && (ds
& DEP_TYPES
) == DEP_TRUE
)
6883 gcc_assert (!(ds
& BE_IN_SPEC
));
6885 if (/* If this dep can be overcome with 'begin speculation'. */
6887 /* Then we have a choice: keep the dep 'begin speculative'
6888 or transform it into 'be in speculative'. */
6890 if (/* In try_ready we assert that if insn once became ready
6891 it can be removed from the ready (or queue) list only
6892 due to backend decision. Hence we can't let the
6893 probability of the speculative dep to decrease. */
6894 ds_weak (ds
) <= ds_weak (fs
))
6898 new_ds
= (ds
& ~BEGIN_SPEC
) | fs
;
6900 if (/* consumer can 'be in speculative'. */
6901 sched_insn_is_legitimate_for_speculation_p (consumer
,
6903 /* Transform it to be in speculative. */
6908 /* Mark the dep as 'be in speculative'. */
6913 dep_def _new_dep
, *new_dep
= &_new_dep
;
6915 init_dep_1 (new_dep
, twin
, consumer
, DEP_TYPE (dep
), ds
);
6916 sd_add_dep (new_dep
, false);
6921 /* Generates recovery code for BEGIN speculative INSN. */
6923 begin_speculative_block (rtx insn
)
6925 if (TODO_SPEC (insn
) & BEGIN_DATA
)
6927 if (TODO_SPEC (insn
) & BEGIN_CONTROL
)
6930 create_check_block_twin (insn
, false);
6932 TODO_SPEC (insn
) &= ~BEGIN_SPEC
;
6935 static void haifa_init_insn (rtx
);
6937 /* Generates recovery code for BE_IN speculative INSN. */
6939 add_to_speculative_block (rtx insn
)
6942 sd_iterator_def sd_it
;
6945 rtx_vec_t priorities_roots
;
6947 ts
= TODO_SPEC (insn
);
6948 gcc_assert (!(ts
& ~BE_IN_SPEC
));
6950 if (ts
& BE_IN_DATA
)
6952 if (ts
& BE_IN_CONTROL
)
6955 TODO_SPEC (insn
) &= ~BE_IN_SPEC
;
6956 gcc_assert (!TODO_SPEC (insn
));
6958 DONE_SPEC (insn
) |= ts
;
6960 /* First we convert all simple checks to branchy. */
6961 for (sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
6962 sd_iterator_cond (&sd_it
, &dep
);)
6964 rtx check
= DEP_PRO (dep
);
6966 if (IS_SPECULATION_SIMPLE_CHECK_P (check
))
6968 create_check_block_twin (check
, true);
6970 /* Restart search. */
6971 sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
6974 /* Continue search. */
6975 sd_iterator_next (&sd_it
);
6978 priorities_roots
= NULL
;
6979 clear_priorities (insn
, &priorities_roots
);
6986 /* Get the first backward dependency of INSN. */
6987 sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
6988 if (!sd_iterator_cond (&sd_it
, &dep
))
6989 /* INSN has no backward dependencies left. */
6992 gcc_assert ((DEP_STATUS (dep
) & BEGIN_SPEC
) == 0
6993 && (DEP_STATUS (dep
) & BE_IN_SPEC
) != 0
6994 && (DEP_STATUS (dep
) & DEP_TYPES
) == DEP_TRUE
);
6996 check
= DEP_PRO (dep
);
6998 gcc_assert (!IS_SPECULATION_CHECK_P (check
) && !ORIG_PAT (check
)
6999 && QUEUE_INDEX (check
) == QUEUE_NOWHERE
);
7001 rec
= BLOCK_FOR_INSN (check
);
7003 twin
= emit_insn_before (copy_insn (PATTERN (insn
)), BB_END (rec
));
7004 haifa_init_insn (twin
);
7006 sd_copy_back_deps (twin
, insn
, true);
7008 if (sched_verbose
&& spec_info
->dump
)
7009 /* INSN_BB (insn) isn't determined for twin insns yet.
7010 So we can't use current_sched_info->print_insn. */
7011 fprintf (spec_info
->dump
, ";;\t\tGenerated twin insn : %d/rec%d\n",
7012 INSN_UID (twin
), rec
->index
);
7014 twins
= alloc_INSN_LIST (twin
, twins
);
7016 /* Add dependences between TWIN and all appropriate
7017 instructions from REC. */
7018 FOR_EACH_DEP (insn
, SD_LIST_SPEC_BACK
, sd_it
, dep
)
7020 rtx pro
= DEP_PRO (dep
);
7022 gcc_assert (DEP_TYPE (dep
) == REG_DEP_TRUE
);
7024 /* INSN might have dependencies from the instructions from
7025 several recovery blocks. At this iteration we process those
7026 producers that reside in REC. */
7027 if (BLOCK_FOR_INSN (pro
) == rec
)
7029 dep_def _new_dep
, *new_dep
= &_new_dep
;
7031 init_dep (new_dep
, pro
, twin
, REG_DEP_TRUE
);
7032 sd_add_dep (new_dep
, false);
7036 process_insn_forw_deps_be_in_spec (insn
, twin
, ts
);
7038 /* Remove all dependencies between INSN and insns in REC. */
7039 for (sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
7040 sd_iterator_cond (&sd_it
, &dep
);)
7042 rtx pro
= DEP_PRO (dep
);
7044 if (BLOCK_FOR_INSN (pro
) == rec
)
7045 sd_delete_dep (sd_it
);
7047 sd_iterator_next (&sd_it
);
7051 /* We couldn't have added the dependencies between INSN and TWINS earlier
7052 because that would make TWINS appear in the INSN_BACK_DEPS (INSN). */
7057 twin
= XEXP (twins
, 0);
7060 dep_def _new_dep
, *new_dep
= &_new_dep
;
7062 init_dep (new_dep
, insn
, twin
, REG_DEP_OUTPUT
);
7063 sd_add_dep (new_dep
, false);
7066 twin
= XEXP (twins
, 1);
7067 free_INSN_LIST_node (twins
);
7071 calc_priorities (priorities_roots
);
7072 VEC_free (rtx
, heap
, priorities_roots
);
7075 /* Extends and fills with zeros (only the new part) array pointed to by P. */
7077 xrecalloc (void *p
, size_t new_nmemb
, size_t old_nmemb
, size_t size
)
7079 gcc_assert (new_nmemb
>= old_nmemb
);
7080 p
= XRESIZEVAR (void, p
, new_nmemb
* size
);
7081 memset (((char *) p
) + old_nmemb
* size
, 0, (new_nmemb
- old_nmemb
) * size
);
7086 Find fallthru edge from PRED. */
7088 find_fallthru_edge_from (basic_block pred
)
7093 succ
= pred
->next_bb
;
7094 gcc_assert (succ
->prev_bb
== pred
);
7096 if (EDGE_COUNT (pred
->succs
) <= EDGE_COUNT (succ
->preds
))
7098 e
= find_fallthru_edge (pred
->succs
);
7102 gcc_assert (e
->dest
== succ
);
7108 e
= find_fallthru_edge (succ
->preds
);
7112 gcc_assert (e
->src
== pred
);
7120 /* Extend per basic block data structures. */
7122 sched_extend_bb (void)
7126 /* The following is done to keep current_sched_info->next_tail non null. */
7127 insn
= BB_END (EXIT_BLOCK_PTR
->prev_bb
);
7128 if (NEXT_INSN (insn
) == 0
7131 /* Don't emit a NOTE if it would end up before a BARRIER. */
7132 && !BARRIER_P (NEXT_INSN (insn
))))
7134 rtx note
= emit_note_after (NOTE_INSN_DELETED
, insn
);
7135 /* Make insn appear outside BB. */
7136 set_block_for_insn (note
, NULL
);
7137 BB_END (EXIT_BLOCK_PTR
->prev_bb
) = insn
;
7141 /* Init per basic block data structures. */
7143 sched_init_bbs (void)
7148 /* Initialize BEFORE_RECOVERY variable. */
7150 init_before_recovery (basic_block
*before_recovery_ptr
)
7155 last
= EXIT_BLOCK_PTR
->prev_bb
;
7156 e
= find_fallthru_edge_from (last
);
7160 /* We create two basic blocks:
7161 1. Single instruction block is inserted right after E->SRC
7163 2. Empty block right before EXIT_BLOCK.
7164 Between these two blocks recovery blocks will be emitted. */
7166 basic_block single
, empty
;
7169 /* If the fallthrough edge to exit we've found is from the block we've
7170 created before, don't do anything more. */
7171 if (last
== after_recovery
)
7174 adding_bb_to_current_region_p
= false;
7176 single
= sched_create_empty_bb (last
);
7177 empty
= sched_create_empty_bb (single
);
7179 /* Add new blocks to the root loop. */
7180 if (current_loops
!= NULL
)
7182 add_bb_to_loop (single
, VEC_index (loop_p
, current_loops
->larray
, 0));
7183 add_bb_to_loop (empty
, VEC_index (loop_p
, current_loops
->larray
, 0));
7186 single
->count
= last
->count
;
7187 empty
->count
= last
->count
;
7188 single
->frequency
= last
->frequency
;
7189 empty
->frequency
= last
->frequency
;
7190 BB_COPY_PARTITION (single
, last
);
7191 BB_COPY_PARTITION (empty
, last
);
7193 redirect_edge_succ (e
, single
);
7194 make_single_succ_edge (single
, empty
, 0);
7195 make_single_succ_edge (empty
, EXIT_BLOCK_PTR
,
7196 EDGE_FALLTHRU
| EDGE_CAN_FALLTHRU
);
7198 label
= block_label (empty
);
7199 x
= emit_jump_insn_after (gen_jump (label
), BB_END (single
));
7200 JUMP_LABEL (x
) = label
;
7201 LABEL_NUSES (label
)++;
7202 haifa_init_insn (x
);
7204 emit_barrier_after (x
);
7206 sched_init_only_bb (empty
, NULL
);
7207 sched_init_only_bb (single
, NULL
);
7210 adding_bb_to_current_region_p
= true;
7211 before_recovery
= single
;
7212 after_recovery
= empty
;
7214 if (before_recovery_ptr
)
7215 *before_recovery_ptr
= before_recovery
;
7217 if (sched_verbose
>= 2 && spec_info
->dump
)
7218 fprintf (spec_info
->dump
,
7219 ";;\t\tFixed fallthru to EXIT : %d->>%d->%d->>EXIT\n",
7220 last
->index
, single
->index
, empty
->index
);
7223 before_recovery
= last
;
7226 /* Returns new recovery block. */
7228 sched_create_recovery_block (basic_block
*before_recovery_ptr
)
7234 haifa_recovery_bb_recently_added_p
= true;
7235 haifa_recovery_bb_ever_added_p
= true;
7237 init_before_recovery (before_recovery_ptr
);
7239 barrier
= get_last_bb_insn (before_recovery
);
7240 gcc_assert (BARRIER_P (barrier
));
7242 label
= emit_label_after (gen_label_rtx (), barrier
);
7244 rec
= create_basic_block (label
, label
, before_recovery
);
7246 /* A recovery block always ends with an unconditional jump. */
7247 emit_barrier_after (BB_END (rec
));
7249 if (BB_PARTITION (before_recovery
) != BB_UNPARTITIONED
)
7250 BB_SET_PARTITION (rec
, BB_COLD_PARTITION
);
7252 if (sched_verbose
&& spec_info
->dump
)
7253 fprintf (spec_info
->dump
, ";;\t\tGenerated recovery block rec%d\n",
7259 /* Create edges: FIRST_BB -> REC; FIRST_BB -> SECOND_BB; REC -> SECOND_BB
7260 and emit necessary jumps. */
7262 sched_create_recovery_edges (basic_block first_bb
, basic_block rec
,
7263 basic_block second_bb
)
7269 /* This is fixing of incoming edge. */
7270 /* ??? Which other flags should be specified? */
7271 if (BB_PARTITION (first_bb
) != BB_PARTITION (rec
))
7272 /* Partition type is the same, if it is "unpartitioned". */
7273 edge_flags
= EDGE_CROSSING
;
7277 make_edge (first_bb
, rec
, edge_flags
);
7278 label
= block_label (second_bb
);
7279 jump
= emit_jump_insn_after (gen_jump (label
), BB_END (rec
));
7280 JUMP_LABEL (jump
) = label
;
7281 LABEL_NUSES (label
)++;
7283 if (BB_PARTITION (second_bb
) != BB_PARTITION (rec
))
7284 /* Partition type is the same, if it is "unpartitioned". */
7286 /* Rewritten from cfgrtl.c. */
7287 if (flag_reorder_blocks_and_partition
7288 && targetm_common
.have_named_sections
)
7290 /* We don't need the same note for the check because
7291 any_condjump_p (check) == true. */
7292 add_reg_note (jump
, REG_CROSSING_JUMP
, NULL_RTX
);
7294 edge_flags
= EDGE_CROSSING
;
7299 make_single_succ_edge (rec
, second_bb
, edge_flags
);
7300 if (dom_info_available_p (CDI_DOMINATORS
))
7301 set_immediate_dominator (CDI_DOMINATORS
, rec
, first_bb
);
7304 /* This function creates recovery code for INSN. If MUTATE_P is nonzero,
7305 INSN is a simple check, that should be converted to branchy one. */
7307 create_check_block_twin (rtx insn
, bool mutate_p
)
7310 rtx label
, check
, twin
;
7312 sd_iterator_def sd_it
;
7314 dep_def _new_dep
, *new_dep
= &_new_dep
;
7317 gcc_assert (ORIG_PAT (insn
) != NULL_RTX
);
7320 todo_spec
= TODO_SPEC (insn
);
7323 gcc_assert (IS_SPECULATION_SIMPLE_CHECK_P (insn
)
7324 && (TODO_SPEC (insn
) & SPECULATIVE
) == 0);
7326 todo_spec
= CHECK_SPEC (insn
);
7329 todo_spec
&= SPECULATIVE
;
7331 /* Create recovery block. */
7332 if (mutate_p
|| targetm
.sched
.needs_block_p (todo_spec
))
7334 rec
= sched_create_recovery_block (NULL
);
7335 label
= BB_HEAD (rec
);
7339 rec
= EXIT_BLOCK_PTR
;
7344 check
= targetm
.sched
.gen_spec_check (insn
, label
, todo_spec
);
7346 if (rec
!= EXIT_BLOCK_PTR
)
7348 /* To have mem_reg alive at the beginning of second_bb,
7349 we emit check BEFORE insn, so insn after splitting
7350 insn will be at the beginning of second_bb, which will
7351 provide us with the correct life information. */
7352 check
= emit_jump_insn_before (check
, insn
);
7353 JUMP_LABEL (check
) = label
;
7354 LABEL_NUSES (label
)++;
7357 check
= emit_insn_before (check
, insn
);
7359 /* Extend data structures. */
7360 haifa_init_insn (check
);
7362 /* CHECK is being added to current region. Extend ready list. */
7363 gcc_assert (sched_ready_n_insns
!= -1);
7364 sched_extend_ready_list (sched_ready_n_insns
+ 1);
7366 if (current_sched_info
->add_remove_insn
)
7367 current_sched_info
->add_remove_insn (insn
, 0);
7369 RECOVERY_BLOCK (check
) = rec
;
7371 if (sched_verbose
&& spec_info
->dump
)
7372 fprintf (spec_info
->dump
, ";;\t\tGenerated check insn : %s\n",
7373 (*current_sched_info
->print_insn
) (check
, 0));
7375 gcc_assert (ORIG_PAT (insn
));
7377 /* Initialize TWIN (twin is a duplicate of original instruction
7378 in the recovery block). */
7379 if (rec
!= EXIT_BLOCK_PTR
)
7381 sd_iterator_def sd_it
;
7384 FOR_EACH_DEP (insn
, SD_LIST_RES_BACK
, sd_it
, dep
)
7385 if ((DEP_STATUS (dep
) & DEP_OUTPUT
) != 0)
7387 struct _dep _dep2
, *dep2
= &_dep2
;
7389 init_dep (dep2
, DEP_PRO (dep
), check
, REG_DEP_TRUE
);
7391 sd_add_dep (dep2
, true);
7394 twin
= emit_insn_after (ORIG_PAT (insn
), BB_END (rec
));
7395 haifa_init_insn (twin
);
7397 if (sched_verbose
&& spec_info
->dump
)
7398 /* INSN_BB (insn) isn't determined for twin insns yet.
7399 So we can't use current_sched_info->print_insn. */
7400 fprintf (spec_info
->dump
, ";;\t\tGenerated twin insn : %d/rec%d\n",
7401 INSN_UID (twin
), rec
->index
);
7405 ORIG_PAT (check
) = ORIG_PAT (insn
);
7406 HAS_INTERNAL_DEP (check
) = 1;
7408 /* ??? We probably should change all OUTPUT dependencies to
7412 /* Copy all resolved back dependencies of INSN to TWIN. This will
7413 provide correct value for INSN_TICK (TWIN). */
7414 sd_copy_back_deps (twin
, insn
, true);
7416 if (rec
!= EXIT_BLOCK_PTR
)
7417 /* In case of branchy check, fix CFG. */
7419 basic_block first_bb
, second_bb
;
7422 first_bb
= BLOCK_FOR_INSN (check
);
7423 second_bb
= sched_split_block (first_bb
, check
);
7425 sched_create_recovery_edges (first_bb
, rec
, second_bb
);
7427 sched_init_only_bb (second_bb
, first_bb
);
7428 sched_init_only_bb (rec
, EXIT_BLOCK_PTR
);
7430 jump
= BB_END (rec
);
7431 haifa_init_insn (jump
);
7434 /* Move backward dependences from INSN to CHECK and
7435 move forward dependences from INSN to TWIN. */
7437 /* First, create dependencies between INSN's producers and CHECK & TWIN. */
7438 FOR_EACH_DEP (insn
, SD_LIST_BACK
, sd_it
, dep
)
7440 rtx pro
= DEP_PRO (dep
);
7443 /* If BEGIN_DATA: [insn ~~TRUE~~> producer]:
7444 check --TRUE--> producer ??? or ANTI ???
7445 twin --TRUE--> producer
7446 twin --ANTI--> check
7448 If BEGIN_CONTROL: [insn ~~ANTI~~> producer]:
7449 check --ANTI--> producer
7450 twin --ANTI--> producer
7451 twin --ANTI--> check
7453 If BE_IN_SPEC: [insn ~~TRUE~~> producer]:
7454 check ~~TRUE~~> producer
7455 twin ~~TRUE~~> producer
7456 twin --ANTI--> check */
7458 ds
= DEP_STATUS (dep
);
7460 if (ds
& BEGIN_SPEC
)
7462 gcc_assert (!mutate_p
);
7466 init_dep_1 (new_dep
, pro
, check
, DEP_TYPE (dep
), ds
);
7467 sd_add_dep (new_dep
, false);
7469 if (rec
!= EXIT_BLOCK_PTR
)
7471 DEP_CON (new_dep
) = twin
;
7472 sd_add_dep (new_dep
, false);
7476 /* Second, remove backward dependencies of INSN. */
7477 for (sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
7478 sd_iterator_cond (&sd_it
, &dep
);)
7480 if ((DEP_STATUS (dep
) & BEGIN_SPEC
)
7482 /* We can delete this dep because we overcome it with
7483 BEGIN_SPECULATION. */
7484 sd_delete_dep (sd_it
);
7486 sd_iterator_next (&sd_it
);
7489 /* Future Speculations. Determine what BE_IN speculations will be like. */
7492 /* Fields (DONE_SPEC (x) & BEGIN_SPEC) and CHECK_SPEC (x) are set only
7495 gcc_assert (!DONE_SPEC (insn
));
7499 ds_t ts
= TODO_SPEC (insn
);
7501 DONE_SPEC (insn
) = ts
& BEGIN_SPEC
;
7502 CHECK_SPEC (check
) = ts
& BEGIN_SPEC
;
7504 /* Luckiness of future speculations solely depends upon initial
7505 BEGIN speculation. */
7506 if (ts
& BEGIN_DATA
)
7507 fs
= set_dep_weak (fs
, BE_IN_DATA
, get_dep_weak (ts
, BEGIN_DATA
));
7508 if (ts
& BEGIN_CONTROL
)
7509 fs
= set_dep_weak (fs
, BE_IN_CONTROL
,
7510 get_dep_weak (ts
, BEGIN_CONTROL
));
7513 CHECK_SPEC (check
) = CHECK_SPEC (insn
);
7515 /* Future speculations: call the helper. */
7516 process_insn_forw_deps_be_in_spec (insn
, twin
, fs
);
7518 if (rec
!= EXIT_BLOCK_PTR
)
7520 /* Which types of dependencies should we use here is,
7521 generally, machine-dependent question... But, for now,
7526 init_dep (new_dep
, insn
, check
, REG_DEP_TRUE
);
7527 sd_add_dep (new_dep
, false);
7529 init_dep (new_dep
, insn
, twin
, REG_DEP_OUTPUT
);
7530 sd_add_dep (new_dep
, false);
7534 if (spec_info
->dump
)
7535 fprintf (spec_info
->dump
, ";;\t\tRemoved simple check : %s\n",
7536 (*current_sched_info
->print_insn
) (insn
, 0));
7538 /* Remove all dependencies of the INSN. */
7540 sd_it
= sd_iterator_start (insn
, (SD_LIST_FORW
7542 | SD_LIST_RES_BACK
));
7543 while (sd_iterator_cond (&sd_it
, &dep
))
7544 sd_delete_dep (sd_it
);
7547 /* If former check (INSN) already was moved to the ready (or queue)
7548 list, add new check (CHECK) there too. */
7549 if (QUEUE_INDEX (insn
) != QUEUE_NOWHERE
)
7552 /* Remove old check from instruction stream and free its
7554 sched_remove_insn (insn
);
7557 init_dep (new_dep
, check
, twin
, REG_DEP_ANTI
);
7558 sd_add_dep (new_dep
, false);
7562 init_dep_1 (new_dep
, insn
, check
, REG_DEP_TRUE
, DEP_TRUE
| DEP_OUTPUT
);
7563 sd_add_dep (new_dep
, false);
7567 /* Fix priorities. If MUTATE_P is nonzero, this is not necessary,
7568 because it'll be done later in add_to_speculative_block. */
7570 rtx_vec_t priorities_roots
= NULL
;
7572 clear_priorities (twin
, &priorities_roots
);
7573 calc_priorities (priorities_roots
);
7574 VEC_free (rtx
, heap
, priorities_roots
);
7578 /* Removes dependency between instructions in the recovery block REC
7579 and usual region instructions. It keeps inner dependences so it
7580 won't be necessary to recompute them. */
7582 fix_recovery_deps (basic_block rec
)
7584 rtx note
, insn
, jump
, ready_list
= 0;
7585 bitmap_head in_ready
;
7588 bitmap_initialize (&in_ready
, 0);
7590 /* NOTE - a basic block note. */
7591 note
= NEXT_INSN (BB_HEAD (rec
));
7592 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
7593 insn
= BB_END (rec
);
7594 gcc_assert (JUMP_P (insn
));
7595 insn
= PREV_INSN (insn
);
7599 sd_iterator_def sd_it
;
7602 for (sd_it
= sd_iterator_start (insn
, SD_LIST_FORW
);
7603 sd_iterator_cond (&sd_it
, &dep
);)
7605 rtx consumer
= DEP_CON (dep
);
7607 if (BLOCK_FOR_INSN (consumer
) != rec
)
7609 sd_delete_dep (sd_it
);
7611 if (bitmap_set_bit (&in_ready
, INSN_LUID (consumer
)))
7612 ready_list
= alloc_INSN_LIST (consumer
, ready_list
);
7616 gcc_assert ((DEP_STATUS (dep
) & DEP_TYPES
) == DEP_TRUE
);
7618 sd_iterator_next (&sd_it
);
7622 insn
= PREV_INSN (insn
);
7624 while (insn
!= note
);
7626 bitmap_clear (&in_ready
);
7628 /* Try to add instructions to the ready or queue list. */
7629 for (link
= ready_list
; link
; link
= XEXP (link
, 1))
7630 try_ready (XEXP (link
, 0));
7631 free_INSN_LIST_list (&ready_list
);
7633 /* Fixing jump's dependences. */
7634 insn
= BB_HEAD (rec
);
7635 jump
= BB_END (rec
);
7637 gcc_assert (LABEL_P (insn
));
7638 insn
= NEXT_INSN (insn
);
7640 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
7641 add_jump_dependencies (insn
, jump
);
7644 /* Change pattern of INSN to NEW_PAT. Invalidate cached haifa
7645 instruction data. */
7647 haifa_change_pattern (rtx insn
, rtx new_pat
)
7649 sd_iterator_def sd_it
;
7653 t
= validate_change (insn
, &PATTERN (insn
), new_pat
, 0);
7656 dfa_clear_single_insn_cache (insn
);
7658 sd_it
= sd_iterator_start (insn
,
7659 SD_LIST_FORW
| SD_LIST_BACK
| SD_LIST_RES_BACK
);
7660 while (sd_iterator_cond (&sd_it
, &dep
))
7662 DEP_COST (dep
) = UNKNOWN_DEP_COST
;
7663 sd_iterator_next (&sd_it
);
7666 /* Invalidate INSN_COST, so it'll be recalculated. */
7667 INSN_COST (insn
) = -1;
7668 /* Invalidate INSN_TICK, so it'll be recalculated. */
7669 INSN_TICK (insn
) = INVALID_TICK
;
7673 /* -1 - can't speculate,
7674 0 - for speculation with REQUEST mode it is OK to use
7675 current instruction pattern,
7676 1 - need to change pattern for *NEW_PAT to be speculative. */
7678 sched_speculate_insn (rtx insn
, ds_t request
, rtx
*new_pat
)
7680 gcc_assert (current_sched_info
->flags
& DO_SPECULATION
7681 && (request
& SPECULATIVE
)
7682 && sched_insn_is_legitimate_for_speculation_p (insn
, request
));
7684 if ((request
& spec_info
->mask
) != request
)
7687 if (request
& BE_IN_SPEC
7688 && !(request
& BEGIN_SPEC
))
7691 return targetm
.sched
.speculate_insn (insn
, request
, new_pat
);
7695 haifa_speculate_insn (rtx insn
, ds_t request
, rtx
*new_pat
)
7697 gcc_assert (sched_deps_info
->generate_spec_deps
7698 && !IS_SPECULATION_CHECK_P (insn
));
7700 if (HAS_INTERNAL_DEP (insn
)
7701 || SCHED_GROUP_P (insn
))
7704 return sched_speculate_insn (insn
, request
, new_pat
);
7707 /* Print some information about block BB, which starts with HEAD and
7708 ends with TAIL, before scheduling it.
7709 I is zero, if scheduler is about to start with the fresh ebb. */
7711 dump_new_block_header (int i
, basic_block bb
, rtx head
, rtx tail
)
7714 fprintf (sched_dump
,
7715 ";; ======================================================\n");
7717 fprintf (sched_dump
,
7718 ";; =====================ADVANCING TO=====================\n");
7719 fprintf (sched_dump
,
7720 ";; -- basic block %d from %d to %d -- %s reload\n",
7721 bb
->index
, INSN_UID (head
), INSN_UID (tail
),
7722 (reload_completed
? "after" : "before"));
7723 fprintf (sched_dump
,
7724 ";; ======================================================\n");
7725 fprintf (sched_dump
, "\n");
7728 /* Unlink basic block notes and labels and saves them, so they
7729 can be easily restored. We unlink basic block notes in EBB to
7730 provide back-compatibility with the previous code, as target backends
7731 assume, that there'll be only instructions between
7732 current_sched_info->{head and tail}. We restore these notes as soon
7734 FIRST (LAST) is the first (last) basic block in the ebb.
7735 NB: In usual case (FIRST == LAST) nothing is really done. */
7737 unlink_bb_notes (basic_block first
, basic_block last
)
7739 /* We DON'T unlink basic block notes of the first block in the ebb. */
7743 bb_header
= XNEWVEC (rtx
, last_basic_block
);
7745 /* Make a sentinel. */
7746 if (last
->next_bb
!= EXIT_BLOCK_PTR
)
7747 bb_header
[last
->next_bb
->index
] = 0;
7749 first
= first
->next_bb
;
7752 rtx prev
, label
, note
, next
;
7754 label
= BB_HEAD (last
);
7755 if (LABEL_P (label
))
7756 note
= NEXT_INSN (label
);
7759 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
7761 prev
= PREV_INSN (label
);
7762 next
= NEXT_INSN (note
);
7763 gcc_assert (prev
&& next
);
7765 NEXT_INSN (prev
) = next
;
7766 PREV_INSN (next
) = prev
;
7768 bb_header
[last
->index
] = label
;
7773 last
= last
->prev_bb
;
7778 /* Restore basic block notes.
7779 FIRST is the first basic block in the ebb. */
7781 restore_bb_notes (basic_block first
)
7786 /* We DON'T unlink basic block notes of the first block in the ebb. */
7787 first
= first
->next_bb
;
7788 /* Remember: FIRST is actually a second basic block in the ebb. */
7790 while (first
!= EXIT_BLOCK_PTR
7791 && bb_header
[first
->index
])
7793 rtx prev
, label
, note
, next
;
7795 label
= bb_header
[first
->index
];
7796 prev
= PREV_INSN (label
);
7797 next
= NEXT_INSN (prev
);
7799 if (LABEL_P (label
))
7800 note
= NEXT_INSN (label
);
7803 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
7805 bb_header
[first
->index
] = 0;
7807 NEXT_INSN (prev
) = label
;
7808 NEXT_INSN (note
) = next
;
7809 PREV_INSN (next
) = note
;
7811 first
= first
->next_bb
;
7819 Fix CFG after both in- and inter-block movement of
7820 control_flow_insn_p JUMP. */
7822 fix_jump_move (rtx jump
)
7824 basic_block bb
, jump_bb
, jump_bb_next
;
7826 bb
= BLOCK_FOR_INSN (PREV_INSN (jump
));
7827 jump_bb
= BLOCK_FOR_INSN (jump
);
7828 jump_bb_next
= jump_bb
->next_bb
;
7830 gcc_assert (common_sched_info
->sched_pass_id
== SCHED_EBB_PASS
7831 || IS_SPECULATION_BRANCHY_CHECK_P (jump
));
7833 if (!NOTE_INSN_BASIC_BLOCK_P (BB_END (jump_bb_next
)))
7834 /* if jump_bb_next is not empty. */
7835 BB_END (jump_bb
) = BB_END (jump_bb_next
);
7837 if (BB_END (bb
) != PREV_INSN (jump
))
7838 /* Then there are instruction after jump that should be placed
7840 BB_END (jump_bb_next
) = BB_END (bb
);
7842 /* Otherwise jump_bb_next is empty. */
7843 BB_END (jump_bb_next
) = NEXT_INSN (BB_HEAD (jump_bb_next
));
7845 /* To make assertion in move_insn happy. */
7846 BB_END (bb
) = PREV_INSN (jump
);
7848 update_bb_for_insn (jump_bb_next
);
7851 /* Fix CFG after interblock movement of control_flow_insn_p JUMP. */
7853 move_block_after_check (rtx jump
)
7855 basic_block bb
, jump_bb
, jump_bb_next
;
7858 bb
= BLOCK_FOR_INSN (PREV_INSN (jump
));
7859 jump_bb
= BLOCK_FOR_INSN (jump
);
7860 jump_bb_next
= jump_bb
->next_bb
;
7862 update_bb_for_insn (jump_bb
);
7864 gcc_assert (IS_SPECULATION_CHECK_P (jump
)
7865 || IS_SPECULATION_CHECK_P (BB_END (jump_bb_next
)));
7867 unlink_block (jump_bb_next
);
7868 link_block (jump_bb_next
, bb
);
7872 move_succs (&(jump_bb
->succs
), bb
);
7873 move_succs (&(jump_bb_next
->succs
), jump_bb
);
7874 move_succs (&t
, jump_bb_next
);
7876 df_mark_solutions_dirty ();
7878 common_sched_info
->fix_recovery_cfg
7879 (bb
->index
, jump_bb
->index
, jump_bb_next
->index
);
7882 /* Helper function for move_block_after_check.
7883 This functions attaches edge vector pointed to by SUCCSP to
7886 move_succs (VEC(edge
,gc
) **succsp
, basic_block to
)
7891 gcc_assert (to
->succs
== 0);
7893 to
->succs
= *succsp
;
7895 FOR_EACH_EDGE (e
, ei
, to
->succs
)
7901 /* Remove INSN from the instruction stream.
7902 INSN should have any dependencies. */
7904 sched_remove_insn (rtx insn
)
7906 sd_finish_insn (insn
);
7908 change_queue_index (insn
, QUEUE_NOWHERE
);
7909 current_sched_info
->add_remove_insn (insn
, 1);
7913 /* Clear priorities of all instructions, that are forward dependent on INSN.
7914 Store in vector pointed to by ROOTS_PTR insns on which priority () should
7915 be invoked to initialize all cleared priorities. */
7917 clear_priorities (rtx insn
, rtx_vec_t
*roots_ptr
)
7919 sd_iterator_def sd_it
;
7921 bool insn_is_root_p
= true;
7923 gcc_assert (QUEUE_INDEX (insn
) != QUEUE_SCHEDULED
);
7925 FOR_EACH_DEP (insn
, SD_LIST_BACK
, sd_it
, dep
)
7927 rtx pro
= DEP_PRO (dep
);
7929 if (INSN_PRIORITY_STATUS (pro
) >= 0
7930 && QUEUE_INDEX (insn
) != QUEUE_SCHEDULED
)
7932 /* If DEP doesn't contribute to priority then INSN itself should
7933 be added to priority roots. */
7934 if (contributes_to_priority_p (dep
))
7935 insn_is_root_p
= false;
7937 INSN_PRIORITY_STATUS (pro
) = -1;
7938 clear_priorities (pro
, roots_ptr
);
7943 VEC_safe_push (rtx
, heap
, *roots_ptr
, insn
);
7946 /* Recompute priorities of instructions, whose priorities might have been
7947 changed. ROOTS is a vector of instructions whose priority computation will
7948 trigger initialization of all cleared priorities. */
7950 calc_priorities (rtx_vec_t roots
)
7955 FOR_EACH_VEC_ELT (rtx
, roots
, i
, insn
)
7960 /* Add dependences between JUMP and other instructions in the recovery
7961 block. INSN is the first insn the recovery block. */
7963 add_jump_dependencies (rtx insn
, rtx jump
)
7967 insn
= NEXT_INSN (insn
);
7971 if (dep_list_size (insn
, SD_LIST_FORW
) == 0)
7973 dep_def _new_dep
, *new_dep
= &_new_dep
;
7975 init_dep (new_dep
, insn
, jump
, REG_DEP_ANTI
);
7976 sd_add_dep (new_dep
, false);
7981 gcc_assert (!sd_lists_empty_p (jump
, SD_LIST_BACK
));
7984 /* Extend data structures for logical insn UID. */
7986 sched_extend_luids (void)
7988 int new_luids_max_uid
= get_max_uid () + 1;
7990 VEC_safe_grow_cleared (int, heap
, sched_luids
, new_luids_max_uid
);
7993 /* Initialize LUID for INSN. */
7995 sched_init_insn_luid (rtx insn
)
7997 int i
= INSN_P (insn
) ? 1 : common_sched_info
->luid_for_non_insn (insn
);
8002 luid
= sched_max_luid
;
8003 sched_max_luid
+= i
;
8008 SET_INSN_LUID (insn
, luid
);
8011 /* Initialize luids for BBS.
8012 The hook common_sched_info->luid_for_non_insn () is used to determine
8013 if notes, labels, etc. need luids. */
8015 sched_init_luids (bb_vec_t bbs
)
8020 sched_extend_luids ();
8021 FOR_EACH_VEC_ELT (basic_block
, bbs
, i
, bb
)
8025 FOR_BB_INSNS (bb
, insn
)
8026 sched_init_insn_luid (insn
);
8032 sched_finish_luids (void)
8034 VEC_free (int, heap
, sched_luids
);
8038 /* Return logical uid of INSN. Helpful while debugging. */
8040 insn_luid (rtx insn
)
8042 return INSN_LUID (insn
);
8045 /* Extend per insn data in the target. */
8047 sched_extend_target (void)
8049 if (targetm
.sched
.h_i_d_extended
)
8050 targetm
.sched
.h_i_d_extended ();
8053 /* Extend global scheduler structures (those, that live across calls to
8054 schedule_block) to include information about just emitted INSN. */
8058 int reserve
= (get_max_uid () + 1
8059 - VEC_length (haifa_insn_data_def
, h_i_d
));
8061 && ! VEC_space (haifa_insn_data_def
, h_i_d
, reserve
))
8063 VEC_safe_grow_cleared (haifa_insn_data_def
, heap
, h_i_d
,
8064 3 * get_max_uid () / 2);
8065 sched_extend_target ();
8069 /* Initialize h_i_d entry of the INSN with default values.
8070 Values, that are not explicitly initialized here, hold zero. */
8072 init_h_i_d (rtx insn
)
8074 if (INSN_LUID (insn
) > 0)
8076 INSN_COST (insn
) = -1;
8077 QUEUE_INDEX (insn
) = QUEUE_NOWHERE
;
8078 INSN_TICK (insn
) = INVALID_TICK
;
8079 INSN_EXACT_TICK (insn
) = INVALID_TICK
;
8080 INTER_TICK (insn
) = INVALID_TICK
;
8081 TODO_SPEC (insn
) = HARD_DEP
;
8085 /* Initialize haifa_insn_data for BBS. */
8087 haifa_init_h_i_d (bb_vec_t bbs
)
8093 FOR_EACH_VEC_ELT (basic_block
, bbs
, i
, bb
)
8097 FOR_BB_INSNS (bb
, insn
)
8102 /* Finalize haifa_insn_data. */
8104 haifa_finish_h_i_d (void)
8107 haifa_insn_data_t data
;
8108 struct reg_use_data
*use
, *next
;
8110 FOR_EACH_VEC_ELT (haifa_insn_data_def
, h_i_d
, i
, data
)
8112 free (data
->max_reg_pressure
);
8113 free (data
->reg_pressure
);
8114 for (use
= data
->reg_use_list
; use
!= NULL
; use
= next
)
8116 next
= use
->next_insn_use
;
8120 VEC_free (haifa_insn_data_def
, heap
, h_i_d
);
8123 /* Init data for the new insn INSN. */
8125 haifa_init_insn (rtx insn
)
8127 gcc_assert (insn
!= NULL
);
8129 sched_extend_luids ();
8130 sched_init_insn_luid (insn
);
8131 sched_extend_target ();
8132 sched_deps_init (false);
8136 if (adding_bb_to_current_region_p
)
8138 sd_init_insn (insn
);
8140 /* Extend dependency caches by one element. */
8141 extend_dependency_caches (1, false);
8143 if (sched_pressure
!= SCHED_PRESSURE_NONE
)
8144 init_insn_reg_pressure_info (insn
);
8147 /* Init data for the new basic block BB which comes after AFTER. */
8149 haifa_init_only_bb (basic_block bb
, basic_block after
)
8151 gcc_assert (bb
!= NULL
);
8155 if (common_sched_info
->add_block
)
8156 /* This changes only data structures of the front-end. */
8157 common_sched_info
->add_block (bb
, after
);
8160 /* A generic version of sched_split_block (). */
8162 sched_split_block_1 (basic_block first_bb
, rtx after
)
8166 e
= split_block (first_bb
, after
);
8167 gcc_assert (e
->src
== first_bb
);
8169 /* sched_split_block emits note if *check == BB_END. Probably it
8170 is better to rip that note off. */
8175 /* A generic version of sched_create_empty_bb (). */
8177 sched_create_empty_bb_1 (basic_block after
)
8179 return create_empty_bb (after
);
8182 /* Insert PAT as an INSN into the schedule and update the necessary data
8183 structures to account for it. */
8185 sched_emit_insn (rtx pat
)
8187 rtx insn
= emit_insn_before (pat
, nonscheduled_insns_begin
);
8188 haifa_init_insn (insn
);
8190 if (current_sched_info
->add_remove_insn
)
8191 current_sched_info
->add_remove_insn (insn
, 0);
8193 (*current_sched_info
->begin_schedule_ready
) (insn
);
8194 VEC_safe_push (rtx
, heap
, scheduled_insns
, insn
);
8196 last_scheduled_insn
= insn
;
8200 /* This function returns a candidate satisfying dispatch constraints from
8204 ready_remove_first_dispatch (struct ready_list
*ready
)
8207 rtx insn
= ready_element (ready
, 0);
8209 if (ready
->n_ready
== 1
8210 || INSN_CODE (insn
) < 0
8212 || !active_insn_p (insn
)
8213 || targetm
.sched
.dispatch (insn
, FITS_DISPATCH_WINDOW
))
8214 return ready_remove_first (ready
);
8216 for (i
= 1; i
< ready
->n_ready
; i
++)
8218 insn
= ready_element (ready
, i
);
8220 if (INSN_CODE (insn
) < 0
8222 || !active_insn_p (insn
))
8225 if (targetm
.sched
.dispatch (insn
, FITS_DISPATCH_WINDOW
))
8227 /* Return ith element of ready. */
8228 insn
= ready_remove (ready
, i
);
8233 if (targetm
.sched
.dispatch (NULL_RTX
, DISPATCH_VIOLATION
))
8234 return ready_remove_first (ready
);
8236 for (i
= 1; i
< ready
->n_ready
; i
++)
8238 insn
= ready_element (ready
, i
);
8240 if (INSN_CODE (insn
) < 0
8242 || !active_insn_p (insn
))
8245 /* Return i-th element of ready. */
8246 if (targetm
.sched
.dispatch (insn
, IS_CMP
))
8247 return ready_remove (ready
, i
);
8250 return ready_remove_first (ready
);
8253 /* Get number of ready insn in the ready list. */
8256 number_in_ready (void)
8258 return ready
.n_ready
;
8261 /* Get number of ready's in the ready list. */
8264 get_ready_element (int i
)
8266 return ready_element (&ready
, i
);
8269 #endif /* INSN_SCHEDULING */