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"
151 #include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.h. */
154 #ifdef INSN_SCHEDULING
156 /* issue_rate is the number of insns that can be scheduled in the same
157 machine cycle. It can be defined in the config/mach/mach.h file,
158 otherwise we set it to 1. */
162 /* This can be set to true by a backend if the scheduler should not
163 enable a DCE pass. */
166 /* The current initiation interval used when modulo scheduling. */
167 static int modulo_ii
;
169 /* The maximum number of stages we are prepared to handle. */
170 static int modulo_max_stages
;
172 /* The number of insns that exist in each iteration of the loop. We use this
173 to detect when we've scheduled all insns from the first iteration. */
174 static int modulo_n_insns
;
176 /* The current count of insns in the first iteration of the loop that have
177 already been scheduled. */
178 static int modulo_insns_scheduled
;
180 /* The maximum uid of insns from the first iteration of the loop. */
181 static int modulo_iter0_max_uid
;
183 /* The number of times we should attempt to backtrack when modulo scheduling.
184 Decreased each time we have to backtrack. */
185 static int modulo_backtracks_left
;
187 /* The stage in which the last insn from the original loop was
189 static int modulo_last_stage
;
191 /* sched-verbose controls the amount of debugging output the
192 scheduler prints. It is controlled by -fsched-verbose=N:
193 N>0 and no -DSR : the output is directed to stderr.
194 N>=10 will direct the printouts to stderr (regardless of -dSR).
196 N=2: bb's probabilities, detailed ready list info, unit/insn info.
197 N=3: rtl at abort point, control-flow, regions info.
198 N=5: dependences info. */
200 int sched_verbose
= 0;
202 /* Debugging file. All printouts are sent to dump, which is always set,
203 either to stderr, or to the dump listing file (-dRS). */
204 FILE *sched_dump
= 0;
206 /* This is a placeholder for the scheduler parameters common
207 to all schedulers. */
208 struct common_sched_info_def
*common_sched_info
;
210 #define INSN_TICK(INSN) (HID (INSN)->tick)
211 #define INSN_EXACT_TICK(INSN) (HID (INSN)->exact_tick)
212 #define INSN_TICK_ESTIMATE(INSN) (HID (INSN)->tick_estimate)
213 #define INTER_TICK(INSN) (HID (INSN)->inter_tick)
214 #define FEEDS_BACKTRACK_INSN(INSN) (HID (INSN)->feeds_backtrack_insn)
215 #define SHADOW_P(INSN) (HID (INSN)->shadow_p)
216 #define MUST_RECOMPUTE_SPEC_P(INSN) (HID (INSN)->must_recompute_spec)
218 /* If INSN_TICK of an instruction is equal to INVALID_TICK,
219 then it should be recalculated from scratch. */
220 #define INVALID_TICK (-(max_insn_queue_index + 1))
221 /* The minimal value of the INSN_TICK of an instruction. */
222 #define MIN_TICK (-max_insn_queue_index)
224 /* List of important notes we must keep around. This is a pointer to the
225 last element in the list. */
228 static struct spec_info_def spec_info_var
;
229 /* Description of the speculative part of the scheduling.
230 If NULL - no speculation. */
231 spec_info_t spec_info
= NULL
;
233 /* True, if recovery block was added during scheduling of current block.
234 Used to determine, if we need to fix INSN_TICKs. */
235 static bool haifa_recovery_bb_recently_added_p
;
237 /* True, if recovery block was added during this scheduling pass.
238 Used to determine if we should have empty memory pools of dependencies
239 after finishing current region. */
240 bool haifa_recovery_bb_ever_added_p
;
242 /* Counters of different types of speculative instructions. */
243 static int nr_begin_data
, nr_be_in_data
, nr_begin_control
, nr_be_in_control
;
245 /* Array used in {unlink, restore}_bb_notes. */
246 static rtx
*bb_header
= 0;
248 /* Basic block after which recovery blocks will be created. */
249 static basic_block before_recovery
;
251 /* Basic block just before the EXIT_BLOCK and after recovery, if we have
253 basic_block after_recovery
;
255 /* FALSE if we add bb to another region, so we don't need to initialize it. */
256 bool adding_bb_to_current_region_p
= true;
260 /* An instruction is ready to be scheduled when all insns preceding it
261 have already been scheduled. It is important to ensure that all
262 insns which use its result will not be executed until its result
263 has been computed. An insn is maintained in one of four structures:
265 (P) the "Pending" set of insns which cannot be scheduled until
266 their dependencies have been satisfied.
267 (Q) the "Queued" set of insns that can be scheduled when sufficient
269 (R) the "Ready" list of unscheduled, uncommitted insns.
270 (S) the "Scheduled" list of insns.
272 Initially, all insns are either "Pending" or "Ready" depending on
273 whether their dependencies are satisfied.
275 Insns move from the "Ready" list to the "Scheduled" list as they
276 are committed to the schedule. As this occurs, the insns in the
277 "Pending" list have their dependencies satisfied and move to either
278 the "Ready" list or the "Queued" set depending on whether
279 sufficient time has passed to make them ready. As time passes,
280 insns move from the "Queued" set to the "Ready" list.
282 The "Pending" list (P) are the insns in the INSN_FORW_DEPS of the
283 unscheduled insns, i.e., those that are ready, queued, and pending.
284 The "Queued" set (Q) is implemented by the variable `insn_queue'.
285 The "Ready" list (R) is implemented by the variables `ready' and
287 The "Scheduled" list (S) is the new insn chain built by this pass.
289 The transition (R->S) is implemented in the scheduling loop in
290 `schedule_block' when the best insn to schedule is chosen.
291 The transitions (P->R and P->Q) are implemented in `schedule_insn' as
292 insns move from the ready list to the scheduled list.
293 The transition (Q->R) is implemented in 'queue_to_insn' as time
294 passes or stalls are introduced. */
296 /* Implement a circular buffer to delay instructions until sufficient
297 time has passed. For the new pipeline description interface,
298 MAX_INSN_QUEUE_INDEX is a power of two minus one which is not less
299 than maximal time of instruction execution computed by genattr.c on
300 the base maximal time of functional unit reservations and getting a
301 result. This is the longest time an insn may be queued. */
303 static rtx
*insn_queue
;
304 static int q_ptr
= 0;
305 static int q_size
= 0;
306 #define NEXT_Q(X) (((X)+1) & max_insn_queue_index)
307 #define NEXT_Q_AFTER(X, C) (((X)+C) & max_insn_queue_index)
309 #define QUEUE_SCHEDULED (-3)
310 #define QUEUE_NOWHERE (-2)
311 #define QUEUE_READY (-1)
312 /* QUEUE_SCHEDULED - INSN is scheduled.
313 QUEUE_NOWHERE - INSN isn't scheduled yet and is neither in
315 QUEUE_READY - INSN is in ready list.
316 N >= 0 - INSN queued for X [where NEXT_Q_AFTER (q_ptr, X) == N] cycles. */
318 #define QUEUE_INDEX(INSN) (HID (INSN)->queue_index)
320 /* The following variable value refers for all current and future
321 reservations of the processor units. */
324 /* The following variable value is size of memory representing all
325 current and future reservations of the processor units. */
326 size_t dfa_state_size
;
328 /* The following array is used to find the best insn from ready when
329 the automaton pipeline interface is used. */
330 char *ready_try
= NULL
;
332 /* The ready list. */
333 struct ready_list ready
= {NULL
, 0, 0, 0, 0};
335 /* The pointer to the ready list (to be removed). */
336 static struct ready_list
*readyp
= &ready
;
338 /* Scheduling clock. */
339 static int clock_var
;
341 /* Clock at which the previous instruction was issued. */
342 static int last_clock_var
;
344 /* Set to true if, when queuing a shadow insn, we discover that it would be
345 scheduled too late. */
346 static bool must_backtrack
;
348 /* The following variable value is number of essential insns issued on
349 the current cycle. An insn is essential one if it changes the
351 int cycle_issued_insns
;
353 /* This records the actual schedule. It is built up during the main phase
354 of schedule_block, and afterwards used to reorder the insns in the RTL. */
355 static VEC(rtx
, heap
) *scheduled_insns
;
357 static int may_trap_exp (const_rtx
, int);
359 /* Nonzero iff the address is comprised from at most 1 register. */
360 #define CONST_BASED_ADDRESS_P(x) \
362 || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
363 || (GET_CODE (x) == LO_SUM)) \
364 && (CONSTANT_P (XEXP (x, 0)) \
365 || CONSTANT_P (XEXP (x, 1)))))
367 /* Returns a class that insn with GET_DEST(insn)=x may belong to,
368 as found by analyzing insn's expression. */
371 static int haifa_luid_for_non_insn (rtx x
);
373 /* Haifa version of sched_info hooks common to all headers. */
374 const struct common_sched_info_def haifa_common_sched_info
=
376 NULL
, /* fix_recovery_cfg */
377 NULL
, /* add_block */
378 NULL
, /* estimate_number_of_insns */
379 haifa_luid_for_non_insn
, /* luid_for_non_insn */
380 SCHED_PASS_UNKNOWN
/* sched_pass_id */
383 /* Mapping from instruction UID to its Logical UID. */
384 VEC (int, heap
) *sched_luids
= NULL
;
386 /* Next LUID to assign to an instruction. */
387 int sched_max_luid
= 1;
389 /* Haifa Instruction Data. */
390 VEC (haifa_insn_data_def
, heap
) *h_i_d
= NULL
;
392 void (* sched_init_only_bb
) (basic_block
, basic_block
);
394 /* Split block function. Different schedulers might use different functions
395 to handle their internal data consistent. */
396 basic_block (* sched_split_block
) (basic_block
, rtx
);
398 /* Create empty basic block after the specified block. */
399 basic_block (* sched_create_empty_bb
) (basic_block
);
402 may_trap_exp (const_rtx x
, int is_store
)
411 if (code
== MEM
&& may_trap_p (x
))
418 /* The insn uses memory: a volatile load. */
419 if (MEM_VOLATILE_P (x
))
421 /* An exception-free load. */
424 /* A load with 1 base register, to be further checked. */
425 if (CONST_BASED_ADDRESS_P (XEXP (x
, 0)))
426 return PFREE_CANDIDATE
;
427 /* No info on the load, to be further checked. */
428 return PRISKY_CANDIDATE
;
433 int i
, insn_class
= TRAP_FREE
;
435 /* Neither store nor load, check if it may cause a trap. */
438 /* Recursive step: walk the insn... */
439 fmt
= GET_RTX_FORMAT (code
);
440 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
444 int tmp_class
= may_trap_exp (XEXP (x
, i
), is_store
);
445 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
447 else if (fmt
[i
] == 'E')
450 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
452 int tmp_class
= may_trap_exp (XVECEXP (x
, i
, j
), is_store
);
453 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
454 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
458 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
465 /* Classifies rtx X of an insn for the purpose of verifying that X can be
466 executed speculatively (and consequently the insn can be moved
467 speculatively), by examining X, returning:
468 TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
469 TRAP_FREE: non-load insn.
470 IFREE: load from a globally safe location.
471 IRISKY: volatile load.
472 PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
473 being either PFREE or PRISKY. */
476 haifa_classify_rtx (const_rtx x
)
478 int tmp_class
= TRAP_FREE
;
479 int insn_class
= TRAP_FREE
;
482 if (GET_CODE (x
) == PARALLEL
)
484 int i
, len
= XVECLEN (x
, 0);
486 for (i
= len
- 1; i
>= 0; i
--)
488 tmp_class
= haifa_classify_rtx (XVECEXP (x
, 0, i
));
489 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
490 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
500 /* Test if it is a 'store'. */
501 tmp_class
= may_trap_exp (XEXP (x
, 0), 1);
504 /* Test if it is a store. */
505 tmp_class
= may_trap_exp (SET_DEST (x
), 1);
506 if (tmp_class
== TRAP_RISKY
)
508 /* Test if it is a load. */
510 WORST_CLASS (tmp_class
,
511 may_trap_exp (SET_SRC (x
), 0));
514 tmp_class
= haifa_classify_rtx (COND_EXEC_CODE (x
));
515 if (tmp_class
== TRAP_RISKY
)
517 tmp_class
= WORST_CLASS (tmp_class
,
518 may_trap_exp (COND_EXEC_TEST (x
), 0));
521 tmp_class
= TRAP_RISKY
;
525 insn_class
= tmp_class
;
532 haifa_classify_insn (const_rtx insn
)
534 return haifa_classify_rtx (PATTERN (insn
));
537 /* After the scheduler initialization function has been called, this function
538 can be called to enable modulo scheduling. II is the initiation interval
539 we should use, it affects the delays for delay_pairs that were recorded as
540 separated by a given number of stages.
542 MAX_STAGES provides us with a limit
543 after which we give up scheduling; the caller must have unrolled at least
544 as many copies of the loop body and recorded delay_pairs for them.
546 INSNS is the number of real (non-debug) insns in one iteration of
547 the loop. MAX_UID can be used to test whether an insn belongs to
548 the first iteration of the loop; all of them have a uid lower than
551 set_modulo_params (int ii
, int max_stages
, int insns
, int max_uid
)
554 modulo_max_stages
= max_stages
;
555 modulo_n_insns
= insns
;
556 modulo_iter0_max_uid
= max_uid
;
557 modulo_backtracks_left
= PARAM_VALUE (PARAM_MAX_MODULO_BACKTRACK_ATTEMPTS
);
560 /* A structure to record a pair of insns where the first one is a real
561 insn that has delay slots, and the second is its delayed shadow.
562 I1 is scheduled normally and will emit an assembly instruction,
563 while I2 describes the side effect that takes place at the
564 transition between cycles CYCLES and (CYCLES + 1) after I1. */
567 struct delay_pair
*next_same_i1
;
570 /* When doing modulo scheduling, we a delay_pair can also be used to
571 show that I1 and I2 are the same insn in a different stage. If that
572 is the case, STAGES will be nonzero. */
576 /* Two hash tables to record delay_pairs, one indexed by I1 and the other
578 static htab_t delay_htab
;
579 static htab_t delay_htab_i2
;
581 /* Called through htab_traverse. Walk the hashtable using I2 as
582 index, and delete all elements involving an UID higher than
583 that pointed to by *DATA. */
585 htab_i2_traverse (void **slot
, void *data
)
587 int maxuid
= *(int *)data
;
588 struct delay_pair
*p
= *(struct delay_pair
**)slot
;
589 if (INSN_UID (p
->i2
) >= maxuid
|| INSN_UID (p
->i1
) >= maxuid
)
591 htab_clear_slot (delay_htab_i2
, slot
);
596 /* Called through htab_traverse. Walk the hashtable using I2 as
597 index, and delete all elements involving an UID higher than
598 that pointed to by *DATA. */
600 htab_i1_traverse (void **slot
, void *data
)
602 int maxuid
= *(int *)data
;
603 struct delay_pair
**pslot
= (struct delay_pair
**)slot
;
604 struct delay_pair
*p
, *first
, **pprev
;
606 if (INSN_UID ((*pslot
)->i1
) >= maxuid
)
608 htab_clear_slot (delay_htab
, slot
);
612 for (p
= *pslot
; p
; p
= p
->next_same_i1
)
614 if (INSN_UID (p
->i2
) < maxuid
)
617 pprev
= &p
->next_same_i1
;
622 htab_clear_slot (delay_htab
, slot
);
628 /* Discard all delay pairs which involve an insn with an UID higher
631 discard_delay_pairs_above (int max_uid
)
633 htab_traverse (delay_htab
, htab_i1_traverse
, &max_uid
);
634 htab_traverse (delay_htab_i2
, htab_i2_traverse
, &max_uid
);
637 /* Returns a hash value for X (which really is a delay_pair), based on
640 delay_hash_i1 (const void *x
)
642 return htab_hash_pointer (((const struct delay_pair
*) x
)->i1
);
645 /* Returns a hash value for X (which really is a delay_pair), based on
648 delay_hash_i2 (const void *x
)
650 return htab_hash_pointer (((const struct delay_pair
*) x
)->i2
);
653 /* Return nonzero if I1 of pair X is the same as that of pair Y. */
655 delay_i1_eq (const void *x
, const void *y
)
657 return ((const struct delay_pair
*) x
)->i1
== y
;
660 /* Return nonzero if I2 of pair X is the same as that of pair Y. */
662 delay_i2_eq (const void *x
, const void *y
)
664 return ((const struct delay_pair
*) x
)->i2
== y
;
667 /* This function can be called by a port just before it starts the final
668 scheduling pass. It records the fact that an instruction with delay
669 slots has been split into two insns, I1 and I2. The first one will be
670 scheduled normally and initiates the operation. The second one is a
671 shadow which must follow a specific number of cycles after I1; its only
672 purpose is to show the side effect that occurs at that cycle in the RTL.
673 If a JUMP_INSN or a CALL_INSN has been split, I1 should be a normal INSN,
674 while I2 retains the original insn type.
676 There are two ways in which the number of cycles can be specified,
677 involving the CYCLES and STAGES arguments to this function. If STAGES
678 is zero, we just use the value of CYCLES. Otherwise, STAGES is a factor
679 which is multiplied by MODULO_II to give the number of cycles. This is
680 only useful if the caller also calls set_modulo_params to enable modulo
684 record_delay_slot_pair (rtx i1
, rtx i2
, int cycles
, int stages
)
686 struct delay_pair
*p
= XNEW (struct delay_pair
);
687 struct delay_pair
**slot
;
696 delay_htab
= htab_create (10, delay_hash_i1
, delay_i1_eq
, NULL
);
697 delay_htab_i2
= htab_create (10, delay_hash_i2
, delay_i2_eq
, free
);
699 slot
= ((struct delay_pair
**)
700 htab_find_slot_with_hash (delay_htab
, i1
, htab_hash_pointer (i1
),
702 p
->next_same_i1
= *slot
;
704 slot
= ((struct delay_pair
**)
705 htab_find_slot_with_hash (delay_htab_i2
, i2
, htab_hash_pointer (i2
),
710 /* Examine the delay pair hashtable to see if INSN is a shadow for another,
711 and return the other insn if so. Return NULL otherwise. */
713 real_insn_for_shadow (rtx insn
)
715 struct delay_pair
*pair
;
717 if (delay_htab
== NULL
)
721 = (struct delay_pair
*)htab_find_with_hash (delay_htab_i2
, insn
,
722 htab_hash_pointer (insn
));
723 if (!pair
|| pair
->stages
> 0)
728 /* For a pair P of insns, return the fixed distance in cycles from the first
729 insn after which the second must be scheduled. */
731 pair_delay (struct delay_pair
*p
)
736 return p
->stages
* modulo_ii
;
739 /* Given an insn INSN, add a dependence on its delayed shadow if it
740 has one. Also try to find situations where shadows depend on each other
741 and add dependencies to the real insns to limit the amount of backtracking
744 add_delay_dependencies (rtx insn
)
746 struct delay_pair
*pair
;
747 sd_iterator_def sd_it
;
754 = (struct delay_pair
*)htab_find_with_hash (delay_htab_i2
, insn
,
755 htab_hash_pointer (insn
));
758 add_dependence (insn
, pair
->i1
, REG_DEP_ANTI
);
762 FOR_EACH_DEP (pair
->i2
, SD_LIST_BACK
, sd_it
, dep
)
764 rtx pro
= DEP_PRO (dep
);
765 struct delay_pair
*other_pair
766 = (struct delay_pair
*)htab_find_with_hash (delay_htab_i2
, pro
,
767 htab_hash_pointer (pro
));
768 if (!other_pair
|| other_pair
->stages
)
770 if (pair_delay (other_pair
) >= pair_delay (pair
))
772 if (sched_verbose
>= 4)
774 fprintf (sched_dump
, ";;\tadding dependence %d <- %d\n",
775 INSN_UID (other_pair
->i1
),
776 INSN_UID (pair
->i1
));
777 fprintf (sched_dump
, ";;\tpair1 %d <- %d, cost %d\n",
781 fprintf (sched_dump
, ";;\tpair2 %d <- %d, cost %d\n",
782 INSN_UID (other_pair
->i1
),
783 INSN_UID (other_pair
->i2
),
784 pair_delay (other_pair
));
786 add_dependence (pair
->i1
, other_pair
->i1
, REG_DEP_ANTI
);
791 /* Forward declarations. */
793 static int priority (rtx
);
794 static int rank_for_schedule (const void *, const void *);
795 static void swap_sort (rtx
*, int);
796 static void queue_insn (rtx
, int, const char *);
797 static int schedule_insn (rtx
);
798 static void adjust_priority (rtx
);
799 static void advance_one_cycle (void);
800 static void extend_h_i_d (void);
803 /* Notes handling mechanism:
804 =========================
805 Generally, NOTES are saved before scheduling and restored after scheduling.
806 The scheduler distinguishes between two types of notes:
808 (1) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes:
809 Before scheduling a region, a pointer to the note is added to the insn
810 that follows or precedes it. (This happens as part of the data dependence
811 computation). After scheduling an insn, the pointer contained in it is
812 used for regenerating the corresponding note (in reemit_notes).
814 (2) All other notes (e.g. INSN_DELETED): Before scheduling a block,
815 these notes are put in a list (in rm_other_notes() and
816 unlink_other_notes ()). After scheduling the block, these notes are
817 inserted at the beginning of the block (in schedule_block()). */
819 static void ready_add (struct ready_list
*, rtx
, bool);
820 static rtx
ready_remove_first (struct ready_list
*);
821 static rtx
ready_remove_first_dispatch (struct ready_list
*ready
);
823 static void queue_to_ready (struct ready_list
*);
824 static int early_queue_to_ready (state_t
, struct ready_list
*);
826 static void debug_ready_list (struct ready_list
*);
828 /* The following functions are used to implement multi-pass scheduling
829 on the first cycle. */
830 static rtx
ready_remove (struct ready_list
*, int);
831 static void ready_remove_insn (rtx
);
833 static void fix_inter_tick (rtx
, rtx
);
834 static int fix_tick_ready (rtx
);
835 static void change_queue_index (rtx
, int);
837 /* The following functions are used to implement scheduling of data/control
838 speculative instructions. */
840 static void extend_h_i_d (void);
841 static void init_h_i_d (rtx
);
842 static int haifa_speculate_insn (rtx
, ds_t
, rtx
*);
843 static void generate_recovery_code (rtx
);
844 static void process_insn_forw_deps_be_in_spec (rtx
, rtx
, ds_t
);
845 static void begin_speculative_block (rtx
);
846 static void add_to_speculative_block (rtx
);
847 static void init_before_recovery (basic_block
*);
848 static void create_check_block_twin (rtx
, bool);
849 static void fix_recovery_deps (basic_block
);
850 static bool haifa_change_pattern (rtx
, rtx
);
851 static void dump_new_block_header (int, basic_block
, rtx
, rtx
);
852 static void restore_bb_notes (basic_block
);
853 static void fix_jump_move (rtx
);
854 static void move_block_after_check (rtx
);
855 static void move_succs (VEC(edge
,gc
) **, basic_block
);
856 static void sched_remove_insn (rtx
);
857 static void clear_priorities (rtx
, rtx_vec_t
*);
858 static void calc_priorities (rtx_vec_t
);
859 static void add_jump_dependencies (rtx
, rtx
);
861 #endif /* INSN_SCHEDULING */
863 /* Point to state used for the current scheduling pass. */
864 struct haifa_sched_info
*current_sched_info
;
866 #ifndef INSN_SCHEDULING
868 schedule_insns (void)
873 /* Do register pressure sensitive insn scheduling if the flag is set
875 bool sched_pressure_p
;
877 /* Map regno -> its pressure class. The map defined only when
878 SCHED_PRESSURE_P is true. */
879 enum reg_class
*sched_regno_pressure_class
;
881 /* The current register pressure. Only elements corresponding pressure
882 classes are defined. */
883 static int curr_reg_pressure
[N_REG_CLASSES
];
885 /* Saved value of the previous array. */
886 static int saved_reg_pressure
[N_REG_CLASSES
];
888 /* Register living at given scheduling point. */
889 static bitmap curr_reg_live
;
891 /* Saved value of the previous array. */
892 static bitmap saved_reg_live
;
894 /* Registers mentioned in the current region. */
895 static bitmap region_ref_regs
;
897 /* Initiate register pressure relative info for scheduling the current
898 region. Currently it is only clearing register mentioned in the
901 sched_init_region_reg_pressure_info (void)
903 bitmap_clear (region_ref_regs
);
906 /* Update current register pressure related info after birth (if
907 BIRTH_P) or death of register REGNO. */
909 mark_regno_birth_or_death (int regno
, bool birth_p
)
911 enum reg_class pressure_class
;
913 pressure_class
= sched_regno_pressure_class
[regno
];
914 if (regno
>= FIRST_PSEUDO_REGISTER
)
916 if (pressure_class
!= NO_REGS
)
920 bitmap_set_bit (curr_reg_live
, regno
);
921 curr_reg_pressure
[pressure_class
]
922 += (ira_reg_class_max_nregs
923 [pressure_class
][PSEUDO_REGNO_MODE (regno
)]);
927 bitmap_clear_bit (curr_reg_live
, regno
);
928 curr_reg_pressure
[pressure_class
]
929 -= (ira_reg_class_max_nregs
930 [pressure_class
][PSEUDO_REGNO_MODE (regno
)]);
934 else if (pressure_class
!= NO_REGS
935 && ! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
))
939 bitmap_set_bit (curr_reg_live
, regno
);
940 curr_reg_pressure
[pressure_class
]++;
944 bitmap_clear_bit (curr_reg_live
, regno
);
945 curr_reg_pressure
[pressure_class
]--;
950 /* Initiate current register pressure related info from living
951 registers given by LIVE. */
953 initiate_reg_pressure_info (bitmap live
)
959 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
960 curr_reg_pressure
[ira_pressure_classes
[i
]] = 0;
961 bitmap_clear (curr_reg_live
);
962 EXECUTE_IF_SET_IN_BITMAP (live
, 0, j
, bi
)
963 if (current_nr_blocks
== 1 || bitmap_bit_p (region_ref_regs
, j
))
964 mark_regno_birth_or_death (j
, true);
967 /* Mark registers in X as mentioned in the current region. */
969 setup_ref_regs (rtx x
)
972 const RTX_CODE code
= GET_CODE (x
);
978 if (HARD_REGISTER_NUM_P (regno
))
979 bitmap_set_range (region_ref_regs
, regno
,
980 hard_regno_nregs
[regno
][GET_MODE (x
)]);
982 bitmap_set_bit (region_ref_regs
, REGNO (x
));
985 fmt
= GET_RTX_FORMAT (code
);
986 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
988 setup_ref_regs (XEXP (x
, i
));
989 else if (fmt
[i
] == 'E')
991 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
992 setup_ref_regs (XVECEXP (x
, i
, j
));
996 /* Initiate current register pressure related info at the start of
999 initiate_bb_reg_pressure_info (basic_block bb
)
1001 unsigned int i ATTRIBUTE_UNUSED
;
1004 if (current_nr_blocks
> 1)
1005 FOR_BB_INSNS (bb
, insn
)
1006 if (NONDEBUG_INSN_P (insn
))
1007 setup_ref_regs (PATTERN (insn
));
1008 initiate_reg_pressure_info (df_get_live_in (bb
));
1009 #ifdef EH_RETURN_DATA_REGNO
1010 if (bb_has_eh_pred (bb
))
1013 unsigned int regno
= EH_RETURN_DATA_REGNO (i
);
1015 if (regno
== INVALID_REGNUM
)
1017 if (! bitmap_bit_p (df_get_live_in (bb
), regno
))
1018 mark_regno_birth_or_death (regno
, true);
1023 /* Save current register pressure related info. */
1025 save_reg_pressure (void)
1029 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1030 saved_reg_pressure
[ira_pressure_classes
[i
]]
1031 = curr_reg_pressure
[ira_pressure_classes
[i
]];
1032 bitmap_copy (saved_reg_live
, curr_reg_live
);
1035 /* Restore saved register pressure related info. */
1037 restore_reg_pressure (void)
1041 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1042 curr_reg_pressure
[ira_pressure_classes
[i
]]
1043 = saved_reg_pressure
[ira_pressure_classes
[i
]];
1044 bitmap_copy (curr_reg_live
, saved_reg_live
);
1047 /* Return TRUE if the register is dying after its USE. */
1049 dying_use_p (struct reg_use_data
*use
)
1051 struct reg_use_data
*next
;
1053 for (next
= use
->next_regno_use
; next
!= use
; next
= next
->next_regno_use
)
1054 if (NONDEBUG_INSN_P (next
->insn
)
1055 && QUEUE_INDEX (next
->insn
) != QUEUE_SCHEDULED
)
1060 /* Print info about the current register pressure and its excess for
1061 each pressure class. */
1063 print_curr_reg_pressure (void)
1068 fprintf (sched_dump
, ";;\t");
1069 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1071 cl
= ira_pressure_classes
[i
];
1072 gcc_assert (curr_reg_pressure
[cl
] >= 0);
1073 fprintf (sched_dump
, " %s:%d(%d)", reg_class_names
[cl
],
1074 curr_reg_pressure
[cl
],
1075 curr_reg_pressure
[cl
] - ira_available_class_regs
[cl
]);
1077 fprintf (sched_dump
, "\n");
1080 /* Determine if INSN has a condition that is clobbered if a register
1081 in SET_REGS is modified. */
1083 cond_clobbered_p (rtx insn
, HARD_REG_SET set_regs
)
1085 rtx pat
= PATTERN (insn
);
1086 gcc_assert (GET_CODE (pat
) == COND_EXEC
);
1087 if (TEST_HARD_REG_BIT (set_regs
, REGNO (XEXP (COND_EXEC_TEST (pat
), 0))))
1089 sd_iterator_def sd_it
;
1091 haifa_change_pattern (insn
, ORIG_PAT (insn
));
1092 FOR_EACH_DEP (insn
, SD_LIST_BACK
, sd_it
, dep
)
1093 DEP_STATUS (dep
) &= ~DEP_CANCELLED
;
1094 TODO_SPEC (insn
) = HARD_DEP
;
1095 if (sched_verbose
>= 2)
1096 fprintf (sched_dump
,
1097 ";;\t\tdequeue insn %s because of clobbered condition\n",
1098 (*current_sched_info
->print_insn
) (insn
, 0));
1105 /* Look at the remaining dependencies for insn NEXT, and compute and return
1106 the TODO_SPEC value we should use for it. This is called after one of
1107 NEXT's dependencies has been resolved. */
1110 recompute_todo_spec (rtx next
)
1113 sd_iterator_def sd_it
;
1114 dep_t dep
, control_dep
= NULL
;
1117 bool first_p
= true;
1119 if (sd_lists_empty_p (next
, SD_LIST_BACK
))
1120 /* NEXT has all its dependencies resolved. */
1123 if (!sd_lists_empty_p (next
, SD_LIST_HARD_BACK
))
1126 /* Now we've got NEXT with speculative deps only.
1127 1. Look at the deps to see what we have to do.
1128 2. Check if we can do 'todo'. */
1131 FOR_EACH_DEP (next
, SD_LIST_BACK
, sd_it
, dep
)
1133 ds_t ds
= DEP_STATUS (dep
) & SPECULATIVE
;
1135 if (DEBUG_INSN_P (DEP_PRO (dep
)) && !DEBUG_INSN_P (next
))
1148 new_ds
= ds_merge (new_ds
, ds
);
1150 if (DEP_TYPE (dep
) == REG_DEP_CONTROL
)
1154 DEP_STATUS (dep
) &= ~DEP_CANCELLED
;
1158 if (n_control
== 1 && n_spec
== 0)
1160 rtx pro
, other
, new_pat
;
1161 rtx cond
= NULL_RTX
;
1163 rtx prev
= NULL_RTX
;
1167 if ((current_sched_info
->flags
& DO_PREDICATION
) == 0
1168 || (ORIG_PAT (next
) != NULL_RTX
1169 && PREDICATED_PAT (next
) == NULL_RTX
))
1172 pro
= DEP_PRO (control_dep
);
1173 other
= real_insn_for_shadow (pro
);
1174 if (other
!= NULL_RTX
)
1177 cond
= sched_get_reverse_condition_uncached (pro
);
1178 regno
= REGNO (XEXP (cond
, 0));
1180 /* Find the last scheduled insn that modifies the condition register.
1181 We can stop looking once we find the insn we depend on through the
1182 REG_DEP_CONTROL; if the condition register isn't modified after it,
1183 we know that it still has the right value. */
1184 if (QUEUE_INDEX (pro
) == QUEUE_SCHEDULED
)
1185 FOR_EACH_VEC_ELT_REVERSE (rtx
, scheduled_insns
, i
, prev
)
1189 find_all_hard_reg_sets (prev
, &t
);
1190 if (TEST_HARD_REG_BIT (t
, regno
))
1195 if (ORIG_PAT (next
) == NULL_RTX
)
1197 ORIG_PAT (next
) = PATTERN (next
);
1199 new_pat
= gen_rtx_COND_EXEC (VOIDmode
, cond
, PATTERN (next
));
1200 success
= haifa_change_pattern (next
, new_pat
);
1203 PREDICATED_PAT (next
) = new_pat
;
1205 else if (PATTERN (next
) != PREDICATED_PAT (next
))
1207 bool success
= haifa_change_pattern (next
,
1208 PREDICATED_PAT (next
));
1209 gcc_assert (success
);
1211 DEP_STATUS (control_dep
) |= DEP_CANCELLED
;
1215 if (PREDICATED_PAT (next
) != NULL_RTX
)
1217 int tick
= INSN_TICK (next
);
1218 bool success
= haifa_change_pattern (next
,
1220 INSN_TICK (next
) = tick
;
1221 gcc_assert (success
);
1224 /* We can't handle the case where there are both speculative and control
1225 dependencies, so we return HARD_DEP in such a case. Also fail if
1226 we have speculative dependencies with not enough points, or more than
1227 one control dependency. */
1228 if ((n_spec
> 0 && n_control
> 0)
1230 /* Too few points? */
1231 && ds_weak (new_ds
) < spec_info
->data_weakness_cutoff
)
1238 /* Pointer to the last instruction scheduled. */
1239 static rtx last_scheduled_insn
;
1241 /* Pointer to the last nondebug instruction scheduled within the
1242 block, or the prev_head of the scheduling block. Used by
1243 rank_for_schedule, so that insns independent of the last scheduled
1244 insn will be preferred over dependent instructions. */
1245 static rtx last_nondebug_scheduled_insn
;
1247 /* Pointer that iterates through the list of unscheduled insns if we
1248 have a dbg_cnt enabled. It always points at an insn prior to the
1249 first unscheduled one. */
1250 static rtx nonscheduled_insns_begin
;
1252 /* Cached cost of the instruction. Use below function to get cost of the
1253 insn. -1 here means that the field is not initialized. */
1254 #define INSN_COST(INSN) (HID (INSN)->cost)
1256 /* Compute cost of executing INSN.
1257 This is the number of cycles between instruction issue and
1258 instruction results. */
1260 insn_cost (rtx insn
)
1266 if (recog_memoized (insn
) < 0)
1269 cost
= insn_default_latency (insn
);
1276 cost
= INSN_COST (insn
);
1280 /* A USE insn, or something else we don't need to
1281 understand. We can't pass these directly to
1282 result_ready_cost or insn_default_latency because it will
1283 trigger a fatal error for unrecognizable insns. */
1284 if (recog_memoized (insn
) < 0)
1286 INSN_COST (insn
) = 0;
1291 cost
= insn_default_latency (insn
);
1295 INSN_COST (insn
) = cost
;
1302 /* Compute cost of dependence LINK.
1303 This is the number of cycles between instruction issue and
1304 instruction results.
1305 ??? We also use this function to call recog_memoized on all insns. */
1307 dep_cost_1 (dep_t link
, dw_t dw
)
1309 rtx insn
= DEP_PRO (link
);
1310 rtx used
= DEP_CON (link
);
1313 if (DEP_COST (link
) != UNKNOWN_DEP_COST
)
1314 return DEP_COST (link
);
1318 struct delay_pair
*delay_entry
;
1320 = (struct delay_pair
*)htab_find_with_hash (delay_htab_i2
, used
,
1321 htab_hash_pointer (used
));
1324 if (delay_entry
->i1
== insn
)
1326 DEP_COST (link
) = pair_delay (delay_entry
);
1327 return DEP_COST (link
);
1332 /* A USE insn should never require the value used to be computed.
1333 This allows the computation of a function's result and parameter
1334 values to overlap the return and call. We don't care about the
1335 dependence cost when only decreasing register pressure. */
1336 if (recog_memoized (used
) < 0)
1339 recog_memoized (insn
);
1343 enum reg_note dep_type
= DEP_TYPE (link
);
1345 cost
= insn_cost (insn
);
1347 if (INSN_CODE (insn
) >= 0)
1349 if (dep_type
== REG_DEP_ANTI
)
1351 else if (dep_type
== REG_DEP_OUTPUT
)
1353 cost
= (insn_default_latency (insn
)
1354 - insn_default_latency (used
));
1358 else if (bypass_p (insn
))
1359 cost
= insn_latency (insn
, used
);
1363 if (targetm
.sched
.adjust_cost_2
)
1364 cost
= targetm
.sched
.adjust_cost_2 (used
, (int) dep_type
, insn
, cost
,
1366 else if (targetm
.sched
.adjust_cost
!= NULL
)
1368 /* This variable is used for backward compatibility with the
1370 rtx dep_cost_rtx_link
= alloc_INSN_LIST (NULL_RTX
, NULL_RTX
);
1372 /* Make it self-cycled, so that if some tries to walk over this
1373 incomplete list he/she will be caught in an endless loop. */
1374 XEXP (dep_cost_rtx_link
, 1) = dep_cost_rtx_link
;
1376 /* Targets use only REG_NOTE_KIND of the link. */
1377 PUT_REG_NOTE_KIND (dep_cost_rtx_link
, DEP_TYPE (link
));
1379 cost
= targetm
.sched
.adjust_cost (used
, dep_cost_rtx_link
,
1382 free_INSN_LIST_node (dep_cost_rtx_link
);
1389 DEP_COST (link
) = cost
;
1393 /* Compute cost of dependence LINK.
1394 This is the number of cycles between instruction issue and
1395 instruction results. */
1397 dep_cost (dep_t link
)
1399 return dep_cost_1 (link
, 0);
1402 /* Use this sel-sched.c friendly function in reorder2 instead of increasing
1403 INSN_PRIORITY explicitly. */
1405 increase_insn_priority (rtx insn
, int amount
)
1407 if (!sel_sched_p ())
1409 /* We're dealing with haifa-sched.c INSN_PRIORITY. */
1410 if (INSN_PRIORITY_KNOWN (insn
))
1411 INSN_PRIORITY (insn
) += amount
;
1415 /* In sel-sched.c INSN_PRIORITY is not kept up to date.
1416 Use EXPR_PRIORITY instead. */
1417 sel_add_to_insn_priority (insn
, amount
);
1421 /* Return 'true' if DEP should be included in priority calculations. */
1423 contributes_to_priority_p (dep_t dep
)
1425 if (DEBUG_INSN_P (DEP_CON (dep
))
1426 || DEBUG_INSN_P (DEP_PRO (dep
)))
1429 /* Critical path is meaningful in block boundaries only. */
1430 if (!current_sched_info
->contributes_to_priority (DEP_CON (dep
),
1434 /* If flag COUNT_SPEC_IN_CRITICAL_PATH is set,
1435 then speculative instructions will less likely be
1436 scheduled. That is because the priority of
1437 their producers will increase, and, thus, the
1438 producers will more likely be scheduled, thus,
1439 resolving the dependence. */
1440 if (sched_deps_info
->generate_spec_deps
1441 && !(spec_info
->flags
& COUNT_SPEC_IN_CRITICAL_PATH
)
1442 && (DEP_STATUS (dep
) & SPECULATIVE
))
1448 /* Compute the number of nondebug forward deps of an insn. */
1451 dep_list_size (rtx insn
)
1453 sd_iterator_def sd_it
;
1455 int dbgcount
= 0, nodbgcount
= 0;
1457 if (!MAY_HAVE_DEBUG_INSNS
)
1458 return sd_lists_size (insn
, SD_LIST_FORW
);
1460 FOR_EACH_DEP (insn
, SD_LIST_FORW
, sd_it
, dep
)
1462 if (DEBUG_INSN_P (DEP_CON (dep
)))
1464 else if (!DEBUG_INSN_P (DEP_PRO (dep
)))
1468 gcc_assert (dbgcount
+ nodbgcount
== sd_lists_size (insn
, SD_LIST_FORW
));
1473 /* Compute the priority number for INSN. */
1477 if (! INSN_P (insn
))
1480 /* We should not be interested in priority of an already scheduled insn. */
1481 gcc_assert (QUEUE_INDEX (insn
) != QUEUE_SCHEDULED
);
1483 if (!INSN_PRIORITY_KNOWN (insn
))
1485 int this_priority
= -1;
1487 if (dep_list_size (insn
) == 0)
1488 /* ??? We should set INSN_PRIORITY to insn_cost when and insn has
1489 some forward deps but all of them are ignored by
1490 contributes_to_priority hook. At the moment we set priority of
1492 this_priority
= insn_cost (insn
);
1495 rtx prev_first
, twin
;
1498 /* For recovery check instructions we calculate priority slightly
1499 different than that of normal instructions. Instead of walking
1500 through INSN_FORW_DEPS (check) list, we walk through
1501 INSN_FORW_DEPS list of each instruction in the corresponding
1504 /* Selective scheduling does not define RECOVERY_BLOCK macro. */
1505 rec
= sel_sched_p () ? NULL
: RECOVERY_BLOCK (insn
);
1506 if (!rec
|| rec
== EXIT_BLOCK_PTR
)
1508 prev_first
= PREV_INSN (insn
);
1513 prev_first
= NEXT_INSN (BB_HEAD (rec
));
1514 twin
= PREV_INSN (BB_END (rec
));
1519 sd_iterator_def sd_it
;
1522 FOR_EACH_DEP (twin
, SD_LIST_FORW
, sd_it
, dep
)
1527 next
= DEP_CON (dep
);
1529 if (BLOCK_FOR_INSN (next
) != rec
)
1533 if (!contributes_to_priority_p (dep
))
1537 cost
= dep_cost (dep
);
1540 struct _dep _dep1
, *dep1
= &_dep1
;
1542 init_dep (dep1
, insn
, next
, REG_DEP_ANTI
);
1544 cost
= dep_cost (dep1
);
1547 next_priority
= cost
+ priority (next
);
1549 if (next_priority
> this_priority
)
1550 this_priority
= next_priority
;
1554 twin
= PREV_INSN (twin
);
1556 while (twin
!= prev_first
);
1559 if (this_priority
< 0)
1561 gcc_assert (this_priority
== -1);
1563 this_priority
= insn_cost (insn
);
1566 INSN_PRIORITY (insn
) = this_priority
;
1567 INSN_PRIORITY_STATUS (insn
) = 1;
1570 return INSN_PRIORITY (insn
);
1573 /* Macros and functions for keeping the priority queue sorted, and
1574 dealing with queuing and dequeuing of instructions. */
1576 #define SCHED_SORT(READY, N_READY) \
1577 do { if ((N_READY) == 2) \
1578 swap_sort (READY, N_READY); \
1579 else if ((N_READY) > 2) \
1580 qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \
1583 /* Setup info about the current register pressure impact of scheduling
1584 INSN at the current scheduling point. */
1586 setup_insn_reg_pressure_info (rtx insn
)
1588 int i
, change
, before
, after
, hard_regno
;
1589 int excess_cost_change
;
1590 enum machine_mode mode
;
1592 struct reg_pressure_data
*pressure_info
;
1593 int *max_reg_pressure
;
1594 struct reg_use_data
*use
;
1595 static int death
[N_REG_CLASSES
];
1597 gcc_checking_assert (!DEBUG_INSN_P (insn
));
1599 excess_cost_change
= 0;
1600 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1601 death
[ira_pressure_classes
[i
]] = 0;
1602 for (use
= INSN_REG_USE_LIST (insn
); use
!= NULL
; use
= use
->next_insn_use
)
1603 if (dying_use_p (use
))
1605 cl
= sched_regno_pressure_class
[use
->regno
];
1606 if (use
->regno
< FIRST_PSEUDO_REGISTER
)
1610 += ira_reg_class_max_nregs
[cl
][PSEUDO_REGNO_MODE (use
->regno
)];
1612 pressure_info
= INSN_REG_PRESSURE (insn
);
1613 max_reg_pressure
= INSN_MAX_REG_PRESSURE (insn
);
1614 gcc_assert (pressure_info
!= NULL
&& max_reg_pressure
!= NULL
);
1615 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1617 cl
= ira_pressure_classes
[i
];
1618 gcc_assert (curr_reg_pressure
[cl
] >= 0);
1619 change
= (int) pressure_info
[i
].set_increase
- death
[cl
];
1620 before
= MAX (0, max_reg_pressure
[i
] - ira_available_class_regs
[cl
]);
1621 after
= MAX (0, max_reg_pressure
[i
] + change
1622 - ira_available_class_regs
[cl
]);
1623 hard_regno
= ira_class_hard_regs
[cl
][0];
1624 gcc_assert (hard_regno
>= 0);
1625 mode
= reg_raw_mode
[hard_regno
];
1626 excess_cost_change
+= ((after
- before
)
1627 * (ira_memory_move_cost
[mode
][cl
][0]
1628 + ira_memory_move_cost
[mode
][cl
][1]));
1630 INSN_REG_PRESSURE_EXCESS_COST_CHANGE (insn
) = excess_cost_change
;
1633 /* Returns a positive value if x is preferred; returns a negative value if
1634 y is preferred. Should never return 0, since that will make the sort
1638 rank_for_schedule (const void *x
, const void *y
)
1640 rtx tmp
= *(const rtx
*) y
;
1641 rtx tmp2
= *(const rtx
*) x
;
1642 int tmp_class
, tmp2_class
;
1643 int val
, priority_val
, info_val
;
1645 if (MAY_HAVE_DEBUG_INSNS
)
1647 /* Schedule debug insns as early as possible. */
1648 if (DEBUG_INSN_P (tmp
) && !DEBUG_INSN_P (tmp2
))
1650 else if (DEBUG_INSN_P (tmp2
))
1654 /* The insn in a schedule group should be issued the first. */
1655 if (flag_sched_group_heuristic
&&
1656 SCHED_GROUP_P (tmp
) != SCHED_GROUP_P (tmp2
))
1657 return SCHED_GROUP_P (tmp2
) ? 1 : -1;
1659 /* Make sure that priority of TMP and TMP2 are initialized. */
1660 gcc_assert (INSN_PRIORITY_KNOWN (tmp
) && INSN_PRIORITY_KNOWN (tmp2
));
1662 if (sched_pressure_p
)
1666 /* Prefer insn whose scheduling results in the smallest register
1668 if ((diff
= (INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp
)
1669 + (INSN_TICK (tmp
) > clock_var
1670 ? INSN_TICK (tmp
) - clock_var
: 0)
1671 - INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp2
)
1672 - (INSN_TICK (tmp2
) > clock_var
1673 ? INSN_TICK (tmp2
) - clock_var
: 0))) != 0)
1678 if (sched_pressure_p
1679 && (INSN_TICK (tmp2
) > clock_var
|| INSN_TICK (tmp
) > clock_var
))
1681 if (INSN_TICK (tmp
) <= clock_var
)
1683 else if (INSN_TICK (tmp2
) <= clock_var
)
1686 return INSN_TICK (tmp
) - INSN_TICK (tmp2
);
1689 /* If we are doing backtracking in this schedule, prefer insns that
1690 have forward dependencies with negative cost against an insn that
1691 was already scheduled. */
1692 if (current_sched_info
->flags
& DO_BACKTRACKING
)
1694 priority_val
= FEEDS_BACKTRACK_INSN (tmp2
) - FEEDS_BACKTRACK_INSN (tmp
);
1696 return priority_val
;
1699 /* Prefer insn with higher priority. */
1700 priority_val
= INSN_PRIORITY (tmp2
) - INSN_PRIORITY (tmp
);
1702 if (flag_sched_critical_path_heuristic
&& priority_val
)
1703 return priority_val
;
1705 /* Prefer speculative insn with greater dependencies weakness. */
1706 if (flag_sched_spec_insn_heuristic
&& spec_info
)
1712 ds1
= TODO_SPEC (tmp
) & SPECULATIVE
;
1714 dw1
= ds_weak (ds1
);
1718 ds2
= TODO_SPEC (tmp2
) & SPECULATIVE
;
1720 dw2
= ds_weak (ds2
);
1725 if (dw
> (NO_DEP_WEAK
/ 8) || dw
< -(NO_DEP_WEAK
/ 8))
1729 info_val
= (*current_sched_info
->rank
) (tmp
, tmp2
);
1730 if(flag_sched_rank_heuristic
&& info_val
)
1733 /* Compare insns based on their relation to the last scheduled
1735 if (flag_sched_last_insn_heuristic
&& last_nondebug_scheduled_insn
)
1739 rtx last
= last_nondebug_scheduled_insn
;
1741 /* Classify the instructions into three classes:
1742 1) Data dependent on last schedule insn.
1743 2) Anti/Output dependent on last scheduled insn.
1744 3) Independent of last scheduled insn, or has latency of one.
1745 Choose the insn from the highest numbered class if different. */
1746 dep1
= sd_find_dep_between (last
, tmp
, true);
1748 if (dep1
== NULL
|| dep_cost (dep1
) == 1)
1750 else if (/* Data dependence. */
1751 DEP_TYPE (dep1
) == REG_DEP_TRUE
)
1756 dep2
= sd_find_dep_between (last
, tmp2
, true);
1758 if (dep2
== NULL
|| dep_cost (dep2
) == 1)
1760 else if (/* Data dependence. */
1761 DEP_TYPE (dep2
) == REG_DEP_TRUE
)
1766 if ((val
= tmp2_class
- tmp_class
))
1770 /* Prefer the insn which has more later insns that depend on it.
1771 This gives the scheduler more freedom when scheduling later
1772 instructions at the expense of added register pressure. */
1774 val
= (dep_list_size (tmp2
) - dep_list_size (tmp
));
1776 if (flag_sched_dep_count_heuristic
&& val
!= 0)
1779 /* If insns are equally good, sort by INSN_LUID (original insn order),
1780 so that we make the sort stable. This minimizes instruction movement,
1781 thus minimizing sched's effect on debugging and cross-jumping. */
1782 return INSN_LUID (tmp
) - INSN_LUID (tmp2
);
1785 /* Resort the array A in which only element at index N may be out of order. */
1787 HAIFA_INLINE
static void
1788 swap_sort (rtx
*a
, int n
)
1790 rtx insn
= a
[n
- 1];
1793 while (i
>= 0 && rank_for_schedule (a
+ i
, &insn
) >= 0)
1801 /* Add INSN to the insn queue so that it can be executed at least
1802 N_CYCLES after the currently executing insn. Preserve insns
1803 chain for debugging purposes. REASON will be printed in debugging
1806 HAIFA_INLINE
static void
1807 queue_insn (rtx insn
, int n_cycles
, const char *reason
)
1809 int next_q
= NEXT_Q_AFTER (q_ptr
, n_cycles
);
1810 rtx link
= alloc_INSN_LIST (insn
, insn_queue
[next_q
]);
1813 gcc_assert (n_cycles
<= max_insn_queue_index
);
1814 gcc_assert (!DEBUG_INSN_P (insn
));
1816 insn_queue
[next_q
] = link
;
1819 if (sched_verbose
>= 2)
1821 fprintf (sched_dump
, ";;\t\tReady-->Q: insn %s: ",
1822 (*current_sched_info
->print_insn
) (insn
, 0));
1824 fprintf (sched_dump
, "queued for %d cycles (%s).\n", n_cycles
, reason
);
1827 QUEUE_INDEX (insn
) = next_q
;
1829 if (current_sched_info
->flags
& DO_BACKTRACKING
)
1831 new_tick
= clock_var
+ n_cycles
;
1832 if (INSN_TICK (insn
) == INVALID_TICK
|| INSN_TICK (insn
) < new_tick
)
1833 INSN_TICK (insn
) = new_tick
;
1835 if (INSN_EXACT_TICK (insn
) != INVALID_TICK
1836 && INSN_EXACT_TICK (insn
) < clock_var
+ n_cycles
)
1838 must_backtrack
= true;
1839 if (sched_verbose
>= 2)
1840 fprintf (sched_dump
, ";;\t\tcausing a backtrack.\n");
1845 /* Remove INSN from queue. */
1847 queue_remove (rtx insn
)
1849 gcc_assert (QUEUE_INDEX (insn
) >= 0);
1850 remove_free_INSN_LIST_elem (insn
, &insn_queue
[QUEUE_INDEX (insn
)]);
1852 QUEUE_INDEX (insn
) = QUEUE_NOWHERE
;
1855 /* Return a pointer to the bottom of the ready list, i.e. the insn
1856 with the lowest priority. */
1859 ready_lastpos (struct ready_list
*ready
)
1861 gcc_assert (ready
->n_ready
>= 1);
1862 return ready
->vec
+ ready
->first
- ready
->n_ready
+ 1;
1865 /* Add an element INSN to the ready list so that it ends up with the
1866 lowest/highest priority depending on FIRST_P. */
1868 HAIFA_INLINE
static void
1869 ready_add (struct ready_list
*ready
, rtx insn
, bool first_p
)
1873 if (ready
->first
== ready
->n_ready
)
1875 memmove (ready
->vec
+ ready
->veclen
- ready
->n_ready
,
1876 ready_lastpos (ready
),
1877 ready
->n_ready
* sizeof (rtx
));
1878 ready
->first
= ready
->veclen
- 1;
1880 ready
->vec
[ready
->first
- ready
->n_ready
] = insn
;
1884 if (ready
->first
== ready
->veclen
- 1)
1887 /* ready_lastpos() fails when called with (ready->n_ready == 0). */
1888 memmove (ready
->vec
+ ready
->veclen
- ready
->n_ready
- 1,
1889 ready_lastpos (ready
),
1890 ready
->n_ready
* sizeof (rtx
));
1891 ready
->first
= ready
->veclen
- 2;
1893 ready
->vec
[++(ready
->first
)] = insn
;
1897 if (DEBUG_INSN_P (insn
))
1900 gcc_assert (QUEUE_INDEX (insn
) != QUEUE_READY
);
1901 QUEUE_INDEX (insn
) = QUEUE_READY
;
1903 if (INSN_EXACT_TICK (insn
) != INVALID_TICK
1904 && INSN_EXACT_TICK (insn
) < clock_var
)
1906 must_backtrack
= true;
1910 /* Remove the element with the highest priority from the ready list and
1913 HAIFA_INLINE
static rtx
1914 ready_remove_first (struct ready_list
*ready
)
1918 gcc_assert (ready
->n_ready
);
1919 t
= ready
->vec
[ready
->first
--];
1921 if (DEBUG_INSN_P (t
))
1923 /* If the queue becomes empty, reset it. */
1924 if (ready
->n_ready
== 0)
1925 ready
->first
= ready
->veclen
- 1;
1927 gcc_assert (QUEUE_INDEX (t
) == QUEUE_READY
);
1928 QUEUE_INDEX (t
) = QUEUE_NOWHERE
;
1933 /* The following code implements multi-pass scheduling for the first
1934 cycle. In other words, we will try to choose ready insn which
1935 permits to start maximum number of insns on the same cycle. */
1937 /* Return a pointer to the element INDEX from the ready. INDEX for
1938 insn with the highest priority is 0, and the lowest priority has
1942 ready_element (struct ready_list
*ready
, int index
)
1944 gcc_assert (ready
->n_ready
&& index
< ready
->n_ready
);
1946 return ready
->vec
[ready
->first
- index
];
1949 /* Remove the element INDEX from the ready list and return it. INDEX
1950 for insn with the highest priority is 0, and the lowest priority
1953 HAIFA_INLINE
static rtx
1954 ready_remove (struct ready_list
*ready
, int index
)
1960 return ready_remove_first (ready
);
1961 gcc_assert (ready
->n_ready
&& index
< ready
->n_ready
);
1962 t
= ready
->vec
[ready
->first
- index
];
1964 if (DEBUG_INSN_P (t
))
1966 for (i
= index
; i
< ready
->n_ready
; i
++)
1967 ready
->vec
[ready
->first
- i
] = ready
->vec
[ready
->first
- i
- 1];
1968 QUEUE_INDEX (t
) = QUEUE_NOWHERE
;
1972 /* Remove INSN from the ready list. */
1974 ready_remove_insn (rtx insn
)
1978 for (i
= 0; i
< readyp
->n_ready
; i
++)
1979 if (ready_element (readyp
, i
) == insn
)
1981 ready_remove (readyp
, i
);
1987 /* Sort the ready list READY by ascending priority, using the SCHED_SORT
1991 ready_sort (struct ready_list
*ready
)
1994 rtx
*first
= ready_lastpos (ready
);
1996 if (sched_pressure_p
)
1998 for (i
= 0; i
< ready
->n_ready
; i
++)
1999 if (!DEBUG_INSN_P (first
[i
]))
2000 setup_insn_reg_pressure_info (first
[i
]);
2002 SCHED_SORT (first
, ready
->n_ready
);
2005 /* PREV is an insn that is ready to execute. Adjust its priority if that
2006 will help shorten or lengthen register lifetimes as appropriate. Also
2007 provide a hook for the target to tweak itself. */
2009 HAIFA_INLINE
static void
2010 adjust_priority (rtx prev
)
2012 /* ??? There used to be code here to try and estimate how an insn
2013 affected register lifetimes, but it did it by looking at REG_DEAD
2014 notes, which we removed in schedule_region. Nor did it try to
2015 take into account register pressure or anything useful like that.
2017 Revisit when we have a machine model to work with and not before. */
2019 if (targetm
.sched
.adjust_priority
)
2020 INSN_PRIORITY (prev
) =
2021 targetm
.sched
.adjust_priority (prev
, INSN_PRIORITY (prev
));
2024 /* Advance DFA state STATE on one cycle. */
2026 advance_state (state_t state
)
2028 if (targetm
.sched
.dfa_pre_advance_cycle
)
2029 targetm
.sched
.dfa_pre_advance_cycle ();
2031 if (targetm
.sched
.dfa_pre_cycle_insn
)
2032 state_transition (state
,
2033 targetm
.sched
.dfa_pre_cycle_insn ());
2035 state_transition (state
, NULL
);
2037 if (targetm
.sched
.dfa_post_cycle_insn
)
2038 state_transition (state
,
2039 targetm
.sched
.dfa_post_cycle_insn ());
2041 if (targetm
.sched
.dfa_post_advance_cycle
)
2042 targetm
.sched
.dfa_post_advance_cycle ();
2045 /* Advance time on one cycle. */
2046 HAIFA_INLINE
static void
2047 advance_one_cycle (void)
2049 advance_state (curr_state
);
2050 if (sched_verbose
>= 6)
2051 fprintf (sched_dump
, ";;\tAdvanced a state.\n");
2054 /* Update register pressure after scheduling INSN. */
2056 update_register_pressure (rtx insn
)
2058 struct reg_use_data
*use
;
2059 struct reg_set_data
*set
;
2061 gcc_checking_assert (!DEBUG_INSN_P (insn
));
2063 for (use
= INSN_REG_USE_LIST (insn
); use
!= NULL
; use
= use
->next_insn_use
)
2064 if (dying_use_p (use
) && bitmap_bit_p (curr_reg_live
, use
->regno
))
2065 mark_regno_birth_or_death (use
->regno
, false);
2066 for (set
= INSN_REG_SET_LIST (insn
); set
!= NULL
; set
= set
->next_insn_set
)
2067 mark_regno_birth_or_death (set
->regno
, true);
2070 /* Set up or update (if UPDATE_P) max register pressure (see its
2071 meaning in sched-int.h::_haifa_insn_data) for all current BB insns
2072 after insn AFTER. */
2074 setup_insn_max_reg_pressure (rtx after
, bool update_p
)
2079 static int max_reg_pressure
[N_REG_CLASSES
];
2081 save_reg_pressure ();
2082 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
2083 max_reg_pressure
[ira_pressure_classes
[i
]]
2084 = curr_reg_pressure
[ira_pressure_classes
[i
]];
2085 for (insn
= NEXT_INSN (after
);
2086 insn
!= NULL_RTX
&& ! BARRIER_P (insn
)
2087 && BLOCK_FOR_INSN (insn
) == BLOCK_FOR_INSN (after
);
2088 insn
= NEXT_INSN (insn
))
2089 if (NONDEBUG_INSN_P (insn
))
2092 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
2094 p
= max_reg_pressure
[ira_pressure_classes
[i
]];
2095 if (INSN_MAX_REG_PRESSURE (insn
)[i
] != p
)
2098 INSN_MAX_REG_PRESSURE (insn
)[i
]
2099 = max_reg_pressure
[ira_pressure_classes
[i
]];
2102 if (update_p
&& eq_p
)
2104 update_register_pressure (insn
);
2105 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
2106 if (max_reg_pressure
[ira_pressure_classes
[i
]]
2107 < curr_reg_pressure
[ira_pressure_classes
[i
]])
2108 max_reg_pressure
[ira_pressure_classes
[i
]]
2109 = curr_reg_pressure
[ira_pressure_classes
[i
]];
2111 restore_reg_pressure ();
2114 /* Update the current register pressure after scheduling INSN. Update
2115 also max register pressure for unscheduled insns of the current
2118 update_reg_and_insn_max_reg_pressure (rtx insn
)
2121 int before
[N_REG_CLASSES
];
2123 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
2124 before
[i
] = curr_reg_pressure
[ira_pressure_classes
[i
]];
2125 update_register_pressure (insn
);
2126 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
2127 if (curr_reg_pressure
[ira_pressure_classes
[i
]] != before
[i
])
2129 if (i
< ira_pressure_classes_num
)
2130 setup_insn_max_reg_pressure (insn
, true);
2133 /* Set up register pressure at the beginning of basic block BB whose
2134 insns starting after insn AFTER. Set up also max register pressure
2135 for all insns of the basic block. */
2137 sched_setup_bb_reg_pressure_info (basic_block bb
, rtx after
)
2139 gcc_assert (sched_pressure_p
);
2140 initiate_bb_reg_pressure_info (bb
);
2141 setup_insn_max_reg_pressure (after
, false);
2144 /* If doing predication while scheduling, verify whether INSN, which
2145 has just been scheduled, clobbers the conditions of any
2146 instructions that must be predicated in order to break their
2147 dependencies. If so, remove them from the queues so that they will
2148 only be scheduled once their control dependency is resolved. */
2151 check_clobbered_conditions (rtx insn
)
2156 if ((current_sched_info
->flags
& DO_PREDICATION
) == 0)
2159 find_all_hard_reg_sets (insn
, &t
);
2162 for (i
= 0; i
< ready
.n_ready
; i
++)
2164 rtx x
= ready_element (&ready
, i
);
2165 if (TODO_SPEC (x
) == DEP_CONTROL
&& cond_clobbered_p (x
, t
))
2167 ready_remove_insn (x
);
2171 for (i
= 0; i
<= max_insn_queue_index
; i
++)
2174 int q
= NEXT_Q_AFTER (q_ptr
, i
);
2177 for (link
= insn_queue
[q
]; link
; link
= XEXP (link
, 1))
2179 rtx x
= XEXP (link
, 0);
2180 if (TODO_SPEC (x
) == DEP_CONTROL
&& cond_clobbered_p (x
, t
))
2189 /* A structure that holds local state for the loop in schedule_block. */
2190 struct sched_block_state
2192 /* True if no real insns have been scheduled in the current cycle. */
2193 bool first_cycle_insn_p
;
2194 /* True if a shadow insn has been scheduled in the current cycle, which
2195 means that no more normal insns can be issued. */
2196 bool shadows_only_p
;
2197 /* True if we're winding down a modulo schedule, which means that we only
2198 issue insns with INSN_EXACT_TICK set. */
2199 bool modulo_epilogue
;
2200 /* Initialized with the machine's issue rate every cycle, and updated
2201 by calls to the variable_issue hook. */
2205 /* INSN is the "currently executing insn". Launch each insn which was
2206 waiting on INSN. READY is the ready list which contains the insns
2207 that are ready to fire. CLOCK is the current cycle. The function
2208 returns necessary cycle advance after issuing the insn (it is not
2209 zero for insns in a schedule group). */
2212 schedule_insn (rtx insn
)
2214 sd_iterator_def sd_it
;
2219 if (sched_verbose
>= 1)
2221 struct reg_pressure_data
*pressure_info
;
2224 print_insn (buf
, insn
, 0);
2226 fprintf (sched_dump
, ";;\t%3i--> %-40s:", clock_var
, buf
);
2228 if (recog_memoized (insn
) < 0)
2229 fprintf (sched_dump
, "nothing");
2231 print_reservation (sched_dump
, insn
);
2232 pressure_info
= INSN_REG_PRESSURE (insn
);
2233 if (pressure_info
!= NULL
)
2235 fputc (':', sched_dump
);
2236 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
2237 fprintf (sched_dump
, "%s%+d(%d)",
2238 reg_class_names
[ira_pressure_classes
[i
]],
2239 pressure_info
[i
].set_increase
, pressure_info
[i
].change
);
2241 fputc ('\n', sched_dump
);
2244 if (sched_pressure_p
&& !DEBUG_INSN_P (insn
))
2245 update_reg_and_insn_max_reg_pressure (insn
);
2247 /* Scheduling instruction should have all its dependencies resolved and
2248 should have been removed from the ready list. */
2249 gcc_assert (sd_lists_empty_p (insn
, SD_LIST_HARD_BACK
));
2251 /* Reset debug insns invalidated by moving this insn. */
2252 if (MAY_HAVE_DEBUG_INSNS
&& !DEBUG_INSN_P (insn
))
2253 for (sd_it
= sd_iterator_start (insn
, SD_LIST_BACK
);
2254 sd_iterator_cond (&sd_it
, &dep
);)
2256 rtx dbg
= DEP_PRO (dep
);
2257 struct reg_use_data
*use
, *next
;
2259 if (DEP_STATUS (dep
) & DEP_CANCELLED
)
2261 sd_iterator_next (&sd_it
);
2265 gcc_assert (DEBUG_INSN_P (dbg
));
2267 if (sched_verbose
>= 6)
2268 fprintf (sched_dump
, ";;\t\tresetting: debug insn %d\n",
2271 /* ??? Rather than resetting the debug insn, we might be able
2272 to emit a debug temp before the just-scheduled insn, but
2273 this would involve checking that the expression at the
2274 point of the debug insn is equivalent to the expression
2275 before the just-scheduled insn. They might not be: the
2276 expression in the debug insn may depend on other insns not
2277 yet scheduled that set MEMs, REGs or even other debug
2278 insns. It's not clear that attempting to preserve debug
2279 information in these cases is worth the effort, given how
2280 uncommon these resets are and the likelihood that the debug
2281 temps introduced won't survive the schedule change. */
2282 INSN_VAR_LOCATION_LOC (dbg
) = gen_rtx_UNKNOWN_VAR_LOC ();
2283 df_insn_rescan (dbg
);
2285 /* Unknown location doesn't use any registers. */
2286 for (use
= INSN_REG_USE_LIST (dbg
); use
!= NULL
; use
= next
)
2288 struct reg_use_data
*prev
= use
;
2290 /* Remove use from the cyclic next_regno_use chain first. */
2291 while (prev
->next_regno_use
!= use
)
2292 prev
= prev
->next_regno_use
;
2293 prev
->next_regno_use
= use
->next_regno_use
;
2294 next
= use
->next_insn_use
;
2297 INSN_REG_USE_LIST (dbg
) = NULL
;
2299 /* We delete rather than resolve these deps, otherwise we
2300 crash in sched_free_deps(), because forward deps are
2301 expected to be released before backward deps. */
2302 sd_delete_dep (sd_it
);
2305 gcc_assert (QUEUE_INDEX (insn
) == QUEUE_NOWHERE
);
2306 QUEUE_INDEX (insn
) = QUEUE_SCHEDULED
;
2308 gcc_assert (INSN_TICK (insn
) >= MIN_TICK
);
2309 if (INSN_TICK (insn
) > clock_var
)
2310 /* INSN has been prematurely moved from the queue to the ready list.
2311 This is possible only if following flag is set. */
2312 gcc_assert (flag_sched_stalled_insns
);
2314 /* ??? Probably, if INSN is scheduled prematurely, we should leave
2315 INSN_TICK untouched. This is a machine-dependent issue, actually. */
2316 INSN_TICK (insn
) = clock_var
;
2318 check_clobbered_conditions (insn
);
2320 /* Update dependent instructions. */
2321 for (sd_it
= sd_iterator_start (insn
, SD_LIST_FORW
);
2322 sd_iterator_cond (&sd_it
, &dep
);)
2324 rtx next
= DEP_CON (dep
);
2325 bool cancelled
= (DEP_STATUS (dep
) & DEP_CANCELLED
) != 0;
2327 /* Resolve the dependence between INSN and NEXT.
2328 sd_resolve_dep () moves current dep to another list thus
2329 advancing the iterator. */
2330 sd_resolve_dep (sd_it
);
2334 if (QUEUE_INDEX (next
) != QUEUE_SCHEDULED
)
2336 int tick
= INSN_TICK (next
);
2337 gcc_assert (ORIG_PAT (next
) != NULL_RTX
);
2338 haifa_change_pattern (next
, ORIG_PAT (next
));
2339 INSN_TICK (next
) = tick
;
2340 if (sd_lists_empty_p (next
, SD_LIST_BACK
))
2341 TODO_SPEC (next
) = 0;
2342 else if (!sd_lists_empty_p (next
, SD_LIST_HARD_BACK
))
2343 TODO_SPEC (next
) = HARD_DEP
;
2348 /* Don't bother trying to mark next as ready if insn is a debug
2349 insn. If insn is the last hard dependency, it will have
2350 already been discounted. */
2351 if (DEBUG_INSN_P (insn
) && !DEBUG_INSN_P (next
))
2354 if (!IS_SPECULATION_BRANCHY_CHECK_P (insn
))
2358 effective_cost
= try_ready (next
);
2360 if (effective_cost
>= 0
2361 && SCHED_GROUP_P (next
)
2362 && advance
< effective_cost
)
2363 advance
= effective_cost
;
2366 /* Check always has only one forward dependence (to the first insn in
2367 the recovery block), therefore, this will be executed only once. */
2369 gcc_assert (sd_lists_empty_p (insn
, SD_LIST_FORW
));
2370 fix_recovery_deps (RECOVERY_BLOCK (insn
));
2374 /* Annotate the instruction with issue information -- TImode
2375 indicates that the instruction is expected not to be able
2376 to issue on the same cycle as the previous insn. A machine
2377 may use this information to decide how the instruction should
2380 && GET_CODE (PATTERN (insn
)) != USE
2381 && GET_CODE (PATTERN (insn
)) != CLOBBER
2382 && !DEBUG_INSN_P (insn
))
2384 if (reload_completed
)
2385 PUT_MODE (insn
, clock_var
> last_clock_var
? TImode
: VOIDmode
);
2386 last_clock_var
= clock_var
;
2392 /* Functions for handling of notes. */
2394 /* Add note list that ends on FROM_END to the end of TO_ENDP. */
2396 concat_note_lists (rtx from_end
, rtx
*to_endp
)
2400 /* It's easy when have nothing to concat. */
2401 if (from_end
== NULL
)
2404 /* It's also easy when destination is empty. */
2405 if (*to_endp
== NULL
)
2407 *to_endp
= from_end
;
2411 from_start
= from_end
;
2412 while (PREV_INSN (from_start
) != NULL
)
2413 from_start
= PREV_INSN (from_start
);
2415 PREV_INSN (from_start
) = *to_endp
;
2416 NEXT_INSN (*to_endp
) = from_start
;
2417 *to_endp
= from_end
;
2420 /* Delete notes between HEAD and TAIL and put them in the chain
2421 of notes ended by NOTE_LIST. */
2423 remove_notes (rtx head
, rtx tail
)
2425 rtx next_tail
, insn
, next
;
2428 if (head
== tail
&& !INSN_P (head
))
2431 next_tail
= NEXT_INSN (tail
);
2432 for (insn
= head
; insn
!= next_tail
; insn
= next
)
2434 next
= NEXT_INSN (insn
);
2438 switch (NOTE_KIND (insn
))
2440 case NOTE_INSN_BASIC_BLOCK
:
2443 case NOTE_INSN_EPILOGUE_BEG
:
2447 add_reg_note (next
, REG_SAVE_NOTE
,
2448 GEN_INT (NOTE_INSN_EPILOGUE_BEG
));
2456 /* Add the note to list that ends at NOTE_LIST. */
2457 PREV_INSN (insn
) = note_list
;
2458 NEXT_INSN (insn
) = NULL_RTX
;
2460 NEXT_INSN (note_list
) = insn
;
2465 gcc_assert ((sel_sched_p () || insn
!= tail
) && insn
!= head
);
2469 /* A structure to record enough data to allow us to backtrack the scheduler to
2470 a previous state. */
2471 struct haifa_saved_data
2473 /* Next entry on the list. */
2474 struct haifa_saved_data
*next
;
2476 /* Backtracking is associated with scheduling insns that have delay slots.
2477 DELAY_PAIR points to the structure that contains the insns involved, and
2478 the number of cycles between them. */
2479 struct delay_pair
*delay_pair
;
2481 /* Data used by the frontend (e.g. sched-ebb or sched-rgn). */
2482 void *fe_saved_data
;
2483 /* Data used by the backend. */
2484 void *be_saved_data
;
2486 /* Copies of global state. */
2487 int clock_var
, last_clock_var
;
2488 struct ready_list ready
;
2491 rtx last_scheduled_insn
;
2492 rtx last_nondebug_scheduled_insn
;
2493 int cycle_issued_insns
;
2495 /* Copies of state used in the inner loop of schedule_block. */
2496 struct sched_block_state sched_block
;
2498 /* We don't need to save q_ptr, as its value is arbitrary and we can set it
2499 to 0 when restoring. */
2504 /* A record, in reverse order, of all scheduled insns which have delay slots
2505 and may require backtracking. */
2506 static struct haifa_saved_data
*backtrack_queue
;
2508 /* For every dependency of INSN, set the FEEDS_BACKTRACK_INSN bit according
2511 mark_backtrack_feeds (rtx insn
, int set_p
)
2513 sd_iterator_def sd_it
;
2515 FOR_EACH_DEP (insn
, SD_LIST_HARD_BACK
, sd_it
, dep
)
2517 FEEDS_BACKTRACK_INSN (DEP_PRO (dep
)) = set_p
;
2521 /* Save the current scheduler state so that we can backtrack to it
2522 later if necessary. PAIR gives the insns that make it necessary to
2523 save this point. SCHED_BLOCK is the local state of schedule_block
2524 that need to be saved. */
2526 save_backtrack_point (struct delay_pair
*pair
,
2527 struct sched_block_state sched_block
)
2530 struct haifa_saved_data
*save
= XNEW (struct haifa_saved_data
);
2532 save
->curr_state
= xmalloc (dfa_state_size
);
2533 memcpy (save
->curr_state
, curr_state
, dfa_state_size
);
2535 save
->ready
.first
= ready
.first
;
2536 save
->ready
.n_ready
= ready
.n_ready
;
2537 save
->ready
.n_debug
= ready
.n_debug
;
2538 save
->ready
.veclen
= ready
.veclen
;
2539 save
->ready
.vec
= XNEWVEC (rtx
, ready
.veclen
);
2540 memcpy (save
->ready
.vec
, ready
.vec
, ready
.veclen
* sizeof (rtx
));
2542 save
->insn_queue
= XNEWVEC (rtx
, max_insn_queue_index
+ 1);
2543 save
->q_size
= q_size
;
2544 for (i
= 0; i
<= max_insn_queue_index
; i
++)
2546 int q
= NEXT_Q_AFTER (q_ptr
, i
);
2547 save
->insn_queue
[i
] = copy_INSN_LIST (insn_queue
[q
]);
2550 save
->clock_var
= clock_var
;
2551 save
->last_clock_var
= last_clock_var
;
2552 save
->cycle_issued_insns
= cycle_issued_insns
;
2553 save
->last_scheduled_insn
= last_scheduled_insn
;
2554 save
->last_nondebug_scheduled_insn
= last_nondebug_scheduled_insn
;
2556 save
->sched_block
= sched_block
;
2558 if (current_sched_info
->save_state
)
2559 save
->fe_saved_data
= (*current_sched_info
->save_state
) ();
2561 if (targetm
.sched
.alloc_sched_context
)
2563 save
->be_saved_data
= targetm
.sched
.alloc_sched_context ();
2564 targetm
.sched
.init_sched_context (save
->be_saved_data
, false);
2567 save
->be_saved_data
= NULL
;
2569 save
->delay_pair
= pair
;
2571 save
->next
= backtrack_queue
;
2572 backtrack_queue
= save
;
2576 mark_backtrack_feeds (pair
->i2
, 1);
2577 INSN_TICK (pair
->i2
) = INVALID_TICK
;
2578 INSN_EXACT_TICK (pair
->i2
) = clock_var
+ pair_delay (pair
);
2579 SHADOW_P (pair
->i2
) = pair
->stages
== 0;
2580 pair
= pair
->next_same_i1
;
2584 /* Walk the ready list and all queues. If any insns have unresolved backwards
2585 dependencies, these must be cancelled deps, broken by predication. Set or
2586 clear (depending on SET) the DEP_CANCELLED bit in DEP_STATUS. */
2589 toggle_cancelled_flags (bool set
)
2592 sd_iterator_def sd_it
;
2595 if (ready
.n_ready
> 0)
2597 rtx
*first
= ready_lastpos (&ready
);
2598 for (i
= 0; i
< ready
.n_ready
; i
++)
2599 FOR_EACH_DEP (first
[i
], SD_LIST_BACK
, sd_it
, dep
)
2600 if (!DEBUG_INSN_P (DEP_PRO (dep
)))
2603 DEP_STATUS (dep
) |= DEP_CANCELLED
;
2605 DEP_STATUS (dep
) &= ~DEP_CANCELLED
;
2608 for (i
= 0; i
<= max_insn_queue_index
; i
++)
2610 int q
= NEXT_Q_AFTER (q_ptr
, i
);
2612 for (link
= insn_queue
[q
]; link
; link
= XEXP (link
, 1))
2614 rtx insn
= XEXP (link
, 0);
2615 FOR_EACH_DEP (insn
, SD_LIST_BACK
, sd_it
, dep
)
2616 if (!DEBUG_INSN_P (DEP_PRO (dep
)))
2619 DEP_STATUS (dep
) |= DEP_CANCELLED
;
2621 DEP_STATUS (dep
) &= ~DEP_CANCELLED
;
2627 /* Pop entries from the SCHEDULED_INSNS vector up to and including INSN.
2628 Restore their dependencies to an unresolved state, and mark them as
2632 unschedule_insns_until (rtx insn
)
2634 VEC (rtx
, heap
) *recompute_vec
;
2636 recompute_vec
= VEC_alloc (rtx
, heap
, 0);
2638 /* Make two passes over the insns to be unscheduled. First, we clear out
2639 dependencies and other trivial bookkeeping. */
2643 sd_iterator_def sd_it
;
2646 last
= VEC_pop (rtx
, scheduled_insns
);
2648 /* This will be changed by restore_backtrack_point if the insn is in
2650 QUEUE_INDEX (last
) = QUEUE_NOWHERE
;
2652 INSN_TICK (last
) = INVALID_TICK
;
2654 if (modulo_ii
> 0 && INSN_UID (last
) < modulo_iter0_max_uid
)
2655 modulo_insns_scheduled
--;
2657 for (sd_it
= sd_iterator_start (last
, SD_LIST_RES_FORW
);
2658 sd_iterator_cond (&sd_it
, &dep
);)
2660 rtx con
= DEP_CON (dep
);
2661 sd_unresolve_dep (sd_it
);
2662 if (!MUST_RECOMPUTE_SPEC_P (con
))
2664 MUST_RECOMPUTE_SPEC_P (con
) = 1;
2665 VEC_safe_push (rtx
, heap
, recompute_vec
, con
);
2673 /* A second pass, to update ready and speculation status for insns
2674 depending on the unscheduled ones. The first pass must have
2675 popped the scheduled_insns vector up to the point where we
2676 restart scheduling, as recompute_todo_spec requires it to be
2678 while (!VEC_empty (rtx
, recompute_vec
))
2682 con
= VEC_pop (rtx
, recompute_vec
);
2683 MUST_RECOMPUTE_SPEC_P (con
) = 0;
2684 if (!sd_lists_empty_p (con
, SD_LIST_HARD_BACK
))
2686 TODO_SPEC (con
) = HARD_DEP
;
2687 INSN_TICK (con
) = INVALID_TICK
;
2688 if (PREDICATED_PAT (con
) != NULL_RTX
)
2689 haifa_change_pattern (con
, ORIG_PAT (con
));
2691 else if (QUEUE_INDEX (con
) != QUEUE_SCHEDULED
)
2692 TODO_SPEC (con
) = recompute_todo_spec (con
);
2694 VEC_free (rtx
, heap
, recompute_vec
);
2697 /* Restore scheduler state from the topmost entry on the backtracking queue.
2698 PSCHED_BLOCK_P points to the local data of schedule_block that we must
2699 overwrite with the saved data.
2700 The caller must already have called unschedule_insns_until. */
2703 restore_last_backtrack_point (struct sched_block_state
*psched_block
)
2707 struct haifa_saved_data
*save
= backtrack_queue
;
2709 backtrack_queue
= save
->next
;
2711 if (current_sched_info
->restore_state
)
2712 (*current_sched_info
->restore_state
) (save
->fe_saved_data
);
2714 if (targetm
.sched
.alloc_sched_context
)
2716 targetm
.sched
.set_sched_context (save
->be_saved_data
);
2717 targetm
.sched
.free_sched_context (save
->be_saved_data
);
2720 /* Clear the QUEUE_INDEX of everything in the ready list or one
2722 if (ready
.n_ready
> 0)
2724 rtx
*first
= ready_lastpos (&ready
);
2725 for (i
= 0; i
< ready
.n_ready
; i
++)
2727 rtx insn
= first
[i
];
2728 QUEUE_INDEX (insn
) = QUEUE_NOWHERE
;
2729 INSN_TICK (insn
) = INVALID_TICK
;
2732 for (i
= 0; i
<= max_insn_queue_index
; i
++)
2734 int q
= NEXT_Q_AFTER (q_ptr
, i
);
2736 for (link
= insn_queue
[q
]; link
; link
= XEXP (link
, 1))
2738 rtx x
= XEXP (link
, 0);
2739 QUEUE_INDEX (x
) = QUEUE_NOWHERE
;
2740 INSN_TICK (x
) = INVALID_TICK
;
2742 free_INSN_LIST_list (&insn_queue
[q
]);
2746 ready
= save
->ready
;
2748 if (ready
.n_ready
> 0)
2750 rtx
*first
= ready_lastpos (&ready
);
2751 for (i
= 0; i
< ready
.n_ready
; i
++)
2753 rtx insn
= first
[i
];
2754 QUEUE_INDEX (insn
) = QUEUE_READY
;
2755 TODO_SPEC (insn
) = recompute_todo_spec (insn
);
2756 INSN_TICK (insn
) = save
->clock_var
;
2761 q_size
= save
->q_size
;
2762 for (i
= 0; i
<= max_insn_queue_index
; i
++)
2764 int q
= NEXT_Q_AFTER (q_ptr
, i
);
2766 insn_queue
[q
] = save
->insn_queue
[q
];
2768 for (link
= insn_queue
[q
]; link
; link
= XEXP (link
, 1))
2770 rtx x
= XEXP (link
, 0);
2771 QUEUE_INDEX (x
) = i
;
2772 TODO_SPEC (x
) = recompute_todo_spec (x
);
2773 INSN_TICK (x
) = save
->clock_var
+ i
;
2776 free (save
->insn_queue
);
2778 toggle_cancelled_flags (true);
2780 clock_var
= save
->clock_var
;
2781 last_clock_var
= save
->last_clock_var
;
2782 cycle_issued_insns
= save
->cycle_issued_insns
;
2783 last_scheduled_insn
= save
->last_scheduled_insn
;
2784 last_nondebug_scheduled_insn
= save
->last_nondebug_scheduled_insn
;
2786 *psched_block
= save
->sched_block
;
2788 memcpy (curr_state
, save
->curr_state
, dfa_state_size
);
2789 free (save
->curr_state
);
2791 mark_backtrack_feeds (save
->delay_pair
->i2
, 0);
2795 for (save
= backtrack_queue
; save
; save
= save
->next
)
2797 mark_backtrack_feeds (save
->delay_pair
->i2
, 1);
2801 /* Discard all data associated with the topmost entry in the backtrack
2802 queue. If RESET_TICK is false, we just want to free the data. If true,
2803 we are doing this because we discovered a reason to backtrack. In the
2804 latter case, also reset the INSN_TICK for the shadow insn. */
2806 free_topmost_backtrack_point (bool reset_tick
)
2808 struct haifa_saved_data
*save
= backtrack_queue
;
2811 backtrack_queue
= save
->next
;
2815 struct delay_pair
*pair
= save
->delay_pair
;
2818 INSN_TICK (pair
->i2
) = INVALID_TICK
;
2819 INSN_EXACT_TICK (pair
->i2
) = INVALID_TICK
;
2820 pair
= pair
->next_same_i1
;
2823 if (targetm
.sched
.free_sched_context
)
2824 targetm
.sched
.free_sched_context (save
->be_saved_data
);
2825 if (current_sched_info
->restore_state
)
2826 free (save
->fe_saved_data
);
2827 for (i
= 0; i
<= max_insn_queue_index
; i
++)
2828 free_INSN_LIST_list (&save
->insn_queue
[i
]);
2829 free (save
->insn_queue
);
2830 free (save
->curr_state
);
2831 free (save
->ready
.vec
);
2835 /* Free the entire backtrack queue. */
2837 free_backtrack_queue (void)
2839 while (backtrack_queue
)
2840 free_topmost_backtrack_point (false);
2843 /* Compute INSN_TICK_ESTIMATE for INSN. PROCESSED is a bitmap of
2844 instructions we've previously encountered, a set bit prevents
2845 recursion. BUDGET is a limit on how far ahead we look, it is
2846 reduced on recursive calls. Return true if we produced a good
2847 estimate, or false if we exceeded the budget. */
2849 estimate_insn_tick (bitmap processed
, rtx insn
, int budget
)
2851 sd_iterator_def sd_it
;
2853 int earliest
= INSN_TICK (insn
);
2855 FOR_EACH_DEP (insn
, SD_LIST_BACK
, sd_it
, dep
)
2857 rtx pro
= DEP_PRO (dep
);
2860 if (DEP_STATUS (dep
) & DEP_CANCELLED
)
2863 if (QUEUE_INDEX (pro
) == QUEUE_SCHEDULED
)
2864 gcc_assert (INSN_TICK (pro
) + dep_cost (dep
) <= INSN_TICK (insn
));
2867 int cost
= dep_cost (dep
);
2870 if (!bitmap_bit_p (processed
, INSN_LUID (pro
)))
2872 if (!estimate_insn_tick (processed
, pro
, budget
- cost
))
2875 gcc_assert (INSN_TICK_ESTIMATE (pro
) != INVALID_TICK
);
2876 t
= INSN_TICK_ESTIMATE (pro
) + cost
;
2877 if (earliest
== INVALID_TICK
|| t
> earliest
)
2881 bitmap_set_bit (processed
, INSN_LUID (insn
));
2882 INSN_TICK_ESTIMATE (insn
) = earliest
;
2886 /* Examine the pair of insns in P, and estimate (optimistically, assuming
2887 infinite resources) the cycle in which the delayed shadow can be issued.
2888 Return the number of cycles that must pass before the real insn can be
2889 issued in order to meet this constraint. */
2891 estimate_shadow_tick (struct delay_pair
*p
)
2893 bitmap_head processed
;
2896 bitmap_initialize (&processed
, 0);
2898 cutoff
= !estimate_insn_tick (&processed
, p
->i2
,
2899 max_insn_queue_index
+ pair_delay (p
));
2900 bitmap_clear (&processed
);
2902 return max_insn_queue_index
;
2903 t
= INSN_TICK_ESTIMATE (p
->i2
) - (clock_var
+ pair_delay (p
) + 1);
2909 /* If INSN has no unresolved backwards dependencies, add it to the schedule and
2910 recursively resolve all its forward dependencies. */
2912 resolve_dependencies (rtx insn
)
2914 sd_iterator_def sd_it
;
2917 /* Don't use sd_lists_empty_p; it ignores debug insns. */
2918 if (DEPS_LIST_FIRST (INSN_HARD_BACK_DEPS (insn
)) != NULL
2919 || DEPS_LIST_FIRST (INSN_SPEC_BACK_DEPS (insn
)) != NULL
)
2922 if (sched_verbose
>= 4)
2923 fprintf (sched_dump
, ";;\tquickly resolving %d\n", INSN_UID (insn
));
2925 if (QUEUE_INDEX (insn
) >= 0)
2926 queue_remove (insn
);
2928 VEC_safe_push (rtx
, heap
, scheduled_insns
, insn
);
2930 /* Update dependent instructions. */
2931 for (sd_it
= sd_iterator_start (insn
, SD_LIST_FORW
);
2932 sd_iterator_cond (&sd_it
, &dep
);)
2934 rtx next
= DEP_CON (dep
);
2936 if (sched_verbose
>= 4)
2937 fprintf (sched_dump
, ";;\t\tdep %d against %d\n", INSN_UID (insn
),
2940 /* Resolve the dependence between INSN and NEXT.
2941 sd_resolve_dep () moves current dep to another list thus
2942 advancing the iterator. */
2943 sd_resolve_dep (sd_it
);
2945 if (!IS_SPECULATION_BRANCHY_CHECK_P (insn
))
2947 resolve_dependencies (next
);
2950 /* Check always has only one forward dependence (to the first insn in
2951 the recovery block), therefore, this will be executed only once. */
2953 gcc_assert (sd_lists_empty_p (insn
, SD_LIST_FORW
));
2959 /* Return the head and tail pointers of ebb starting at BEG and ending
2962 get_ebb_head_tail (basic_block beg
, basic_block end
, rtx
*headp
, rtx
*tailp
)
2964 rtx beg_head
= BB_HEAD (beg
);
2965 rtx beg_tail
= BB_END (beg
);
2966 rtx end_head
= BB_HEAD (end
);
2967 rtx end_tail
= BB_END (end
);
2969 /* Don't include any notes or labels at the beginning of the BEG
2970 basic block, or notes at the end of the END basic blocks. */
2972 if (LABEL_P (beg_head
))
2973 beg_head
= NEXT_INSN (beg_head
);
2975 while (beg_head
!= beg_tail
)
2976 if (NOTE_P (beg_head
))
2977 beg_head
= NEXT_INSN (beg_head
);
2978 else if (DEBUG_INSN_P (beg_head
))
2982 for (note
= NEXT_INSN (beg_head
);
2986 next
= NEXT_INSN (note
);
2989 if (sched_verbose
>= 9)
2990 fprintf (sched_dump
, "reorder %i\n", INSN_UID (note
));
2992 reorder_insns_nobb (note
, note
, PREV_INSN (beg_head
));
2994 if (BLOCK_FOR_INSN (note
) != beg
)
2995 df_insn_change_bb (note
, beg
);
2997 else if (!DEBUG_INSN_P (note
))
3009 end_head
= beg_head
;
3010 else if (LABEL_P (end_head
))
3011 end_head
= NEXT_INSN (end_head
);
3013 while (end_head
!= end_tail
)
3014 if (NOTE_P (end_tail
))
3015 end_tail
= PREV_INSN (end_tail
);
3016 else if (DEBUG_INSN_P (end_tail
))
3020 for (note
= PREV_INSN (end_tail
);
3024 prev
= PREV_INSN (note
);
3027 if (sched_verbose
>= 9)
3028 fprintf (sched_dump
, "reorder %i\n", INSN_UID (note
));
3030 reorder_insns_nobb (note
, note
, end_tail
);
3032 if (end_tail
== BB_END (end
))
3033 BB_END (end
) = note
;
3035 if (BLOCK_FOR_INSN (note
) != end
)
3036 df_insn_change_bb (note
, end
);
3038 else if (!DEBUG_INSN_P (note
))
3050 /* Return nonzero if there are no real insns in the range [ HEAD, TAIL ]. */
3053 no_real_insns_p (const_rtx head
, const_rtx tail
)
3055 while (head
!= NEXT_INSN (tail
))
3057 if (!NOTE_P (head
) && !LABEL_P (head
))
3059 head
= NEXT_INSN (head
);
3064 /* Restore-other-notes: NOTE_LIST is the end of a chain of notes
3065 previously found among the insns. Insert them just before HEAD. */
3067 restore_other_notes (rtx head
, basic_block head_bb
)
3071 rtx note_head
= note_list
;
3074 head_bb
= BLOCK_FOR_INSN (head
);
3076 head
= NEXT_INSN (bb_note (head_bb
));
3078 while (PREV_INSN (note_head
))
3080 set_block_for_insn (note_head
, head_bb
);
3081 note_head
= PREV_INSN (note_head
);
3083 /* In the above cycle we've missed this note. */
3084 set_block_for_insn (note_head
, head_bb
);
3086 PREV_INSN (note_head
) = PREV_INSN (head
);
3087 NEXT_INSN (PREV_INSN (head
)) = note_head
;
3088 PREV_INSN (head
) = note_list
;
3089 NEXT_INSN (note_list
) = head
;
3091 if (BLOCK_FOR_INSN (head
) != head_bb
)
3092 BB_END (head_bb
) = note_list
;
3100 /* Move insns that became ready to fire from queue to ready list. */
3103 queue_to_ready (struct ready_list
*ready
)
3109 q_ptr
= NEXT_Q (q_ptr
);
3111 if (dbg_cnt (sched_insn
) == false)
3113 /* If debug counter is activated do not requeue the first
3114 nonscheduled insn. */
3115 skip_insn
= nonscheduled_insns_begin
;
3118 skip_insn
= next_nonnote_nondebug_insn (skip_insn
);
3120 while (QUEUE_INDEX (skip_insn
) == QUEUE_SCHEDULED
);
3123 skip_insn
= NULL_RTX
;
3125 /* Add all pending insns that can be scheduled without stalls to the
3127 for (link
= insn_queue
[q_ptr
]; link
; link
= XEXP (link
, 1))
3129 insn
= XEXP (link
, 0);
3132 if (sched_verbose
>= 2)
3133 fprintf (sched_dump
, ";;\t\tQ-->Ready: insn %s: ",
3134 (*current_sched_info
->print_insn
) (insn
, 0));
3136 /* If the ready list is full, delay the insn for 1 cycle.
3137 See the comment in schedule_block for the rationale. */
3138 if (!reload_completed
3139 && ready
->n_ready
- ready
->n_debug
> MAX_SCHED_READY_INSNS
3140 && !SCHED_GROUP_P (insn
)
3141 && insn
!= skip_insn
)
3142 queue_insn (insn
, 1, "ready full");
3145 ready_add (ready
, insn
, false);
3146 if (sched_verbose
>= 2)
3147 fprintf (sched_dump
, "moving to ready without stalls\n");
3150 free_INSN_LIST_list (&insn_queue
[q_ptr
]);
3152 /* If there are no ready insns, stall until one is ready and add all
3153 of the pending insns at that point to the ready list. */
3154 if (ready
->n_ready
== 0)
3158 for (stalls
= 1; stalls
<= max_insn_queue_index
; stalls
++)
3160 if ((link
= insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)]))
3162 for (; link
; link
= XEXP (link
, 1))
3164 insn
= XEXP (link
, 0);
3167 if (sched_verbose
>= 2)
3168 fprintf (sched_dump
, ";;\t\tQ-->Ready: insn %s: ",
3169 (*current_sched_info
->print_insn
) (insn
, 0));
3171 ready_add (ready
, insn
, false);
3172 if (sched_verbose
>= 2)
3173 fprintf (sched_dump
, "moving to ready with %d stalls\n", stalls
);
3175 free_INSN_LIST_list (&insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)]);
3177 advance_one_cycle ();
3182 advance_one_cycle ();
3185 q_ptr
= NEXT_Q_AFTER (q_ptr
, stalls
);
3186 clock_var
+= stalls
;
3190 /* Used by early_queue_to_ready. Determines whether it is "ok" to
3191 prematurely move INSN from the queue to the ready list. Currently,
3192 if a target defines the hook 'is_costly_dependence', this function
3193 uses the hook to check whether there exist any dependences which are
3194 considered costly by the target, between INSN and other insns that
3195 have already been scheduled. Dependences are checked up to Y cycles
3196 back, with default Y=1; The flag -fsched-stalled-insns-dep=Y allows
3197 controlling this value.
3198 (Other considerations could be taken into account instead (or in
3199 addition) depending on user flags and target hooks. */
3202 ok_for_early_queue_removal (rtx insn
)
3204 if (targetm
.sched
.is_costly_dependence
)
3208 int i
= VEC_length (rtx
, scheduled_insns
);
3209 for (n_cycles
= flag_sched_stalled_insns_dep
; n_cycles
; n_cycles
--)
3215 prev_insn
= VEC_index (rtx
, scheduled_insns
, i
);
3217 if (!NOTE_P (prev_insn
))
3221 dep
= sd_find_dep_between (prev_insn
, insn
, true);
3225 cost
= dep_cost (dep
);
3227 if (targetm
.sched
.is_costly_dependence (dep
, cost
,
3228 flag_sched_stalled_insns_dep
- n_cycles
))
3233 if (GET_MODE (prev_insn
) == TImode
) /* end of dispatch group */
3246 /* Remove insns from the queue, before they become "ready" with respect
3247 to FU latency considerations. */
3250 early_queue_to_ready (state_t state
, struct ready_list
*ready
)
3258 state_t temp_state
= alloca (dfa_state_size
);
3260 int insns_removed
= 0;
3263 Flag '-fsched-stalled-insns=X' determines the aggressiveness of this
3266 X == 0: There is no limit on how many queued insns can be removed
3267 prematurely. (flag_sched_stalled_insns = -1).
3269 X >= 1: Only X queued insns can be removed prematurely in each
3270 invocation. (flag_sched_stalled_insns = X).
3272 Otherwise: Early queue removal is disabled.
3273 (flag_sched_stalled_insns = 0)
3276 if (! flag_sched_stalled_insns
)
3279 for (stalls
= 0; stalls
<= max_insn_queue_index
; stalls
++)
3281 if ((link
= insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)]))
3283 if (sched_verbose
> 6)
3284 fprintf (sched_dump
, ";; look at index %d + %d\n", q_ptr
, stalls
);
3289 next_link
= XEXP (link
, 1);
3290 insn
= XEXP (link
, 0);
3291 if (insn
&& sched_verbose
> 6)
3292 print_rtl_single (sched_dump
, insn
);
3294 memcpy (temp_state
, state
, dfa_state_size
);
3295 if (recog_memoized (insn
) < 0)
3296 /* non-negative to indicate that it's not ready
3297 to avoid infinite Q->R->Q->R... */
3300 cost
= state_transition (temp_state
, insn
);
3302 if (sched_verbose
>= 6)
3303 fprintf (sched_dump
, "transition cost = %d\n", cost
);
3305 move_to_ready
= false;
3308 move_to_ready
= ok_for_early_queue_removal (insn
);
3309 if (move_to_ready
== true)
3311 /* move from Q to R */
3313 ready_add (ready
, insn
, false);
3316 XEXP (prev_link
, 1) = next_link
;
3318 insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)] = next_link
;
3320 free_INSN_LIST_node (link
);
3322 if (sched_verbose
>= 2)
3323 fprintf (sched_dump
, ";;\t\tEarly Q-->Ready: insn %s\n",
3324 (*current_sched_info
->print_insn
) (insn
, 0));
3327 if (insns_removed
== flag_sched_stalled_insns
)
3328 /* Remove no more than flag_sched_stalled_insns insns
3329 from Q at a time. */
3330 return insns_removed
;
3334 if (move_to_ready
== false)
3341 } /* for stalls.. */
3343 return insns_removed
;
3347 /* Print the ready list for debugging purposes. Callable from debugger. */
3350 debug_ready_list (struct ready_list
*ready
)
3355 if (ready
->n_ready
== 0)
3357 fprintf (sched_dump
, "\n");
3361 p
= ready_lastpos (ready
);
3362 for (i
= 0; i
< ready
->n_ready
; i
++)
3364 fprintf (sched_dump
, " %s:%d",
3365 (*current_sched_info
->print_insn
) (p
[i
], 0),
3367 if (sched_pressure_p
)
3368 fprintf (sched_dump
, "(cost=%d",
3369 INSN_REG_PRESSURE_EXCESS_COST_CHANGE (p
[i
]));
3370 if (INSN_TICK (p
[i
]) > clock_var
)
3371 fprintf (sched_dump
, ":delay=%d", INSN_TICK (p
[i
]) - clock_var
);
3372 if (sched_pressure_p
)
3373 fprintf (sched_dump
, ")");
3375 fprintf (sched_dump
, "\n");
3378 /* Search INSN for REG_SAVE_NOTE notes and convert them back into insn
3379 NOTEs. This is used for NOTE_INSN_EPILOGUE_BEG, so that sched-ebb
3380 replaces the epilogue note in the correct basic block. */
3382 reemit_notes (rtx insn
)
3384 rtx note
, last
= insn
;
3386 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
3388 if (REG_NOTE_KIND (note
) == REG_SAVE_NOTE
)
3390 enum insn_note note_type
= (enum insn_note
) INTVAL (XEXP (note
, 0));
3392 last
= emit_note_before (note_type
, last
);
3393 remove_note (insn
, note
);
3398 /* Move INSN. Reemit notes if needed. Update CFG, if needed. */
3400 move_insn (rtx insn
, rtx last
, rtx nt
)
3402 if (PREV_INSN (insn
) != last
)
3408 bb
= BLOCK_FOR_INSN (insn
);
3410 /* BB_HEAD is either LABEL or NOTE. */
3411 gcc_assert (BB_HEAD (bb
) != insn
);
3413 if (BB_END (bb
) == insn
)
3414 /* If this is last instruction in BB, move end marker one
3417 /* Jumps are always placed at the end of basic block. */
3418 jump_p
= control_flow_insn_p (insn
);
3421 || ((common_sched_info
->sched_pass_id
== SCHED_RGN_PASS
)
3422 && IS_SPECULATION_BRANCHY_CHECK_P (insn
))
3423 || (common_sched_info
->sched_pass_id
3424 == SCHED_EBB_PASS
));
3426 gcc_assert (BLOCK_FOR_INSN (PREV_INSN (insn
)) == bb
);
3428 BB_END (bb
) = PREV_INSN (insn
);
3431 gcc_assert (BB_END (bb
) != last
);
3434 /* We move the block note along with jump. */
3438 note
= NEXT_INSN (insn
);
3439 while (NOTE_NOT_BB_P (note
) && note
!= nt
)
3440 note
= NEXT_INSN (note
);
3444 || BARRIER_P (note
)))
3445 note
= NEXT_INSN (note
);
3447 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
3452 NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (note
);
3453 PREV_INSN (NEXT_INSN (note
)) = PREV_INSN (insn
);
3455 NEXT_INSN (note
) = NEXT_INSN (last
);
3456 PREV_INSN (NEXT_INSN (last
)) = note
;
3458 NEXT_INSN (last
) = insn
;
3459 PREV_INSN (insn
) = last
;
3461 bb
= BLOCK_FOR_INSN (last
);
3465 fix_jump_move (insn
);
3467 if (BLOCK_FOR_INSN (insn
) != bb
)
3468 move_block_after_check (insn
);
3470 gcc_assert (BB_END (bb
) == last
);
3473 df_insn_change_bb (insn
, bb
);
3475 /* Update BB_END, if needed. */
3476 if (BB_END (bb
) == last
)
3480 SCHED_GROUP_P (insn
) = 0;
3483 /* Return true if scheduling INSN will finish current clock cycle. */
3485 insn_finishes_cycle_p (rtx insn
)
3487 if (SCHED_GROUP_P (insn
))
3488 /* After issuing INSN, rest of the sched_group will be forced to issue
3489 in order. Don't make any plans for the rest of cycle. */
3492 /* Finishing the block will, apparently, finish the cycle. */
3493 if (current_sched_info
->insn_finishes_block_p
3494 && current_sched_info
->insn_finishes_block_p (insn
))
3500 /* Define type for target data used in multipass scheduling. */
3501 #ifndef TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DATA_T
3502 # define TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DATA_T int
3504 typedef TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DATA_T first_cycle_multipass_data_t
;
3506 /* The following structure describe an entry of the stack of choices. */
3509 /* Ordinal number of the issued insn in the ready queue. */
3511 /* The number of the rest insns whose issues we should try. */
3513 /* The number of issued essential insns. */
3515 /* State after issuing the insn. */
3517 /* Target-specific data. */
3518 first_cycle_multipass_data_t target_data
;
3521 /* The following array is used to implement a stack of choices used in
3522 function max_issue. */
3523 static struct choice_entry
*choice_stack
;
3525 /* This holds the value of the target dfa_lookahead hook. */
3528 /* The following variable value is maximal number of tries of issuing
3529 insns for the first cycle multipass insn scheduling. We define
3530 this value as constant*(DFA_LOOKAHEAD**ISSUE_RATE). We would not
3531 need this constraint if all real insns (with non-negative codes)
3532 had reservations because in this case the algorithm complexity is
3533 O(DFA_LOOKAHEAD**ISSUE_RATE). Unfortunately, the dfa descriptions
3534 might be incomplete and such insn might occur. For such
3535 descriptions, the complexity of algorithm (without the constraint)
3536 could achieve DFA_LOOKAHEAD ** N , where N is the queue length. */
3537 static int max_lookahead_tries
;
3539 /* The following value is value of hook
3540 `first_cycle_multipass_dfa_lookahead' at the last call of
3542 static int cached_first_cycle_multipass_dfa_lookahead
= 0;
3544 /* The following value is value of `issue_rate' at the last call of
3546 static int cached_issue_rate
= 0;
3548 /* The following function returns maximal (or close to maximal) number
3549 of insns which can be issued on the same cycle and one of which
3550 insns is insns with the best rank (the first insn in READY). To
3551 make this function tries different samples of ready insns. READY
3552 is current queue `ready'. Global array READY_TRY reflects what
3553 insns are already issued in this try. The function stops immediately,
3554 if it reached the such a solution, that all instruction can be issued.
3555 INDEX will contain index of the best insn in READY. The following
3556 function is used only for first cycle multipass scheduling.
3560 This function expects recognized insns only. All USEs,
3561 CLOBBERs, etc must be filtered elsewhere. */
3563 max_issue (struct ready_list
*ready
, int privileged_n
, state_t state
,
3564 bool first_cycle_insn_p
, int *index
)
3566 int n
, i
, all
, n_ready
, best
, delay
, tries_num
;
3568 struct choice_entry
*top
;
3571 n_ready
= ready
->n_ready
;
3572 gcc_assert (dfa_lookahead
>= 1 && privileged_n
>= 0
3573 && privileged_n
<= n_ready
);
3575 /* Init MAX_LOOKAHEAD_TRIES. */
3576 if (cached_first_cycle_multipass_dfa_lookahead
!= dfa_lookahead
)
3578 cached_first_cycle_multipass_dfa_lookahead
= dfa_lookahead
;
3579 max_lookahead_tries
= 100;
3580 for (i
= 0; i
< issue_rate
; i
++)
3581 max_lookahead_tries
*= dfa_lookahead
;
3584 /* Init max_points. */
3585 more_issue
= issue_rate
- cycle_issued_insns
;
3586 gcc_assert (more_issue
>= 0);
3588 /* The number of the issued insns in the best solution. */
3593 /* Set initial state of the search. */
3594 memcpy (top
->state
, state
, dfa_state_size
);
3595 top
->rest
= dfa_lookahead
;
3597 if (targetm
.sched
.first_cycle_multipass_begin
)
3598 targetm
.sched
.first_cycle_multipass_begin (&top
->target_data
,
3600 first_cycle_insn_p
);
3602 /* Count the number of the insns to search among. */
3603 for (all
= i
= 0; i
< n_ready
; i
++)
3607 /* I is the index of the insn to try next. */
3612 if (/* If we've reached a dead end or searched enough of what we have
3615 /* or have nothing else to try... */
3617 /* or should not issue more. */
3618 || top
->n
>= more_issue
)
3620 /* ??? (... || i == n_ready). */
3621 gcc_assert (i
<= n_ready
);
3623 /* We should not issue more than issue_rate instructions. */
3624 gcc_assert (top
->n
<= more_issue
);
3626 if (top
== choice_stack
)
3629 if (best
< top
- choice_stack
)
3634 /* Try to find issued privileged insn. */
3635 while (n
&& !ready_try
[--n
])
3639 if (/* If all insns are equally good... */
3641 /* Or a privileged insn will be issued. */
3643 /* Then we have a solution. */
3645 best
= top
- choice_stack
;
3646 /* This is the index of the insn issued first in this
3648 *index
= choice_stack
[1].index
;
3649 if (top
->n
== more_issue
|| best
== all
)
3654 /* Set ready-list index to point to the last insn
3655 ('i++' below will advance it to the next insn). */
3661 if (targetm
.sched
.first_cycle_multipass_backtrack
)
3662 targetm
.sched
.first_cycle_multipass_backtrack (&top
->target_data
,
3663 ready_try
, n_ready
);
3666 memcpy (state
, top
->state
, dfa_state_size
);
3668 else if (!ready_try
[i
])
3671 if (tries_num
> max_lookahead_tries
)
3673 insn
= ready_element (ready
, i
);
3674 delay
= state_transition (state
, insn
);
3677 if (state_dead_lock_p (state
)
3678 || insn_finishes_cycle_p (insn
))
3679 /* We won't issue any more instructions in the next
3686 if (memcmp (top
->state
, state
, dfa_state_size
) != 0)
3689 /* Advance to the next choice_entry. */
3691 /* Initialize it. */
3692 top
->rest
= dfa_lookahead
;
3695 memcpy (top
->state
, state
, dfa_state_size
);
3698 if (targetm
.sched
.first_cycle_multipass_issue
)
3699 targetm
.sched
.first_cycle_multipass_issue (&top
->target_data
,
3709 /* Increase ready-list index. */
3713 if (targetm
.sched
.first_cycle_multipass_end
)
3714 targetm
.sched
.first_cycle_multipass_end (best
!= 0
3715 ? &choice_stack
[1].target_data
3718 /* Restore the original state of the DFA. */
3719 memcpy (state
, choice_stack
->state
, dfa_state_size
);
3724 /* The following function chooses insn from READY and modifies
3725 READY. The following function is used only for first
3726 cycle multipass scheduling.
3728 -1 if cycle should be advanced,
3729 0 if INSN_PTR is set to point to the desirable insn,
3730 1 if choose_ready () should be restarted without advancing the cycle. */
3732 choose_ready (struct ready_list
*ready
, bool first_cycle_insn_p
,
3737 if (dbg_cnt (sched_insn
) == false)
3739 rtx insn
= nonscheduled_insns_begin
;
3742 insn
= next_nonnote_insn (insn
);
3744 while (QUEUE_INDEX (insn
) == QUEUE_SCHEDULED
);
3746 if (QUEUE_INDEX (insn
) == QUEUE_READY
)
3747 /* INSN is in the ready_list. */
3749 nonscheduled_insns_begin
= insn
;
3750 ready_remove_insn (insn
);
3755 /* INSN is in the queue. Advance cycle to move it to the ready list. */
3761 if (targetm
.sched
.first_cycle_multipass_dfa_lookahead
)
3762 lookahead
= targetm
.sched
.first_cycle_multipass_dfa_lookahead ();
3763 if (lookahead
<= 0 || SCHED_GROUP_P (ready_element (ready
, 0))
3764 || DEBUG_INSN_P (ready_element (ready
, 0)))
3766 if (targetm
.sched
.dispatch (NULL_RTX
, IS_DISPATCH_ON
))
3767 *insn_ptr
= ready_remove_first_dispatch (ready
);
3769 *insn_ptr
= ready_remove_first (ready
);
3775 /* Try to choose the better insn. */
3776 int index
= 0, i
, n
;
3778 int try_data
= 1, try_control
= 1;
3781 insn
= ready_element (ready
, 0);
3782 if (INSN_CODE (insn
) < 0)
3784 *insn_ptr
= ready_remove_first (ready
);
3789 && spec_info
->flags
& (PREFER_NON_DATA_SPEC
3790 | PREFER_NON_CONTROL_SPEC
))
3792 for (i
= 0, n
= ready
->n_ready
; i
< n
; i
++)
3797 x
= ready_element (ready
, i
);
3800 if (spec_info
->flags
& PREFER_NON_DATA_SPEC
3801 && !(s
& DATA_SPEC
))
3804 if (!(spec_info
->flags
& PREFER_NON_CONTROL_SPEC
)
3809 if (spec_info
->flags
& PREFER_NON_CONTROL_SPEC
3810 && !(s
& CONTROL_SPEC
))
3813 if (!(spec_info
->flags
& PREFER_NON_DATA_SPEC
) || !try_data
)
3819 ts
= TODO_SPEC (insn
);
3820 if ((ts
& SPECULATIVE
)
3821 && (((!try_data
&& (ts
& DATA_SPEC
))
3822 || (!try_control
&& (ts
& CONTROL_SPEC
)))
3823 || (targetm
.sched
.first_cycle_multipass_dfa_lookahead_guard_spec
3825 .first_cycle_multipass_dfa_lookahead_guard_spec (insn
))))
3826 /* Discard speculative instruction that stands first in the ready
3829 change_queue_index (insn
, 1);
3835 for (i
= 1; i
< ready
->n_ready
; i
++)
3837 insn
= ready_element (ready
, i
);
3840 = ((!try_data
&& (TODO_SPEC (insn
) & DATA_SPEC
))
3841 || (!try_control
&& (TODO_SPEC (insn
) & CONTROL_SPEC
)));
3844 /* Let the target filter the search space. */
3845 for (i
= 1; i
< ready
->n_ready
; i
++)
3848 insn
= ready_element (ready
, i
);
3850 /* If this insn is recognizable we should have already
3851 recognized it earlier.
3852 ??? Not very clear where this is supposed to be done.
3854 gcc_checking_assert (INSN_CODE (insn
) >= 0
3855 || recog_memoized (insn
) < 0);
3858 = (/* INSN_CODE check can be omitted here as it is also done later
3860 INSN_CODE (insn
) < 0
3861 || (targetm
.sched
.first_cycle_multipass_dfa_lookahead_guard
3862 && !targetm
.sched
.first_cycle_multipass_dfa_lookahead_guard
3866 if (max_issue (ready
, 1, curr_state
, first_cycle_insn_p
, &index
) == 0)
3868 *insn_ptr
= ready_remove_first (ready
);
3869 if (sched_verbose
>= 4)
3870 fprintf (sched_dump
, ";;\t\tChosen insn (but can't issue) : %s \n",
3871 (*current_sched_info
->print_insn
) (*insn_ptr
, 0));
3876 if (sched_verbose
>= 4)
3877 fprintf (sched_dump
, ";;\t\tChosen insn : %s\n",
3878 (*current_sched_info
->print_insn
)
3879 (ready_element (ready
, index
), 0));
3881 *insn_ptr
= ready_remove (ready
, index
);
3887 /* This function is called when we have successfully scheduled a
3888 block. It uses the schedule stored in the scheduled_insns vector
3889 to rearrange the RTL. PREV_HEAD is used as the anchor to which we
3890 append the scheduled insns; TAIL is the insn after the scheduled
3891 block. TARGET_BB is the argument passed to schedule_block. */
3894 commit_schedule (rtx prev_head
, rtx tail
, basic_block
*target_bb
)
3899 last_scheduled_insn
= prev_head
;
3901 VEC_iterate (rtx
, scheduled_insns
, i
, insn
);
3904 if (control_flow_insn_p (last_scheduled_insn
)
3905 || current_sched_info
->advance_target_bb (*target_bb
, insn
))
3907 *target_bb
= current_sched_info
->advance_target_bb (*target_bb
, 0);
3913 x
= next_real_insn (last_scheduled_insn
);
3915 dump_new_block_header (1, *target_bb
, x
, tail
);
3918 last_scheduled_insn
= bb_note (*target_bb
);
3921 if (current_sched_info
->begin_move_insn
)
3922 (*current_sched_info
->begin_move_insn
) (insn
, last_scheduled_insn
);
3923 move_insn (insn
, last_scheduled_insn
,
3924 current_sched_info
->next_tail
);
3925 if (!DEBUG_INSN_P (insn
))
3926 reemit_notes (insn
);
3927 last_scheduled_insn
= insn
;
3930 VEC_truncate (rtx
, scheduled_insns
, 0);
3933 /* Examine all insns on the ready list and queue those which can't be
3934 issued in this cycle. TEMP_STATE is temporary scheduler state we
3935 can use as scratch space. If FIRST_CYCLE_INSN_P is true, no insns
3936 have been issued for the current cycle, which means it is valid to
3937 issue an asm statement.
3939 If SHADOWS_ONLY_P is true, we eliminate all real insns and only
3940 leave those for which SHADOW_P is true. If MODULO_EPILOGUE is true,
3941 we only leave insns which have an INSN_EXACT_TICK. */
3944 prune_ready_list (state_t temp_state
, bool first_cycle_insn_p
,
3945 bool shadows_only_p
, bool modulo_epilogue_p
)
3948 bool sched_group_found
= false;
3951 for (i
= 0; i
< ready
.n_ready
; i
++)
3953 rtx insn
= ready_element (&ready
, i
);
3955 const char *reason
= "resource conflict";
3957 if (DEBUG_INSN_P (insn
))
3960 if (SCHED_GROUP_P (insn
) && !sched_group_found
)
3962 sched_group_found
= true;
3967 if (sched_group_found
&& !SCHED_GROUP_P (insn
))
3970 reason
= "not in sched group";
3972 else if (modulo_epilogue_p
&& INSN_EXACT_TICK (insn
) == INVALID_TICK
)
3974 cost
= max_insn_queue_index
;
3975 reason
= "not an epilogue insn";
3977 else if (shadows_only_p
&& !SHADOW_P (insn
))
3980 reason
= "not a shadow";
3982 else if (recog_memoized (insn
) < 0)
3984 if (!first_cycle_insn_p
3985 && (GET_CODE (PATTERN (insn
)) == ASM_INPUT
3986 || asm_noperands (PATTERN (insn
)) >= 0))
3990 else if (sched_pressure_p
)
3998 struct delay_pair
*delay_entry
;
4000 = (struct delay_pair
*)htab_find_with_hash (delay_htab
, insn
,
4001 htab_hash_pointer (insn
));
4002 while (delay_entry
&& delay_cost
== 0)
4004 delay_cost
= estimate_shadow_tick (delay_entry
);
4005 if (delay_cost
> max_insn_queue_index
)
4006 delay_cost
= max_insn_queue_index
;
4007 delay_entry
= delay_entry
->next_same_i1
;
4011 memcpy (temp_state
, curr_state
, dfa_state_size
);
4012 cost
= state_transition (temp_state
, insn
);
4017 if (cost
< delay_cost
)
4020 reason
= "shadow tick";
4025 ready_remove (&ready
, i
);
4026 queue_insn (insn
, cost
, reason
);
4032 /* Called when we detect that the schedule is impossible. We examine the
4033 backtrack queue to find the earliest insn that caused this condition. */
4035 static struct haifa_saved_data
*
4036 verify_shadows (void)
4038 struct haifa_saved_data
*save
, *earliest_fail
= NULL
;
4039 for (save
= backtrack_queue
; save
; save
= save
->next
)
4042 struct delay_pair
*pair
= save
->delay_pair
;
4045 for (; pair
; pair
= pair
->next_same_i1
)
4049 if (QUEUE_INDEX (i2
) == QUEUE_SCHEDULED
)
4052 t
= INSN_TICK (i1
) + pair_delay (pair
);
4055 if (sched_verbose
>= 2)
4056 fprintf (sched_dump
,
4057 ";;\t\tfailed delay requirements for %d/%d (%d->%d)"
4059 INSN_UID (pair
->i1
), INSN_UID (pair
->i2
),
4060 INSN_TICK (pair
->i1
), INSN_EXACT_TICK (pair
->i2
));
4061 earliest_fail
= save
;
4064 if (QUEUE_INDEX (i2
) >= 0)
4066 int queued_for
= INSN_TICK (i2
);
4070 if (sched_verbose
>= 2)
4071 fprintf (sched_dump
,
4072 ";;\t\tfailed delay requirements for %d/%d"
4073 " (%d->%d), queued too late\n",
4074 INSN_UID (pair
->i1
), INSN_UID (pair
->i2
),
4075 INSN_TICK (pair
->i1
), INSN_EXACT_TICK (pair
->i2
));
4076 earliest_fail
= save
;
4083 return earliest_fail
;
4086 /* Use forward list scheduling to rearrange insns of block pointed to by
4087 TARGET_BB, possibly bringing insns from subsequent blocks in the same
4091 schedule_block (basic_block
*target_bb
)
4094 bool success
= modulo_ii
== 0;
4095 struct sched_block_state ls
;
4096 state_t temp_state
= NULL
; /* It is used for multipass scheduling. */
4097 int sort_p
, advance
, start_clock_var
;
4099 /* Head/tail info for this block. */
4100 rtx prev_head
= current_sched_info
->prev_head
;
4101 rtx next_tail
= current_sched_info
->next_tail
;
4102 rtx head
= NEXT_INSN (prev_head
);
4103 rtx tail
= PREV_INSN (next_tail
);
4105 /* We used to have code to avoid getting parameters moved from hard
4106 argument registers into pseudos.
4108 However, it was removed when it proved to be of marginal benefit
4109 and caused problems because schedule_block and compute_forward_dependences
4110 had different notions of what the "head" insn was. */
4112 gcc_assert (head
!= tail
|| INSN_P (head
));
4114 haifa_recovery_bb_recently_added_p
= false;
4116 backtrack_queue
= NULL
;
4120 dump_new_block_header (0, *target_bb
, head
, tail
);
4122 state_reset (curr_state
);
4124 /* Clear the ready list. */
4125 ready
.first
= ready
.veclen
- 1;
4129 /* It is used for first cycle multipass scheduling. */
4130 temp_state
= alloca (dfa_state_size
);
4132 if (targetm
.sched
.init
)
4133 targetm
.sched
.init (sched_dump
, sched_verbose
, ready
.veclen
);
4135 /* We start inserting insns after PREV_HEAD. */
4136 last_scheduled_insn
= nonscheduled_insns_begin
= prev_head
;
4137 last_nondebug_scheduled_insn
= NULL_RTX
;
4139 gcc_assert ((NOTE_P (last_scheduled_insn
)
4140 || DEBUG_INSN_P (last_scheduled_insn
))
4141 && BLOCK_FOR_INSN (last_scheduled_insn
) == *target_bb
);
4143 /* Initialize INSN_QUEUE. Q_SIZE is the total number of insns in the
4148 insn_queue
= XALLOCAVEC (rtx
, max_insn_queue_index
+ 1);
4149 memset (insn_queue
, 0, (max_insn_queue_index
+ 1) * sizeof (rtx
));
4151 /* Start just before the beginning of time. */
4154 /* We need queue and ready lists and clock_var be initialized
4155 in try_ready () (which is called through init_ready_list ()). */
4156 (*current_sched_info
->init_ready_list
) ();
4158 /* The algorithm is O(n^2) in the number of ready insns at any given
4159 time in the worst case. Before reload we are more likely to have
4160 big lists so truncate them to a reasonable size. */
4161 if (!reload_completed
4162 && ready
.n_ready
- ready
.n_debug
> MAX_SCHED_READY_INSNS
)
4164 ready_sort (&ready
);
4166 /* Find first free-standing insn past MAX_SCHED_READY_INSNS.
4167 If there are debug insns, we know they're first. */
4168 for (i
= MAX_SCHED_READY_INSNS
+ ready
.n_debug
; i
< ready
.n_ready
; i
++)
4169 if (!SCHED_GROUP_P (ready_element (&ready
, i
)))
4172 if (sched_verbose
>= 2)
4174 fprintf (sched_dump
,
4175 ";;\t\tReady list on entry: %d insns\n", ready
.n_ready
);
4176 fprintf (sched_dump
,
4177 ";;\t\t before reload => truncated to %d insns\n", i
);
4180 /* Delay all insns past it for 1 cycle. If debug counter is
4181 activated make an exception for the insn right after
4182 nonscheduled_insns_begin. */
4186 if (dbg_cnt (sched_insn
) == false)
4187 skip_insn
= next_nonnote_insn (nonscheduled_insns_begin
);
4189 skip_insn
= NULL_RTX
;
4191 while (i
< ready
.n_ready
)
4195 insn
= ready_remove (&ready
, i
);
4197 if (insn
!= skip_insn
)
4198 queue_insn (insn
, 1, "list truncated");
4201 ready_add (&ready
, skip_insn
, true);
4205 /* Now we can restore basic block notes and maintain precise cfg. */
4206 restore_bb_notes (*target_bb
);
4208 last_clock_var
= -1;
4212 gcc_assert (VEC_length (rtx
, scheduled_insns
) == 0);
4214 must_backtrack
= false;
4215 modulo_insns_scheduled
= 0;
4217 ls
.modulo_epilogue
= false;
4219 /* Loop until all the insns in BB are scheduled. */
4220 while ((*current_sched_info
->schedule_more_p
) ())
4224 start_clock_var
= clock_var
;
4228 advance_one_cycle ();
4230 /* Add to the ready list all pending insns that can be issued now.
4231 If there are no ready insns, increment clock until one
4232 is ready and add all pending insns at that point to the ready
4234 queue_to_ready (&ready
);
4236 gcc_assert (ready
.n_ready
);
4238 if (sched_verbose
>= 2)
4240 fprintf (sched_dump
, ";;\t\tReady list after queue_to_ready: ");
4241 debug_ready_list (&ready
);
4243 advance
-= clock_var
- start_clock_var
;
4245 while (advance
> 0);
4247 if (ls
.modulo_epilogue
)
4249 int stage
= clock_var
/ modulo_ii
;
4250 if (stage
> modulo_last_stage
* 2 + 2)
4252 if (sched_verbose
>= 2)
4253 fprintf (sched_dump
,
4254 ";;\t\tmodulo scheduled succeeded at II %d\n",
4260 else if (modulo_ii
> 0)
4262 int stage
= clock_var
/ modulo_ii
;
4263 if (stage
> modulo_max_stages
)
4265 if (sched_verbose
>= 2)
4266 fprintf (sched_dump
,
4267 ";;\t\tfailing schedule due to excessive stages\n");
4270 if (modulo_n_insns
== modulo_insns_scheduled
4271 && stage
> modulo_last_stage
)
4273 if (sched_verbose
>= 2)
4274 fprintf (sched_dump
,
4275 ";;\t\tfound kernel after %d stages, II %d\n",
4277 ls
.modulo_epilogue
= true;
4281 prune_ready_list (temp_state
, true, false, ls
.modulo_epilogue
);
4282 if (ready
.n_ready
== 0)
4287 ls
.first_cycle_insn_p
= true;
4288 ls
.shadows_only_p
= false;
4289 cycle_issued_insns
= 0;
4290 ls
.can_issue_more
= issue_rate
;
4297 if (sort_p
&& ready
.n_ready
> 0)
4299 /* Sort the ready list based on priority. This must be
4300 done every iteration through the loop, as schedule_insn
4301 may have readied additional insns that will not be
4302 sorted correctly. */
4303 ready_sort (&ready
);
4305 if (sched_verbose
>= 2)
4307 fprintf (sched_dump
, ";;\t\tReady list after ready_sort: ");
4308 debug_ready_list (&ready
);
4312 /* We don't want md sched reorder to even see debug isns, so put
4313 them out right away. */
4314 if (ready
.n_ready
&& DEBUG_INSN_P (ready_element (&ready
, 0))
4315 && (*current_sched_info
->schedule_more_p
) ())
4317 while (ready
.n_ready
&& DEBUG_INSN_P (ready_element (&ready
, 0)))
4319 rtx insn
= ready_remove_first (&ready
);
4320 gcc_assert (DEBUG_INSN_P (insn
));
4321 (*current_sched_info
->begin_schedule_ready
) (insn
);
4322 VEC_safe_push (rtx
, heap
, scheduled_insns
, insn
);
4323 last_scheduled_insn
= insn
;
4324 advance
= schedule_insn (insn
);
4325 gcc_assert (advance
== 0);
4326 if (ready
.n_ready
> 0)
4327 ready_sort (&ready
);
4331 if (ls
.first_cycle_insn_p
&& !ready
.n_ready
)
4334 resume_after_backtrack
:
4335 /* Allow the target to reorder the list, typically for
4336 better instruction bundling. */
4338 && (ready
.n_ready
== 0
4339 || !SCHED_GROUP_P (ready_element (&ready
, 0))))
4341 if (ls
.first_cycle_insn_p
&& targetm
.sched
.reorder
)
4343 = targetm
.sched
.reorder (sched_dump
, sched_verbose
,
4344 ready_lastpos (&ready
),
4345 &ready
.n_ready
, clock_var
);
4346 else if (!ls
.first_cycle_insn_p
&& targetm
.sched
.reorder2
)
4348 = targetm
.sched
.reorder2 (sched_dump
, sched_verbose
,
4350 ? ready_lastpos (&ready
) : NULL
,
4351 &ready
.n_ready
, clock_var
);
4354 restart_choose_ready
:
4355 if (sched_verbose
>= 2)
4357 fprintf (sched_dump
, ";;\tReady list (t = %3d): ",
4359 debug_ready_list (&ready
);
4360 if (sched_pressure_p
)
4361 print_curr_reg_pressure ();
4364 if (ready
.n_ready
== 0
4365 && ls
.can_issue_more
4366 && reload_completed
)
4368 /* Allow scheduling insns directly from the queue in case
4369 there's nothing better to do (ready list is empty) but
4370 there are still vacant dispatch slots in the current cycle. */
4371 if (sched_verbose
>= 6)
4372 fprintf (sched_dump
,";;\t\tSecond chance\n");
4373 memcpy (temp_state
, curr_state
, dfa_state_size
);
4374 if (early_queue_to_ready (temp_state
, &ready
))
4375 ready_sort (&ready
);
4378 if (ready
.n_ready
== 0
4379 || !ls
.can_issue_more
4380 || state_dead_lock_p (curr_state
)
4381 || !(*current_sched_info
->schedule_more_p
) ())
4384 /* Select and remove the insn from the ready list. */
4390 res
= choose_ready (&ready
, ls
.first_cycle_insn_p
, &insn
);
4396 goto restart_choose_ready
;
4398 gcc_assert (insn
!= NULL_RTX
);
4401 insn
= ready_remove_first (&ready
);
4403 if (sched_pressure_p
&& INSN_TICK (insn
) > clock_var
)
4405 ready_add (&ready
, insn
, true);
4410 if (targetm
.sched
.dfa_new_cycle
4411 && targetm
.sched
.dfa_new_cycle (sched_dump
, sched_verbose
,
4412 insn
, last_clock_var
,
4413 clock_var
, &sort_p
))
4414 /* SORT_P is used by the target to override sorting
4415 of the ready list. This is needed when the target
4416 has modified its internal structures expecting that
4417 the insn will be issued next. As we need the insn
4418 to have the highest priority (so it will be returned by
4419 the ready_remove_first call above), we invoke
4420 ready_add (&ready, insn, true).
4421 But, still, there is one issue: INSN can be later
4422 discarded by scheduler's front end through
4423 current_sched_info->can_schedule_ready_p, hence, won't
4426 ready_add (&ready
, insn
, true);
4432 if (current_sched_info
->can_schedule_ready_p
4433 && ! (*current_sched_info
->can_schedule_ready_p
) (insn
))
4434 /* We normally get here only if we don't want to move
4435 insn from the split block. */
4437 TODO_SPEC (insn
) = HARD_DEP
;
4438 goto restart_choose_ready
;
4443 /* If this insn is the first part of a delay-slot pair, record a
4445 struct delay_pair
*delay_entry
;
4447 = (struct delay_pair
*)htab_find_with_hash (delay_htab
, insn
,
4448 htab_hash_pointer (insn
));
4451 save_backtrack_point (delay_entry
, ls
);
4452 if (sched_verbose
>= 2)
4453 fprintf (sched_dump
, ";;\t\tsaving backtrack point\n");
4457 /* DECISION is made. */
4459 if (modulo_ii
> 0 && INSN_UID (insn
) < modulo_iter0_max_uid
)
4461 modulo_insns_scheduled
++;
4462 modulo_last_stage
= clock_var
/ modulo_ii
;
4464 if (TODO_SPEC (insn
) & SPECULATIVE
)
4465 generate_recovery_code (insn
);
4467 if (targetm
.sched
.dispatch (NULL_RTX
, IS_DISPATCH_ON
))
4468 targetm
.sched
.dispatch_do (insn
, ADD_TO_DISPATCH_WINDOW
);
4470 /* Update counters, etc in the scheduler's front end. */
4471 (*current_sched_info
->begin_schedule_ready
) (insn
);
4472 VEC_safe_push (rtx
, heap
, scheduled_insns
, insn
);
4473 gcc_assert (NONDEBUG_INSN_P (insn
));
4474 last_nondebug_scheduled_insn
= last_scheduled_insn
= insn
;
4476 if (recog_memoized (insn
) >= 0)
4478 memcpy (temp_state
, curr_state
, dfa_state_size
);
4479 cost
= state_transition (curr_state
, insn
);
4480 if (!sched_pressure_p
)
4481 gcc_assert (cost
< 0);
4482 if (memcmp (temp_state
, curr_state
, dfa_state_size
) != 0)
4483 cycle_issued_insns
++;
4487 asm_p
= (GET_CODE (PATTERN (insn
)) == ASM_INPUT
4488 || asm_noperands (PATTERN (insn
)) >= 0);
4490 if (targetm
.sched
.variable_issue
)
4492 targetm
.sched
.variable_issue (sched_dump
, sched_verbose
,
4493 insn
, ls
.can_issue_more
);
4494 /* A naked CLOBBER or USE generates no instruction, so do
4495 not count them against the issue rate. */
4496 else if (GET_CODE (PATTERN (insn
)) != USE
4497 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
4498 ls
.can_issue_more
--;
4499 advance
= schedule_insn (insn
);
4501 if (SHADOW_P (insn
))
4502 ls
.shadows_only_p
= true;
4504 /* After issuing an asm insn we should start a new cycle. */
4505 if (advance
== 0 && asm_p
)
4514 ls
.first_cycle_insn_p
= false;
4515 if (ready
.n_ready
> 0)
4516 prune_ready_list (temp_state
, false, ls
.shadows_only_p
,
4517 ls
.modulo_epilogue
);
4521 if (!must_backtrack
)
4522 for (i
= 0; i
< ready
.n_ready
; i
++)
4524 rtx insn
= ready_element (&ready
, i
);
4525 if (INSN_EXACT_TICK (insn
) == clock_var
)
4527 must_backtrack
= true;
4532 if (must_backtrack
&& modulo_ii
> 0)
4534 if (modulo_backtracks_left
== 0)
4536 modulo_backtracks_left
--;
4538 while (must_backtrack
)
4540 struct haifa_saved_data
*failed
;
4543 must_backtrack
= false;
4544 failed
= verify_shadows ();
4545 gcc_assert (failed
);
4547 failed_insn
= failed
->delay_pair
->i1
;
4548 toggle_cancelled_flags (false);
4549 unschedule_insns_until (failed_insn
);
4550 while (failed
!= backtrack_queue
)
4551 free_topmost_backtrack_point (true);
4552 restore_last_backtrack_point (&ls
);
4553 if (sched_verbose
>= 2)
4554 fprintf (sched_dump
, ";;\t\trewind to cycle %d\n", clock_var
);
4555 /* Delay by at least a cycle. This could cause additional
4557 queue_insn (failed_insn
, 1, "backtracked");
4561 if (ready
.n_ready
> 0)
4562 goto resume_after_backtrack
;
4565 if (clock_var
== 0 && ls
.first_cycle_insn_p
)
4572 if (ls
.modulo_epilogue
)
4577 /* Once again, debug insn suckiness: they can be on the ready list
4578 even if they have unresolved dependencies. To make our view
4579 of the world consistent, remove such "ready" insns. */
4580 restart_debug_insn_loop
:
4581 for (i
= ready
.n_ready
- 1; i
>= 0; i
--)
4585 x
= ready_element (&ready
, i
);
4586 if (DEPS_LIST_FIRST (INSN_HARD_BACK_DEPS (x
)) != NULL
4587 || DEPS_LIST_FIRST (INSN_SPEC_BACK_DEPS (x
)) != NULL
)
4589 ready_remove (&ready
, i
);
4590 goto restart_debug_insn_loop
;
4593 for (i
= ready
.n_ready
- 1; i
>= 0; i
--)
4597 x
= ready_element (&ready
, i
);
4598 resolve_dependencies (x
);
4600 for (i
= 0; i
<= max_insn_queue_index
; i
++)
4603 while ((link
= insn_queue
[i
]) != NULL
)
4605 rtx x
= XEXP (link
, 0);
4606 insn_queue
[i
] = XEXP (link
, 1);
4607 QUEUE_INDEX (x
) = QUEUE_NOWHERE
;
4608 free_INSN_LIST_node (link
);
4609 resolve_dependencies (x
);
4617 fprintf (sched_dump
, ";;\tReady list (final): ");
4618 debug_ready_list (&ready
);
4621 if (modulo_ii
== 0 && current_sched_info
->queue_must_finish_empty
)
4622 /* Sanity check -- queue must be empty now. Meaningless if region has
4624 gcc_assert (!q_size
&& !ready
.n_ready
&& !ready
.n_debug
);
4625 else if (modulo_ii
== 0)
4627 /* We must maintain QUEUE_INDEX between blocks in region. */
4628 for (i
= ready
.n_ready
- 1; i
>= 0; i
--)
4632 x
= ready_element (&ready
, i
);
4633 QUEUE_INDEX (x
) = QUEUE_NOWHERE
;
4634 TODO_SPEC (x
) = HARD_DEP
;
4638 for (i
= 0; i
<= max_insn_queue_index
; i
++)
4641 for (link
= insn_queue
[i
]; link
; link
= XEXP (link
, 1))
4646 QUEUE_INDEX (x
) = QUEUE_NOWHERE
;
4647 TODO_SPEC (x
) = HARD_DEP
;
4649 free_INSN_LIST_list (&insn_queue
[i
]);
4655 commit_schedule (prev_head
, tail
, target_bb
);
4657 fprintf (sched_dump
, ";; total time = %d\n", clock_var
);
4660 last_scheduled_insn
= tail
;
4662 VEC_truncate (rtx
, scheduled_insns
, 0);
4664 if (!current_sched_info
->queue_must_finish_empty
4665 || haifa_recovery_bb_recently_added_p
)
4667 /* INSN_TICK (minimum clock tick at which the insn becomes
4668 ready) may be not correct for the insn in the subsequent
4669 blocks of the region. We should use a correct value of
4670 `clock_var' or modify INSN_TICK. It is better to keep
4671 clock_var value equal to 0 at the start of a basic block.
4672 Therefore we modify INSN_TICK here. */
4673 fix_inter_tick (NEXT_INSN (prev_head
), last_scheduled_insn
);
4676 if (targetm
.sched
.finish
)
4678 targetm
.sched
.finish (sched_dump
, sched_verbose
);
4679 /* Target might have added some instructions to the scheduled block
4680 in its md_finish () hook. These new insns don't have any data
4681 initialized and to identify them we extend h_i_d so that they'll
4683 sched_extend_luids ();
4687 fprintf (sched_dump
, ";; new head = %d\n;; new tail = %d\n\n",
4688 INSN_UID (head
), INSN_UID (tail
));
4690 /* Update head/tail boundaries. */
4691 head
= NEXT_INSN (prev_head
);
4692 tail
= last_scheduled_insn
;
4694 head
= restore_other_notes (head
, NULL
);
4696 current_sched_info
->head
= head
;
4697 current_sched_info
->tail
= tail
;
4699 free_backtrack_queue ();
4704 /* Set_priorities: compute priority of each insn in the block. */
4707 set_priorities (rtx head
, rtx tail
)
4711 int sched_max_insns_priority
=
4712 current_sched_info
->sched_max_insns_priority
;
4715 if (head
== tail
&& ! INSN_P (head
))
4720 prev_head
= PREV_INSN (head
);
4721 for (insn
= tail
; insn
!= prev_head
; insn
= PREV_INSN (insn
))
4727 (void) priority (insn
);
4729 gcc_assert (INSN_PRIORITY_KNOWN (insn
));
4731 sched_max_insns_priority
= MAX (sched_max_insns_priority
,
4732 INSN_PRIORITY (insn
));
4735 current_sched_info
->sched_max_insns_priority
= sched_max_insns_priority
;
4740 /* Set dump and sched_verbose for the desired debugging output. If no
4741 dump-file was specified, but -fsched-verbose=N (any N), print to stderr.
4742 For -fsched-verbose=N, N>=10, print everything to stderr. */
4744 setup_sched_dump (void)
4746 sched_verbose
= sched_verbose_param
;
4747 if (sched_verbose_param
== 0 && dump_file
)
4749 sched_dump
= ((sched_verbose_param
>= 10 || !dump_file
)
4750 ? stderr
: dump_file
);
4753 /* Initialize some global state for the scheduler. This function works
4754 with the common data shared between all the schedulers. It is called
4755 from the scheduler specific initialization routine. */
4760 /* Disable speculative loads in their presence if cc0 defined. */
4762 flag_schedule_speculative_load
= 0;
4765 if (targetm
.sched
.dispatch (NULL_RTX
, IS_DISPATCH_ON
))
4766 targetm
.sched
.dispatch_do (NULL_RTX
, DISPATCH_INIT
);
4768 sched_pressure_p
= (flag_sched_pressure
&& ! reload_completed
4769 && common_sched_info
->sched_pass_id
== SCHED_RGN_PASS
);
4771 if (sched_pressure_p
)
4772 ira_setup_eliminable_regset ();
4774 /* Initialize SPEC_INFO. */
4775 if (targetm
.sched
.set_sched_flags
)
4777 spec_info
= &spec_info_var
;
4778 targetm
.sched
.set_sched_flags (spec_info
);
4780 if (spec_info
->mask
!= 0)
4782 spec_info
->data_weakness_cutoff
=
4783 (PARAM_VALUE (PARAM_SCHED_SPEC_PROB_CUTOFF
) * MAX_DEP_WEAK
) / 100;
4784 spec_info
->control_weakness_cutoff
=
4785 (PARAM_VALUE (PARAM_SCHED_SPEC_PROB_CUTOFF
)
4786 * REG_BR_PROB_BASE
) / 100;
4789 /* So we won't read anything accidentally. */
4794 /* So we won't read anything accidentally. */
4797 /* Initialize issue_rate. */
4798 if (targetm
.sched
.issue_rate
)
4799 issue_rate
= targetm
.sched
.issue_rate ();
4803 if (cached_issue_rate
!= issue_rate
)
4805 cached_issue_rate
= issue_rate
;
4806 /* To invalidate max_lookahead_tries: */
4807 cached_first_cycle_multipass_dfa_lookahead
= 0;
4810 if (targetm
.sched
.first_cycle_multipass_dfa_lookahead
)
4811 dfa_lookahead
= targetm
.sched
.first_cycle_multipass_dfa_lookahead ();
4815 if (targetm
.sched
.init_dfa_pre_cycle_insn
)
4816 targetm
.sched
.init_dfa_pre_cycle_insn ();
4818 if (targetm
.sched
.init_dfa_post_cycle_insn
)
4819 targetm
.sched
.init_dfa_post_cycle_insn ();
4822 dfa_state_size
= state_size ();
4824 init_alias_analysis ();
4827 df_set_flags (DF_LR_RUN_DCE
);
4828 df_note_add_problem ();
4830 /* More problems needed for interloop dep calculation in SMS. */
4831 if (common_sched_info
->sched_pass_id
== SCHED_SMS_PASS
)
4833 df_rd_add_problem ();
4834 df_chain_add_problem (DF_DU_CHAIN
+ DF_UD_CHAIN
);
4839 /* Do not run DCE after reload, as this can kill nops inserted
4841 if (reload_completed
)
4842 df_clear_flags (DF_LR_RUN_DCE
);
4844 regstat_compute_calls_crossed ();
4846 if (targetm
.sched
.init_global
)
4847 targetm
.sched
.init_global (sched_dump
, sched_verbose
, get_max_uid () + 1);
4849 if (sched_pressure_p
)
4851 int i
, max_regno
= max_reg_num ();
4853 if (sched_dump
!= NULL
)
4854 /* We need info about pseudos for rtl dumps about pseudo
4855 classes and costs. */
4856 regstat_init_n_sets_and_refs ();
4857 ira_set_pseudo_classes (sched_verbose
? sched_dump
: NULL
);
4858 sched_regno_pressure_class
4859 = (enum reg_class
*) xmalloc (max_regno
* sizeof (enum reg_class
));
4860 for (i
= 0; i
< max_regno
; i
++)
4861 sched_regno_pressure_class
[i
]
4862 = (i
< FIRST_PSEUDO_REGISTER
4863 ? ira_pressure_class_translate
[REGNO_REG_CLASS (i
)]
4864 : ira_pressure_class_translate
[reg_allocno_class (i
)]);
4865 curr_reg_live
= BITMAP_ALLOC (NULL
);
4866 saved_reg_live
= BITMAP_ALLOC (NULL
);
4867 region_ref_regs
= BITMAP_ALLOC (NULL
);
4870 curr_state
= xmalloc (dfa_state_size
);
4873 static void haifa_init_only_bb (basic_block
, basic_block
);
4875 /* Initialize data structures specific to the Haifa scheduler. */
4877 haifa_sched_init (void)
4879 setup_sched_dump ();
4882 scheduled_insns
= VEC_alloc (rtx
, heap
, 0);
4884 if (spec_info
!= NULL
)
4886 sched_deps_info
->use_deps_list
= 1;
4887 sched_deps_info
->generate_spec_deps
= 1;
4890 /* Initialize luids, dependency caches, target and h_i_d for the
4893 bb_vec_t bbs
= VEC_alloc (basic_block
, heap
, n_basic_blocks
);
4899 VEC_quick_push (basic_block
, bbs
, bb
);
4900 sched_init_luids (bbs
);
4901 sched_deps_init (true);
4902 sched_extend_target ();
4903 haifa_init_h_i_d (bbs
);
4905 VEC_free (basic_block
, heap
, bbs
);
4908 sched_init_only_bb
= haifa_init_only_bb
;
4909 sched_split_block
= sched_split_block_1
;
4910 sched_create_empty_bb
= sched_create_empty_bb_1
;
4911 haifa_recovery_bb_ever_added_p
= false;
4913 nr_begin_data
= nr_begin_control
= nr_be_in_data
= nr_be_in_control
= 0;
4914 before_recovery
= 0;
4920 /* Finish work with the data specific to the Haifa scheduler. */
4922 haifa_sched_finish (void)
4924 sched_create_empty_bb
= NULL
;
4925 sched_split_block
= NULL
;
4926 sched_init_only_bb
= NULL
;
4928 if (spec_info
&& spec_info
->dump
)
4930 char c
= reload_completed
? 'a' : 'b';
4932 fprintf (spec_info
->dump
,
4933 ";; %s:\n", current_function_name ());
4935 fprintf (spec_info
->dump
,
4936 ";; Procedure %cr-begin-data-spec motions == %d\n",
4938 fprintf (spec_info
->dump
,
4939 ";; Procedure %cr-be-in-data-spec motions == %d\n",
4941 fprintf (spec_info
->dump
,
4942 ";; Procedure %cr-begin-control-spec motions == %d\n",
4943 c
, nr_begin_control
);
4944 fprintf (spec_info
->dump
,
4945 ";; Procedure %cr-be-in-control-spec motions == %d\n",
4946 c
, nr_be_in_control
);
4949 VEC_free (rtx
, heap
, scheduled_insns
);
4951 /* Finalize h_i_d, dependency caches, and luids for the whole
4952 function. Target will be finalized in md_global_finish (). */
4953 sched_deps_finish ();
4954 sched_finish_luids ();
4955 current_sched_info
= NULL
;
4959 /* Free global data used during insn scheduling. This function works with
4960 the common data shared between the schedulers. */
4965 haifa_finish_h_i_d ();
4966 if (sched_pressure_p
)
4968 if (regstat_n_sets_and_refs
!= NULL
)
4969 regstat_free_n_sets_and_refs ();
4970 free (sched_regno_pressure_class
);
4971 BITMAP_FREE (region_ref_regs
);
4972 BITMAP_FREE (saved_reg_live
);
4973 BITMAP_FREE (curr_reg_live
);
4977 if (targetm
.sched
.finish_global
)
4978 targetm
.sched
.finish_global (sched_dump
, sched_verbose
);
4980 end_alias_analysis ();
4982 regstat_free_calls_crossed ();
4987 /* Free all delay_pair structures that were recorded. */
4989 free_delay_pairs (void)
4993 htab_empty (delay_htab
);
4994 htab_empty (delay_htab_i2
);
4998 /* Fix INSN_TICKs of the instructions in the current block as well as
4999 INSN_TICKs of their dependents.
5000 HEAD and TAIL are the begin and the end of the current scheduled block. */
5002 fix_inter_tick (rtx head
, rtx tail
)
5004 /* Set of instructions with corrected INSN_TICK. */
5005 bitmap_head processed
;
5006 /* ??? It is doubtful if we should assume that cycle advance happens on
5007 basic block boundaries. Basically insns that are unconditionally ready
5008 on the start of the block are more preferable then those which have
5009 a one cycle dependency over insn from the previous block. */
5010 int next_clock
= clock_var
+ 1;
5012 bitmap_initialize (&processed
, 0);
5014 /* Iterates over scheduled instructions and fix their INSN_TICKs and
5015 INSN_TICKs of dependent instructions, so that INSN_TICKs are consistent
5016 across different blocks. */
5017 for (tail
= NEXT_INSN (tail
); head
!= tail
; head
= NEXT_INSN (head
))
5022 sd_iterator_def sd_it
;
5025 tick
= INSN_TICK (head
);
5026 gcc_assert (tick
>= MIN_TICK
);
5028 /* Fix INSN_TICK of instruction from just scheduled block. */
5029 if (bitmap_set_bit (&processed
, INSN_LUID (head
)))
5033 if (tick
< MIN_TICK
)
5036 INSN_TICK (head
) = tick
;
5039 FOR_EACH_DEP (head
, SD_LIST_RES_FORW
, sd_it
, dep
)
5043 next
= DEP_CON (dep
);
5044 tick
= INSN_TICK (next
);
5046 if (tick
!= INVALID_TICK
5047 /* If NEXT has its INSN_TICK calculated, fix it.
5048 If not - it will be properly calculated from
5049 scratch later in fix_tick_ready. */
5050 && bitmap_set_bit (&processed
, INSN_LUID (next
)))
5054 if (tick
< MIN_TICK
)
5057 if (tick
> INTER_TICK (next
))
5058 INTER_TICK (next
) = tick
;
5060 tick
= INTER_TICK (next
);
5062 INSN_TICK (next
) = tick
;
5067 bitmap_clear (&processed
);
5070 /* Check if NEXT is ready to be added to the ready or queue list.
5071 If "yes", add it to the proper list.
5073 -1 - is not ready yet,
5074 0 - added to the ready list,
5075 0 < N - queued for N cycles. */
5077 try_ready (rtx next
)
5079 ds_t old_ts
, new_ts
;
5081 old_ts
= TODO_SPEC (next
);
5083 gcc_assert (!(old_ts
& ~(SPECULATIVE
| HARD_DEP
| DEP_CONTROL
))
5084 && ((old_ts
& HARD_DEP
)
5085 || (old_ts
& SPECULATIVE
)
5086 || (old_ts
& DEP_CONTROL
)));
5088 new_ts
= recompute_todo_spec (next
);
5090 if (new_ts
& HARD_DEP
)
5091 gcc_assert (new_ts
== old_ts
5092 && QUEUE_INDEX (next
) == QUEUE_NOWHERE
);
5093 else if (current_sched_info
->new_ready
)
5094 new_ts
= current_sched_info
->new_ready (next
, new_ts
);
5096 /* * if !(old_ts & SPECULATIVE) (e.g. HARD_DEP or 0), then insn might
5097 have its original pattern or changed (speculative) one. This is due
5098 to changing ebb in region scheduling.
5099 * But if (old_ts & SPECULATIVE), then we are pretty sure that insn
5100 has speculative pattern.
5102 We can't assert (!(new_ts & HARD_DEP) || new_ts == old_ts) here because
5103 control-speculative NEXT could have been discarded by sched-rgn.c
5104 (the same case as when discarded by can_schedule_ready_p ()). */
5106 if ((new_ts
& SPECULATIVE
)
5107 /* If (old_ts == new_ts), then (old_ts & SPECULATIVE) and we don't
5108 need to change anything. */
5109 && new_ts
!= old_ts
)
5114 gcc_assert ((new_ts
& SPECULATIVE
) && !(new_ts
& ~SPECULATIVE
));
5116 res
= haifa_speculate_insn (next
, new_ts
, &new_pat
);
5121 /* It would be nice to change DEP_STATUS of all dependences,
5122 which have ((DEP_STATUS & SPECULATIVE) == new_ts) to HARD_DEP,
5123 so we won't reanalyze anything. */
5128 /* We follow the rule, that every speculative insn
5129 has non-null ORIG_PAT. */
5130 if (!ORIG_PAT (next
))
5131 ORIG_PAT (next
) = PATTERN (next
);
5135 if (!ORIG_PAT (next
))
5136 /* If we gonna to overwrite the original pattern of insn,
5138 ORIG_PAT (next
) = PATTERN (next
);
5140 res
= haifa_change_pattern (next
, new_pat
);
5149 /* We need to restore pattern only if (new_ts == 0), because otherwise it is
5150 either correct (new_ts & SPECULATIVE),
5151 or we simply don't care (new_ts & HARD_DEP). */
5153 gcc_assert (!ORIG_PAT (next
)
5154 || !IS_SPECULATION_BRANCHY_CHECK_P (next
));
5156 TODO_SPEC (next
) = new_ts
;
5158 if (new_ts
& HARD_DEP
)
5160 /* We can't assert (QUEUE_INDEX (next) == QUEUE_NOWHERE) here because
5161 control-speculative NEXT could have been discarded by sched-rgn.c
5162 (the same case as when discarded by can_schedule_ready_p ()). */
5163 /*gcc_assert (QUEUE_INDEX (next) == QUEUE_NOWHERE);*/
5165 change_queue_index (next
, QUEUE_NOWHERE
);
5169 else if (!(new_ts
& BEGIN_SPEC
)
5170 && ORIG_PAT (next
) && PREDICATED_PAT (next
) == NULL_RTX
5171 && !IS_SPECULATION_CHECK_P (next
))
5172 /* We should change pattern of every previously speculative
5173 instruction - and we determine if NEXT was speculative by using
5174 ORIG_PAT field. Except one case - speculation checks have ORIG_PAT
5175 pat too, so skip them. */
5177 bool success
= haifa_change_pattern (next
, ORIG_PAT (next
));
5178 gcc_assert (success
);
5179 ORIG_PAT (next
) = 0;
5182 if (sched_verbose
>= 2)
5184 fprintf (sched_dump
, ";;\t\tdependencies resolved: insn %s",
5185 (*current_sched_info
->print_insn
) (next
, 0));
5187 if (spec_info
&& spec_info
->dump
)
5189 if (new_ts
& BEGIN_DATA
)
5190 fprintf (spec_info
->dump
, "; data-spec;");
5191 if (new_ts
& BEGIN_CONTROL
)
5192 fprintf (spec_info
->dump
, "; control-spec;");
5193 if (new_ts
& BE_IN_CONTROL
)
5194 fprintf (spec_info
->dump
, "; in-control-spec;");
5196 if (TODO_SPEC (next
) & DEP_CONTROL
)
5197 fprintf (sched_dump
, " predicated");
5198 fprintf (sched_dump
, "\n");
5201 adjust_priority (next
);
5203 return fix_tick_ready (next
);
5206 /* Calculate INSN_TICK of NEXT and add it to either ready or queue list. */
5208 fix_tick_ready (rtx next
)
5212 if (!DEBUG_INSN_P (next
) && !sd_lists_empty_p (next
, SD_LIST_RES_BACK
))
5215 sd_iterator_def sd_it
;
5218 tick
= INSN_TICK (next
);
5219 /* if tick is not equal to INVALID_TICK, then update
5220 INSN_TICK of NEXT with the most recent resolved dependence
5221 cost. Otherwise, recalculate from scratch. */
5222 full_p
= (tick
== INVALID_TICK
);
5224 FOR_EACH_DEP (next
, SD_LIST_RES_BACK
, sd_it
, dep
)
5226 rtx pro
= DEP_PRO (dep
);
5229 gcc_assert (INSN_TICK (pro
) >= MIN_TICK
);
5231 tick1
= INSN_TICK (pro
) + dep_cost (dep
);
5242 INSN_TICK (next
) = tick
;
5244 delay
= tick
- clock_var
;
5245 if (delay
<= 0 || sched_pressure_p
)
5246 delay
= QUEUE_READY
;
5248 change_queue_index (next
, delay
);
5253 /* Move NEXT to the proper queue list with (DELAY >= 1),
5254 or add it to the ready list (DELAY == QUEUE_READY),
5255 or remove it from ready and queue lists at all (DELAY == QUEUE_NOWHERE). */
5257 change_queue_index (rtx next
, int delay
)
5259 int i
= QUEUE_INDEX (next
);
5261 gcc_assert (QUEUE_NOWHERE
<= delay
&& delay
<= max_insn_queue_index
5263 gcc_assert (i
!= QUEUE_SCHEDULED
);
5265 if ((delay
> 0 && NEXT_Q_AFTER (q_ptr
, delay
) == i
)
5266 || (delay
< 0 && delay
== i
))
5267 /* We have nothing to do. */
5270 /* Remove NEXT from wherever it is now. */
5271 if (i
== QUEUE_READY
)
5272 ready_remove_insn (next
);
5274 queue_remove (next
);
5276 /* Add it to the proper place. */
5277 if (delay
== QUEUE_READY
)
5278 ready_add (readyp
, next
, false);
5279 else if (delay
>= 1)
5280 queue_insn (next
, delay
, "change queue index");
5282 if (sched_verbose
>= 2)
5284 fprintf (sched_dump
, ";;\t\ttick updated: insn %s",
5285 (*current_sched_info
->print_insn
) (next
, 0));
5287 if (delay
== QUEUE_READY
)
5288 fprintf (sched_dump
, " into ready\n");
5289 else if (delay
>= 1)
5290 fprintf (sched_dump
, " into queue with cost=%d\n", delay
);
5292 fprintf (sched_dump
, " removed from ready or queue lists\n");
5296 static int sched_ready_n_insns
= -1;
5298 /* Initialize per region data structures. */
5300 sched_extend_ready_list (int new_sched_ready_n_insns
)
5304 if (sched_ready_n_insns
== -1)
5305 /* At the first call we need to initialize one more choice_stack
5309 sched_ready_n_insns
= 0;
5310 VEC_reserve (rtx
, heap
, scheduled_insns
, new_sched_ready_n_insns
);
5313 i
= sched_ready_n_insns
+ 1;
5315 ready
.veclen
= new_sched_ready_n_insns
+ issue_rate
;
5316 ready
.vec
= XRESIZEVEC (rtx
, ready
.vec
, ready
.veclen
);
5318 gcc_assert (new_sched_ready_n_insns
>= sched_ready_n_insns
);
5320 ready_try
= (char *) xrecalloc (ready_try
, new_sched_ready_n_insns
,
5321 sched_ready_n_insns
, sizeof (*ready_try
));
5323 /* We allocate +1 element to save initial state in the choice_stack[0]
5325 choice_stack
= XRESIZEVEC (struct choice_entry
, choice_stack
,
5326 new_sched_ready_n_insns
+ 1);
5328 for (; i
<= new_sched_ready_n_insns
; i
++)
5330 choice_stack
[i
].state
= xmalloc (dfa_state_size
);
5332 if (targetm
.sched
.first_cycle_multipass_init
)
5333 targetm
.sched
.first_cycle_multipass_init (&(choice_stack
[i
]
5337 sched_ready_n_insns
= new_sched_ready_n_insns
;
5340 /* Free per region data structures. */
5342 sched_finish_ready_list (void)
5353 for (i
= 0; i
<= sched_ready_n_insns
; i
++)
5355 if (targetm
.sched
.first_cycle_multipass_fini
)
5356 targetm
.sched
.first_cycle_multipass_fini (&(choice_stack
[i
]
5359 free (choice_stack
[i
].state
);
5361 free (choice_stack
);
5362 choice_stack
= NULL
;
5364 sched_ready_n_insns
= -1;
5368 haifa_luid_for_non_insn (rtx x
)
5370 gcc_assert (NOTE_P (x
) || LABEL_P (x
));
5375 /* Generates recovery code for INSN. */
5377 generate_recovery_code (rtx insn
)
5379 if (TODO_SPEC (insn
) & BEGIN_SPEC
)
5380 begin_speculative_block (insn
);
5382 /* Here we have insn with no dependencies to
5383 instructions other then CHECK_SPEC ones. */
5385 if (TODO_SPEC (insn
) & BE_IN_SPEC
)
5386 add_to_speculative_block (insn
);
5390 Tries to add speculative dependencies of type FS between instructions
5391 in deps_list L and TWIN. */
5393 process_insn_forw_deps_be_in_spec (rtx insn
, rtx twin
, ds_t fs
)
5395 sd_iterator_def sd_it
;
5398 FOR_EACH_DEP (insn
, SD_LIST_FORW
, sd_it
, dep
)
5403 consumer
= DEP_CON (dep
);
5405 ds
= DEP_STATUS (dep
);
5407 if (/* If we want to create speculative dep. */
5409 /* And we can do that because this is a true dep. */
5410 && (ds
& DEP_TYPES
) == DEP_TRUE
)
5412 gcc_assert (!(ds
& BE_IN_SPEC
));
5414 if (/* If this dep can be overcome with 'begin speculation'. */
5416 /* Then we have a choice: keep the dep 'begin speculative'
5417 or transform it into 'be in speculative'. */
5419 if (/* In try_ready we assert that if insn once became ready
5420 it can be removed from the ready (or queue) list only
5421 due to backend decision. Hence we can't let the
5422 probability of the speculative dep to decrease. */
5423 ds_weak (ds
) <= ds_weak (fs
))
5427 new_ds
= (ds
& ~BEGIN_SPEC
) | fs
;
5429 if (/* consumer can 'be in speculative'. */
5430 sched_insn_is_legitimate_for_speculation_p (consumer
,
5432 /* Transform it to be in speculative. */
5437 /* Mark the dep as 'be in speculative'. */
5442 dep_def _new_dep
, *new_dep
= &_new_dep
;
5444 init_dep_1 (new_dep
, twin
, consumer
, DEP_TYPE (dep
), ds
);
5445 sd_add_dep (new_dep
, false);
5450 /* Generates recovery code for BEGIN speculative INSN. */
5452 begin_speculative_block (rtx insn
)
5454 if (TODO_SPEC (insn
) & BEGIN_DATA
)
5456 if (TODO_SPEC (insn
) & BEGIN_CONTROL
)
5459 create_check_block_twin (insn
, false);
5461 TODO_SPEC (insn
) &= ~BEGIN_SPEC
;
5464 static void haifa_init_insn (rtx
);
5466 /* Generates recovery code for BE_IN speculative INSN. */
5468 add_to_speculative_block (rtx insn
)
5471 sd_iterator_def sd_it
;
5474 rtx_vec_t priorities_roots
;
5476 ts
= TODO_SPEC (insn
);
5477 gcc_assert (!(ts
& ~BE_IN_SPEC
));
5479 if (ts
& BE_IN_DATA
)
5481 if (ts
& BE_IN_CONTROL
)
5484 TODO_SPEC (insn
) &= ~BE_IN_SPEC
;
5485 gcc_assert (!TODO_SPEC (insn
));
5487 DONE_SPEC (insn
) |= ts
;
5489 /* First we convert all simple checks to branchy. */
5490 for (sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
5491 sd_iterator_cond (&sd_it
, &dep
);)
5493 rtx check
= DEP_PRO (dep
);
5495 if (IS_SPECULATION_SIMPLE_CHECK_P (check
))
5497 create_check_block_twin (check
, true);
5499 /* Restart search. */
5500 sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
5503 /* Continue search. */
5504 sd_iterator_next (&sd_it
);
5507 priorities_roots
= NULL
;
5508 clear_priorities (insn
, &priorities_roots
);
5515 /* Get the first backward dependency of INSN. */
5516 sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
5517 if (!sd_iterator_cond (&sd_it
, &dep
))
5518 /* INSN has no backward dependencies left. */
5521 gcc_assert ((DEP_STATUS (dep
) & BEGIN_SPEC
) == 0
5522 && (DEP_STATUS (dep
) & BE_IN_SPEC
) != 0
5523 && (DEP_STATUS (dep
) & DEP_TYPES
) == DEP_TRUE
);
5525 check
= DEP_PRO (dep
);
5527 gcc_assert (!IS_SPECULATION_CHECK_P (check
) && !ORIG_PAT (check
)
5528 && QUEUE_INDEX (check
) == QUEUE_NOWHERE
);
5530 rec
= BLOCK_FOR_INSN (check
);
5532 twin
= emit_insn_before (copy_insn (PATTERN (insn
)), BB_END (rec
));
5533 haifa_init_insn (twin
);
5535 sd_copy_back_deps (twin
, insn
, true);
5537 if (sched_verbose
&& spec_info
->dump
)
5538 /* INSN_BB (insn) isn't determined for twin insns yet.
5539 So we can't use current_sched_info->print_insn. */
5540 fprintf (spec_info
->dump
, ";;\t\tGenerated twin insn : %d/rec%d\n",
5541 INSN_UID (twin
), rec
->index
);
5543 twins
= alloc_INSN_LIST (twin
, twins
);
5545 /* Add dependences between TWIN and all appropriate
5546 instructions from REC. */
5547 FOR_EACH_DEP (insn
, SD_LIST_SPEC_BACK
, sd_it
, dep
)
5549 rtx pro
= DEP_PRO (dep
);
5551 gcc_assert (DEP_TYPE (dep
) == REG_DEP_TRUE
);
5553 /* INSN might have dependencies from the instructions from
5554 several recovery blocks. At this iteration we process those
5555 producers that reside in REC. */
5556 if (BLOCK_FOR_INSN (pro
) == rec
)
5558 dep_def _new_dep
, *new_dep
= &_new_dep
;
5560 init_dep (new_dep
, pro
, twin
, REG_DEP_TRUE
);
5561 sd_add_dep (new_dep
, false);
5565 process_insn_forw_deps_be_in_spec (insn
, twin
, ts
);
5567 /* Remove all dependencies between INSN and insns in REC. */
5568 for (sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
5569 sd_iterator_cond (&sd_it
, &dep
);)
5571 rtx pro
= DEP_PRO (dep
);
5573 if (BLOCK_FOR_INSN (pro
) == rec
)
5574 sd_delete_dep (sd_it
);
5576 sd_iterator_next (&sd_it
);
5580 /* We couldn't have added the dependencies between INSN and TWINS earlier
5581 because that would make TWINS appear in the INSN_BACK_DEPS (INSN). */
5586 twin
= XEXP (twins
, 0);
5589 dep_def _new_dep
, *new_dep
= &_new_dep
;
5591 init_dep (new_dep
, insn
, twin
, REG_DEP_OUTPUT
);
5592 sd_add_dep (new_dep
, false);
5595 twin
= XEXP (twins
, 1);
5596 free_INSN_LIST_node (twins
);
5600 calc_priorities (priorities_roots
);
5601 VEC_free (rtx
, heap
, priorities_roots
);
5604 /* Extends and fills with zeros (only the new part) array pointed to by P. */
5606 xrecalloc (void *p
, size_t new_nmemb
, size_t old_nmemb
, size_t size
)
5608 gcc_assert (new_nmemb
>= old_nmemb
);
5609 p
= XRESIZEVAR (void, p
, new_nmemb
* size
);
5610 memset (((char *) p
) + old_nmemb
* size
, 0, (new_nmemb
- old_nmemb
) * size
);
5615 Find fallthru edge from PRED. */
5617 find_fallthru_edge_from (basic_block pred
)
5622 succ
= pred
->next_bb
;
5623 gcc_assert (succ
->prev_bb
== pred
);
5625 if (EDGE_COUNT (pred
->succs
) <= EDGE_COUNT (succ
->preds
))
5627 e
= find_fallthru_edge (pred
->succs
);
5631 gcc_assert (e
->dest
== succ
);
5637 e
= find_fallthru_edge (succ
->preds
);
5641 gcc_assert (e
->src
== pred
);
5649 /* Extend per basic block data structures. */
5651 sched_extend_bb (void)
5655 /* The following is done to keep current_sched_info->next_tail non null. */
5656 insn
= BB_END (EXIT_BLOCK_PTR
->prev_bb
);
5657 if (NEXT_INSN (insn
) == 0
5660 /* Don't emit a NOTE if it would end up before a BARRIER. */
5661 && !BARRIER_P (NEXT_INSN (insn
))))
5663 rtx note
= emit_note_after (NOTE_INSN_DELETED
, insn
);
5664 /* Make insn appear outside BB. */
5665 set_block_for_insn (note
, NULL
);
5666 BB_END (EXIT_BLOCK_PTR
->prev_bb
) = insn
;
5670 /* Init per basic block data structures. */
5672 sched_init_bbs (void)
5677 /* Initialize BEFORE_RECOVERY variable. */
5679 init_before_recovery (basic_block
*before_recovery_ptr
)
5684 last
= EXIT_BLOCK_PTR
->prev_bb
;
5685 e
= find_fallthru_edge_from (last
);
5689 /* We create two basic blocks:
5690 1. Single instruction block is inserted right after E->SRC
5692 2. Empty block right before EXIT_BLOCK.
5693 Between these two blocks recovery blocks will be emitted. */
5695 basic_block single
, empty
;
5698 /* If the fallthrough edge to exit we've found is from the block we've
5699 created before, don't do anything more. */
5700 if (last
== after_recovery
)
5703 adding_bb_to_current_region_p
= false;
5705 single
= sched_create_empty_bb (last
);
5706 empty
= sched_create_empty_bb (single
);
5708 /* Add new blocks to the root loop. */
5709 if (current_loops
!= NULL
)
5711 add_bb_to_loop (single
, VEC_index (loop_p
, current_loops
->larray
, 0));
5712 add_bb_to_loop (empty
, VEC_index (loop_p
, current_loops
->larray
, 0));
5715 single
->count
= last
->count
;
5716 empty
->count
= last
->count
;
5717 single
->frequency
= last
->frequency
;
5718 empty
->frequency
= last
->frequency
;
5719 BB_COPY_PARTITION (single
, last
);
5720 BB_COPY_PARTITION (empty
, last
);
5722 redirect_edge_succ (e
, single
);
5723 make_single_succ_edge (single
, empty
, 0);
5724 make_single_succ_edge (empty
, EXIT_BLOCK_PTR
,
5725 EDGE_FALLTHRU
| EDGE_CAN_FALLTHRU
);
5727 label
= block_label (empty
);
5728 x
= emit_jump_insn_after (gen_jump (label
), BB_END (single
));
5729 JUMP_LABEL (x
) = label
;
5730 LABEL_NUSES (label
)++;
5731 haifa_init_insn (x
);
5733 emit_barrier_after (x
);
5735 sched_init_only_bb (empty
, NULL
);
5736 sched_init_only_bb (single
, NULL
);
5739 adding_bb_to_current_region_p
= true;
5740 before_recovery
= single
;
5741 after_recovery
= empty
;
5743 if (before_recovery_ptr
)
5744 *before_recovery_ptr
= before_recovery
;
5746 if (sched_verbose
>= 2 && spec_info
->dump
)
5747 fprintf (spec_info
->dump
,
5748 ";;\t\tFixed fallthru to EXIT : %d->>%d->%d->>EXIT\n",
5749 last
->index
, single
->index
, empty
->index
);
5752 before_recovery
= last
;
5755 /* Returns new recovery block. */
5757 sched_create_recovery_block (basic_block
*before_recovery_ptr
)
5763 haifa_recovery_bb_recently_added_p
= true;
5764 haifa_recovery_bb_ever_added_p
= true;
5766 init_before_recovery (before_recovery_ptr
);
5768 barrier
= get_last_bb_insn (before_recovery
);
5769 gcc_assert (BARRIER_P (barrier
));
5771 label
= emit_label_after (gen_label_rtx (), barrier
);
5773 rec
= create_basic_block (label
, label
, before_recovery
);
5775 /* A recovery block always ends with an unconditional jump. */
5776 emit_barrier_after (BB_END (rec
));
5778 if (BB_PARTITION (before_recovery
) != BB_UNPARTITIONED
)
5779 BB_SET_PARTITION (rec
, BB_COLD_PARTITION
);
5781 if (sched_verbose
&& spec_info
->dump
)
5782 fprintf (spec_info
->dump
, ";;\t\tGenerated recovery block rec%d\n",
5788 /* Create edges: FIRST_BB -> REC; FIRST_BB -> SECOND_BB; REC -> SECOND_BB
5789 and emit necessary jumps. */
5791 sched_create_recovery_edges (basic_block first_bb
, basic_block rec
,
5792 basic_block second_bb
)
5798 /* This is fixing of incoming edge. */
5799 /* ??? Which other flags should be specified? */
5800 if (BB_PARTITION (first_bb
) != BB_PARTITION (rec
))
5801 /* Partition type is the same, if it is "unpartitioned". */
5802 edge_flags
= EDGE_CROSSING
;
5806 make_edge (first_bb
, rec
, edge_flags
);
5807 label
= block_label (second_bb
);
5808 jump
= emit_jump_insn_after (gen_jump (label
), BB_END (rec
));
5809 JUMP_LABEL (jump
) = label
;
5810 LABEL_NUSES (label
)++;
5812 if (BB_PARTITION (second_bb
) != BB_PARTITION (rec
))
5813 /* Partition type is the same, if it is "unpartitioned". */
5815 /* Rewritten from cfgrtl.c. */
5816 if (flag_reorder_blocks_and_partition
5817 && targetm_common
.have_named_sections
)
5819 /* We don't need the same note for the check because
5820 any_condjump_p (check) == true. */
5821 add_reg_note (jump
, REG_CROSSING_JUMP
, NULL_RTX
);
5823 edge_flags
= EDGE_CROSSING
;
5828 make_single_succ_edge (rec
, second_bb
, edge_flags
);
5829 if (dom_info_available_p (CDI_DOMINATORS
))
5830 set_immediate_dominator (CDI_DOMINATORS
, rec
, first_bb
);
5833 /* This function creates recovery code for INSN. If MUTATE_P is nonzero,
5834 INSN is a simple check, that should be converted to branchy one. */
5836 create_check_block_twin (rtx insn
, bool mutate_p
)
5839 rtx label
, check
, twin
;
5841 sd_iterator_def sd_it
;
5843 dep_def _new_dep
, *new_dep
= &_new_dep
;
5846 gcc_assert (ORIG_PAT (insn
) != NULL_RTX
);
5849 todo_spec
= TODO_SPEC (insn
);
5852 gcc_assert (IS_SPECULATION_SIMPLE_CHECK_P (insn
)
5853 && (TODO_SPEC (insn
) & SPECULATIVE
) == 0);
5855 todo_spec
= CHECK_SPEC (insn
);
5858 todo_spec
&= SPECULATIVE
;
5860 /* Create recovery block. */
5861 if (mutate_p
|| targetm
.sched
.needs_block_p (todo_spec
))
5863 rec
= sched_create_recovery_block (NULL
);
5864 label
= BB_HEAD (rec
);
5868 rec
= EXIT_BLOCK_PTR
;
5873 check
= targetm
.sched
.gen_spec_check (insn
, label
, todo_spec
);
5875 if (rec
!= EXIT_BLOCK_PTR
)
5877 /* To have mem_reg alive at the beginning of second_bb,
5878 we emit check BEFORE insn, so insn after splitting
5879 insn will be at the beginning of second_bb, which will
5880 provide us with the correct life information. */
5881 check
= emit_jump_insn_before (check
, insn
);
5882 JUMP_LABEL (check
) = label
;
5883 LABEL_NUSES (label
)++;
5886 check
= emit_insn_before (check
, insn
);
5888 /* Extend data structures. */
5889 haifa_init_insn (check
);
5891 /* CHECK is being added to current region. Extend ready list. */
5892 gcc_assert (sched_ready_n_insns
!= -1);
5893 sched_extend_ready_list (sched_ready_n_insns
+ 1);
5895 if (current_sched_info
->add_remove_insn
)
5896 current_sched_info
->add_remove_insn (insn
, 0);
5898 RECOVERY_BLOCK (check
) = rec
;
5900 if (sched_verbose
&& spec_info
->dump
)
5901 fprintf (spec_info
->dump
, ";;\t\tGenerated check insn : %s\n",
5902 (*current_sched_info
->print_insn
) (check
, 0));
5904 gcc_assert (ORIG_PAT (insn
));
5906 /* Initialize TWIN (twin is a duplicate of original instruction
5907 in the recovery block). */
5908 if (rec
!= EXIT_BLOCK_PTR
)
5910 sd_iterator_def sd_it
;
5913 FOR_EACH_DEP (insn
, SD_LIST_RES_BACK
, sd_it
, dep
)
5914 if ((DEP_STATUS (dep
) & DEP_OUTPUT
) != 0)
5916 struct _dep _dep2
, *dep2
= &_dep2
;
5918 init_dep (dep2
, DEP_PRO (dep
), check
, REG_DEP_TRUE
);
5920 sd_add_dep (dep2
, true);
5923 twin
= emit_insn_after (ORIG_PAT (insn
), BB_END (rec
));
5924 haifa_init_insn (twin
);
5926 if (sched_verbose
&& spec_info
->dump
)
5927 /* INSN_BB (insn) isn't determined for twin insns yet.
5928 So we can't use current_sched_info->print_insn. */
5929 fprintf (spec_info
->dump
, ";;\t\tGenerated twin insn : %d/rec%d\n",
5930 INSN_UID (twin
), rec
->index
);
5934 ORIG_PAT (check
) = ORIG_PAT (insn
);
5935 HAS_INTERNAL_DEP (check
) = 1;
5937 /* ??? We probably should change all OUTPUT dependencies to
5941 /* Copy all resolved back dependencies of INSN to TWIN. This will
5942 provide correct value for INSN_TICK (TWIN). */
5943 sd_copy_back_deps (twin
, insn
, true);
5945 if (rec
!= EXIT_BLOCK_PTR
)
5946 /* In case of branchy check, fix CFG. */
5948 basic_block first_bb
, second_bb
;
5951 first_bb
= BLOCK_FOR_INSN (check
);
5952 second_bb
= sched_split_block (first_bb
, check
);
5954 sched_create_recovery_edges (first_bb
, rec
, second_bb
);
5956 sched_init_only_bb (second_bb
, first_bb
);
5957 sched_init_only_bb (rec
, EXIT_BLOCK_PTR
);
5959 jump
= BB_END (rec
);
5960 haifa_init_insn (jump
);
5963 /* Move backward dependences from INSN to CHECK and
5964 move forward dependences from INSN to TWIN. */
5966 /* First, create dependencies between INSN's producers and CHECK & TWIN. */
5967 FOR_EACH_DEP (insn
, SD_LIST_BACK
, sd_it
, dep
)
5969 rtx pro
= DEP_PRO (dep
);
5972 /* If BEGIN_DATA: [insn ~~TRUE~~> producer]:
5973 check --TRUE--> producer ??? or ANTI ???
5974 twin --TRUE--> producer
5975 twin --ANTI--> check
5977 If BEGIN_CONTROL: [insn ~~ANTI~~> producer]:
5978 check --ANTI--> producer
5979 twin --ANTI--> producer
5980 twin --ANTI--> check
5982 If BE_IN_SPEC: [insn ~~TRUE~~> producer]:
5983 check ~~TRUE~~> producer
5984 twin ~~TRUE~~> producer
5985 twin --ANTI--> check */
5987 ds
= DEP_STATUS (dep
);
5989 if (ds
& BEGIN_SPEC
)
5991 gcc_assert (!mutate_p
);
5995 init_dep_1 (new_dep
, pro
, check
, DEP_TYPE (dep
), ds
);
5996 sd_add_dep (new_dep
, false);
5998 if (rec
!= EXIT_BLOCK_PTR
)
6000 DEP_CON (new_dep
) = twin
;
6001 sd_add_dep (new_dep
, false);
6005 /* Second, remove backward dependencies of INSN. */
6006 for (sd_it
= sd_iterator_start (insn
, SD_LIST_SPEC_BACK
);
6007 sd_iterator_cond (&sd_it
, &dep
);)
6009 if ((DEP_STATUS (dep
) & BEGIN_SPEC
)
6011 /* We can delete this dep because we overcome it with
6012 BEGIN_SPECULATION. */
6013 sd_delete_dep (sd_it
);
6015 sd_iterator_next (&sd_it
);
6018 /* Future Speculations. Determine what BE_IN speculations will be like. */
6021 /* Fields (DONE_SPEC (x) & BEGIN_SPEC) and CHECK_SPEC (x) are set only
6024 gcc_assert (!DONE_SPEC (insn
));
6028 ds_t ts
= TODO_SPEC (insn
);
6030 DONE_SPEC (insn
) = ts
& BEGIN_SPEC
;
6031 CHECK_SPEC (check
) = ts
& BEGIN_SPEC
;
6033 /* Luckiness of future speculations solely depends upon initial
6034 BEGIN speculation. */
6035 if (ts
& BEGIN_DATA
)
6036 fs
= set_dep_weak (fs
, BE_IN_DATA
, get_dep_weak (ts
, BEGIN_DATA
));
6037 if (ts
& BEGIN_CONTROL
)
6038 fs
= set_dep_weak (fs
, BE_IN_CONTROL
,
6039 get_dep_weak (ts
, BEGIN_CONTROL
));
6042 CHECK_SPEC (check
) = CHECK_SPEC (insn
);
6044 /* Future speculations: call the helper. */
6045 process_insn_forw_deps_be_in_spec (insn
, twin
, fs
);
6047 if (rec
!= EXIT_BLOCK_PTR
)
6049 /* Which types of dependencies should we use here is,
6050 generally, machine-dependent question... But, for now,
6055 init_dep (new_dep
, insn
, check
, REG_DEP_TRUE
);
6056 sd_add_dep (new_dep
, false);
6058 init_dep (new_dep
, insn
, twin
, REG_DEP_OUTPUT
);
6059 sd_add_dep (new_dep
, false);
6063 if (spec_info
->dump
)
6064 fprintf (spec_info
->dump
, ";;\t\tRemoved simple check : %s\n",
6065 (*current_sched_info
->print_insn
) (insn
, 0));
6067 /* Remove all dependencies of the INSN. */
6069 sd_it
= sd_iterator_start (insn
, (SD_LIST_FORW
6071 | SD_LIST_RES_BACK
));
6072 while (sd_iterator_cond (&sd_it
, &dep
))
6073 sd_delete_dep (sd_it
);
6076 /* If former check (INSN) already was moved to the ready (or queue)
6077 list, add new check (CHECK) there too. */
6078 if (QUEUE_INDEX (insn
) != QUEUE_NOWHERE
)
6081 /* Remove old check from instruction stream and free its
6083 sched_remove_insn (insn
);
6086 init_dep (new_dep
, check
, twin
, REG_DEP_ANTI
);
6087 sd_add_dep (new_dep
, false);
6091 init_dep_1 (new_dep
, insn
, check
, REG_DEP_TRUE
, DEP_TRUE
| DEP_OUTPUT
);
6092 sd_add_dep (new_dep
, false);
6096 /* Fix priorities. If MUTATE_P is nonzero, this is not necessary,
6097 because it'll be done later in add_to_speculative_block. */
6099 rtx_vec_t priorities_roots
= NULL
;
6101 clear_priorities (twin
, &priorities_roots
);
6102 calc_priorities (priorities_roots
);
6103 VEC_free (rtx
, heap
, priorities_roots
);
6107 /* Removes dependency between instructions in the recovery block REC
6108 and usual region instructions. It keeps inner dependences so it
6109 won't be necessary to recompute them. */
6111 fix_recovery_deps (basic_block rec
)
6113 rtx note
, insn
, jump
, ready_list
= 0;
6114 bitmap_head in_ready
;
6117 bitmap_initialize (&in_ready
, 0);
6119 /* NOTE - a basic block note. */
6120 note
= NEXT_INSN (BB_HEAD (rec
));
6121 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
6122 insn
= BB_END (rec
);
6123 gcc_assert (JUMP_P (insn
));
6124 insn
= PREV_INSN (insn
);
6128 sd_iterator_def sd_it
;
6131 for (sd_it
= sd_iterator_start (insn
, SD_LIST_FORW
);
6132 sd_iterator_cond (&sd_it
, &dep
);)
6134 rtx consumer
= DEP_CON (dep
);
6136 if (BLOCK_FOR_INSN (consumer
) != rec
)
6138 sd_delete_dep (sd_it
);
6140 if (bitmap_set_bit (&in_ready
, INSN_LUID (consumer
)))
6141 ready_list
= alloc_INSN_LIST (consumer
, ready_list
);
6145 gcc_assert ((DEP_STATUS (dep
) & DEP_TYPES
) == DEP_TRUE
);
6147 sd_iterator_next (&sd_it
);
6151 insn
= PREV_INSN (insn
);
6153 while (insn
!= note
);
6155 bitmap_clear (&in_ready
);
6157 /* Try to add instructions to the ready or queue list. */
6158 for (link
= ready_list
; link
; link
= XEXP (link
, 1))
6159 try_ready (XEXP (link
, 0));
6160 free_INSN_LIST_list (&ready_list
);
6162 /* Fixing jump's dependences. */
6163 insn
= BB_HEAD (rec
);
6164 jump
= BB_END (rec
);
6166 gcc_assert (LABEL_P (insn
));
6167 insn
= NEXT_INSN (insn
);
6169 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
6170 add_jump_dependencies (insn
, jump
);
6173 /* Change pattern of INSN to NEW_PAT. Invalidate cached haifa
6174 instruction data. */
6176 haifa_change_pattern (rtx insn
, rtx new_pat
)
6178 sd_iterator_def sd_it
;
6182 t
= validate_change (insn
, &PATTERN (insn
), new_pat
, 0);
6185 dfa_clear_single_insn_cache (insn
);
6187 sd_it
= sd_iterator_start (insn
,
6188 SD_LIST_FORW
| SD_LIST_BACK
| SD_LIST_RES_BACK
);
6189 while (sd_iterator_cond (&sd_it
, &dep
))
6191 DEP_COST (dep
) = UNKNOWN_DEP_COST
;
6192 sd_iterator_next (&sd_it
);
6195 /* Invalidate INSN_COST, so it'll be recalculated. */
6196 INSN_COST (insn
) = -1;
6197 /* Invalidate INSN_TICK, so it'll be recalculated. */
6198 INSN_TICK (insn
) = INVALID_TICK
;
6202 /* -1 - can't speculate,
6203 0 - for speculation with REQUEST mode it is OK to use
6204 current instruction pattern,
6205 1 - need to change pattern for *NEW_PAT to be speculative. */
6207 sched_speculate_insn (rtx insn
, ds_t request
, rtx
*new_pat
)
6209 gcc_assert (current_sched_info
->flags
& DO_SPECULATION
6210 && (request
& SPECULATIVE
)
6211 && sched_insn_is_legitimate_for_speculation_p (insn
, request
));
6213 if ((request
& spec_info
->mask
) != request
)
6216 if (request
& BE_IN_SPEC
6217 && !(request
& BEGIN_SPEC
))
6220 return targetm
.sched
.speculate_insn (insn
, request
, new_pat
);
6224 haifa_speculate_insn (rtx insn
, ds_t request
, rtx
*new_pat
)
6226 gcc_assert (sched_deps_info
->generate_spec_deps
6227 && !IS_SPECULATION_CHECK_P (insn
));
6229 if (HAS_INTERNAL_DEP (insn
)
6230 || SCHED_GROUP_P (insn
))
6233 return sched_speculate_insn (insn
, request
, new_pat
);
6236 /* Print some information about block BB, which starts with HEAD and
6237 ends with TAIL, before scheduling it.
6238 I is zero, if scheduler is about to start with the fresh ebb. */
6240 dump_new_block_header (int i
, basic_block bb
, rtx head
, rtx tail
)
6243 fprintf (sched_dump
,
6244 ";; ======================================================\n");
6246 fprintf (sched_dump
,
6247 ";; =====================ADVANCING TO=====================\n");
6248 fprintf (sched_dump
,
6249 ";; -- basic block %d from %d to %d -- %s reload\n",
6250 bb
->index
, INSN_UID (head
), INSN_UID (tail
),
6251 (reload_completed
? "after" : "before"));
6252 fprintf (sched_dump
,
6253 ";; ======================================================\n");
6254 fprintf (sched_dump
, "\n");
6257 /* Unlink basic block notes and labels and saves them, so they
6258 can be easily restored. We unlink basic block notes in EBB to
6259 provide back-compatibility with the previous code, as target backends
6260 assume, that there'll be only instructions between
6261 current_sched_info->{head and tail}. We restore these notes as soon
6263 FIRST (LAST) is the first (last) basic block in the ebb.
6264 NB: In usual case (FIRST == LAST) nothing is really done. */
6266 unlink_bb_notes (basic_block first
, basic_block last
)
6268 /* We DON'T unlink basic block notes of the first block in the ebb. */
6272 bb_header
= XNEWVEC (rtx
, last_basic_block
);
6274 /* Make a sentinel. */
6275 if (last
->next_bb
!= EXIT_BLOCK_PTR
)
6276 bb_header
[last
->next_bb
->index
] = 0;
6278 first
= first
->next_bb
;
6281 rtx prev
, label
, note
, next
;
6283 label
= BB_HEAD (last
);
6284 if (LABEL_P (label
))
6285 note
= NEXT_INSN (label
);
6288 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
6290 prev
= PREV_INSN (label
);
6291 next
= NEXT_INSN (note
);
6292 gcc_assert (prev
&& next
);
6294 NEXT_INSN (prev
) = next
;
6295 PREV_INSN (next
) = prev
;
6297 bb_header
[last
->index
] = label
;
6302 last
= last
->prev_bb
;
6307 /* Restore basic block notes.
6308 FIRST is the first basic block in the ebb. */
6310 restore_bb_notes (basic_block first
)
6315 /* We DON'T unlink basic block notes of the first block in the ebb. */
6316 first
= first
->next_bb
;
6317 /* Remember: FIRST is actually a second basic block in the ebb. */
6319 while (first
!= EXIT_BLOCK_PTR
6320 && bb_header
[first
->index
])
6322 rtx prev
, label
, note
, next
;
6324 label
= bb_header
[first
->index
];
6325 prev
= PREV_INSN (label
);
6326 next
= NEXT_INSN (prev
);
6328 if (LABEL_P (label
))
6329 note
= NEXT_INSN (label
);
6332 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
6334 bb_header
[first
->index
] = 0;
6336 NEXT_INSN (prev
) = label
;
6337 NEXT_INSN (note
) = next
;
6338 PREV_INSN (next
) = note
;
6340 first
= first
->next_bb
;
6348 Fix CFG after both in- and inter-block movement of
6349 control_flow_insn_p JUMP. */
6351 fix_jump_move (rtx jump
)
6353 basic_block bb
, jump_bb
, jump_bb_next
;
6355 bb
= BLOCK_FOR_INSN (PREV_INSN (jump
));
6356 jump_bb
= BLOCK_FOR_INSN (jump
);
6357 jump_bb_next
= jump_bb
->next_bb
;
6359 gcc_assert (common_sched_info
->sched_pass_id
== SCHED_EBB_PASS
6360 || IS_SPECULATION_BRANCHY_CHECK_P (jump
));
6362 if (!NOTE_INSN_BASIC_BLOCK_P (BB_END (jump_bb_next
)))
6363 /* if jump_bb_next is not empty. */
6364 BB_END (jump_bb
) = BB_END (jump_bb_next
);
6366 if (BB_END (bb
) != PREV_INSN (jump
))
6367 /* Then there are instruction after jump that should be placed
6369 BB_END (jump_bb_next
) = BB_END (bb
);
6371 /* Otherwise jump_bb_next is empty. */
6372 BB_END (jump_bb_next
) = NEXT_INSN (BB_HEAD (jump_bb_next
));
6374 /* To make assertion in move_insn happy. */
6375 BB_END (bb
) = PREV_INSN (jump
);
6377 update_bb_for_insn (jump_bb_next
);
6380 /* Fix CFG after interblock movement of control_flow_insn_p JUMP. */
6382 move_block_after_check (rtx jump
)
6384 basic_block bb
, jump_bb
, jump_bb_next
;
6387 bb
= BLOCK_FOR_INSN (PREV_INSN (jump
));
6388 jump_bb
= BLOCK_FOR_INSN (jump
);
6389 jump_bb_next
= jump_bb
->next_bb
;
6391 update_bb_for_insn (jump_bb
);
6393 gcc_assert (IS_SPECULATION_CHECK_P (jump
)
6394 || IS_SPECULATION_CHECK_P (BB_END (jump_bb_next
)));
6396 unlink_block (jump_bb_next
);
6397 link_block (jump_bb_next
, bb
);
6401 move_succs (&(jump_bb
->succs
), bb
);
6402 move_succs (&(jump_bb_next
->succs
), jump_bb
);
6403 move_succs (&t
, jump_bb_next
);
6405 df_mark_solutions_dirty ();
6407 common_sched_info
->fix_recovery_cfg
6408 (bb
->index
, jump_bb
->index
, jump_bb_next
->index
);
6411 /* Helper function for move_block_after_check.
6412 This functions attaches edge vector pointed to by SUCCSP to
6415 move_succs (VEC(edge
,gc
) **succsp
, basic_block to
)
6420 gcc_assert (to
->succs
== 0);
6422 to
->succs
= *succsp
;
6424 FOR_EACH_EDGE (e
, ei
, to
->succs
)
6430 /* Remove INSN from the instruction stream.
6431 INSN should have any dependencies. */
6433 sched_remove_insn (rtx insn
)
6435 sd_finish_insn (insn
);
6437 change_queue_index (insn
, QUEUE_NOWHERE
);
6438 current_sched_info
->add_remove_insn (insn
, 1);
6442 /* Clear priorities of all instructions, that are forward dependent on INSN.
6443 Store in vector pointed to by ROOTS_PTR insns on which priority () should
6444 be invoked to initialize all cleared priorities. */
6446 clear_priorities (rtx insn
, rtx_vec_t
*roots_ptr
)
6448 sd_iterator_def sd_it
;
6450 bool insn_is_root_p
= true;
6452 gcc_assert (QUEUE_INDEX (insn
) != QUEUE_SCHEDULED
);
6454 FOR_EACH_DEP (insn
, SD_LIST_BACK
, sd_it
, dep
)
6456 rtx pro
= DEP_PRO (dep
);
6458 if (INSN_PRIORITY_STATUS (pro
) >= 0
6459 && QUEUE_INDEX (insn
) != QUEUE_SCHEDULED
)
6461 /* If DEP doesn't contribute to priority then INSN itself should
6462 be added to priority roots. */
6463 if (contributes_to_priority_p (dep
))
6464 insn_is_root_p
= false;
6466 INSN_PRIORITY_STATUS (pro
) = -1;
6467 clear_priorities (pro
, roots_ptr
);
6472 VEC_safe_push (rtx
, heap
, *roots_ptr
, insn
);
6475 /* Recompute priorities of instructions, whose priorities might have been
6476 changed. ROOTS is a vector of instructions whose priority computation will
6477 trigger initialization of all cleared priorities. */
6479 calc_priorities (rtx_vec_t roots
)
6484 FOR_EACH_VEC_ELT (rtx
, roots
, i
, insn
)
6489 /* Add dependences between JUMP and other instructions in the recovery
6490 block. INSN is the first insn the recovery block. */
6492 add_jump_dependencies (rtx insn
, rtx jump
)
6496 insn
= NEXT_INSN (insn
);
6500 if (dep_list_size (insn
) == 0)
6502 dep_def _new_dep
, *new_dep
= &_new_dep
;
6504 init_dep (new_dep
, insn
, jump
, REG_DEP_ANTI
);
6505 sd_add_dep (new_dep
, false);
6510 gcc_assert (!sd_lists_empty_p (jump
, SD_LIST_BACK
));
6513 /* Extend data structures for logical insn UID. */
6515 sched_extend_luids (void)
6517 int new_luids_max_uid
= get_max_uid () + 1;
6519 VEC_safe_grow_cleared (int, heap
, sched_luids
, new_luids_max_uid
);
6522 /* Initialize LUID for INSN. */
6524 sched_init_insn_luid (rtx insn
)
6526 int i
= INSN_P (insn
) ? 1 : common_sched_info
->luid_for_non_insn (insn
);
6531 luid
= sched_max_luid
;
6532 sched_max_luid
+= i
;
6537 SET_INSN_LUID (insn
, luid
);
6540 /* Initialize luids for BBS.
6541 The hook common_sched_info->luid_for_non_insn () is used to determine
6542 if notes, labels, etc. need luids. */
6544 sched_init_luids (bb_vec_t bbs
)
6549 sched_extend_luids ();
6550 FOR_EACH_VEC_ELT (basic_block
, bbs
, i
, bb
)
6554 FOR_BB_INSNS (bb
, insn
)
6555 sched_init_insn_luid (insn
);
6561 sched_finish_luids (void)
6563 VEC_free (int, heap
, sched_luids
);
6567 /* Return logical uid of INSN. Helpful while debugging. */
6569 insn_luid (rtx insn
)
6571 return INSN_LUID (insn
);
6574 /* Extend per insn data in the target. */
6576 sched_extend_target (void)
6578 if (targetm
.sched
.h_i_d_extended
)
6579 targetm
.sched
.h_i_d_extended ();
6582 /* Extend global scheduler structures (those, that live across calls to
6583 schedule_block) to include information about just emitted INSN. */
6587 int reserve
= (get_max_uid () + 1
6588 - VEC_length (haifa_insn_data_def
, h_i_d
));
6590 && ! VEC_space (haifa_insn_data_def
, h_i_d
, reserve
))
6592 VEC_safe_grow_cleared (haifa_insn_data_def
, heap
, h_i_d
,
6593 3 * get_max_uid () / 2);
6594 sched_extend_target ();
6598 /* Initialize h_i_d entry of the INSN with default values.
6599 Values, that are not explicitly initialized here, hold zero. */
6601 init_h_i_d (rtx insn
)
6603 if (INSN_LUID (insn
) > 0)
6605 INSN_COST (insn
) = -1;
6606 QUEUE_INDEX (insn
) = QUEUE_NOWHERE
;
6607 INSN_TICK (insn
) = INVALID_TICK
;
6608 INSN_EXACT_TICK (insn
) = INVALID_TICK
;
6609 INTER_TICK (insn
) = INVALID_TICK
;
6610 TODO_SPEC (insn
) = HARD_DEP
;
6614 /* Initialize haifa_insn_data for BBS. */
6616 haifa_init_h_i_d (bb_vec_t bbs
)
6622 FOR_EACH_VEC_ELT (basic_block
, bbs
, i
, bb
)
6626 FOR_BB_INSNS (bb
, insn
)
6631 /* Finalize haifa_insn_data. */
6633 haifa_finish_h_i_d (void)
6636 haifa_insn_data_t data
;
6637 struct reg_use_data
*use
, *next
;
6639 FOR_EACH_VEC_ELT (haifa_insn_data_def
, h_i_d
, i
, data
)
6641 free (data
->reg_pressure
);
6642 for (use
= data
->reg_use_list
; use
!= NULL
; use
= next
)
6644 next
= use
->next_insn_use
;
6648 VEC_free (haifa_insn_data_def
, heap
, h_i_d
);
6651 /* Init data for the new insn INSN. */
6653 haifa_init_insn (rtx insn
)
6655 gcc_assert (insn
!= NULL
);
6657 sched_extend_luids ();
6658 sched_init_insn_luid (insn
);
6659 sched_extend_target ();
6660 sched_deps_init (false);
6664 if (adding_bb_to_current_region_p
)
6666 sd_init_insn (insn
);
6668 /* Extend dependency caches by one element. */
6669 extend_dependency_caches (1, false);
6671 if (sched_pressure_p
)
6672 init_insn_reg_pressure_info (insn
);
6675 /* Init data for the new basic block BB which comes after AFTER. */
6677 haifa_init_only_bb (basic_block bb
, basic_block after
)
6679 gcc_assert (bb
!= NULL
);
6683 if (common_sched_info
->add_block
)
6684 /* This changes only data structures of the front-end. */
6685 common_sched_info
->add_block (bb
, after
);
6688 /* A generic version of sched_split_block (). */
6690 sched_split_block_1 (basic_block first_bb
, rtx after
)
6694 e
= split_block (first_bb
, after
);
6695 gcc_assert (e
->src
== first_bb
);
6697 /* sched_split_block emits note if *check == BB_END. Probably it
6698 is better to rip that note off. */
6703 /* A generic version of sched_create_empty_bb (). */
6705 sched_create_empty_bb_1 (basic_block after
)
6707 return create_empty_bb (after
);
6710 /* Insert PAT as an INSN into the schedule and update the necessary data
6711 structures to account for it. */
6713 sched_emit_insn (rtx pat
)
6715 rtx insn
= emit_insn_before (pat
, nonscheduled_insns_begin
);
6716 haifa_init_insn (insn
);
6718 if (current_sched_info
->add_remove_insn
)
6719 current_sched_info
->add_remove_insn (insn
, 0);
6721 (*current_sched_info
->begin_schedule_ready
) (insn
);
6722 VEC_safe_push (rtx
, heap
, scheduled_insns
, insn
);
6724 last_scheduled_insn
= insn
;
6728 /* This function returns a candidate satisfying dispatch constraints from
6732 ready_remove_first_dispatch (struct ready_list
*ready
)
6735 rtx insn
= ready_element (ready
, 0);
6737 if (ready
->n_ready
== 1
6738 || INSN_CODE (insn
) < 0
6740 || !active_insn_p (insn
)
6741 || targetm
.sched
.dispatch (insn
, FITS_DISPATCH_WINDOW
))
6742 return ready_remove_first (ready
);
6744 for (i
= 1; i
< ready
->n_ready
; i
++)
6746 insn
= ready_element (ready
, i
);
6748 if (INSN_CODE (insn
) < 0
6750 || !active_insn_p (insn
))
6753 if (targetm
.sched
.dispatch (insn
, FITS_DISPATCH_WINDOW
))
6755 /* Return ith element of ready. */
6756 insn
= ready_remove (ready
, i
);
6761 if (targetm
.sched
.dispatch (NULL_RTX
, DISPATCH_VIOLATION
))
6762 return ready_remove_first (ready
);
6764 for (i
= 1; i
< ready
->n_ready
; i
++)
6766 insn
= ready_element (ready
, i
);
6768 if (INSN_CODE (insn
) < 0
6770 || !active_insn_p (insn
))
6773 /* Return i-th element of ready. */
6774 if (targetm
.sched
.dispatch (insn
, IS_CMP
))
6775 return ready_remove (ready
, i
);
6778 return ready_remove_first (ready
);
6781 /* Get number of ready insn in the ready list. */
6784 number_in_ready (void)
6786 return ready
.n_ready
;
6789 /* Get number of ready's in the ready list. */
6792 get_ready_element (int i
)
6794 return ready_element (&ready
, i
);
6797 #endif /* INSN_SCHEDULING */