2012-10-23 Vladimir Makarov <vmakarov@redhat.com>
[official-gcc.git] / gcc / haifa-sched.c
blobfa80f246b423b5e4443defd5bf861563ed2d0380
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
13 version.
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
18 for more details.
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
55 remaining slots.
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
61 broken by
62 2. choose insn with least contribution to register pressure,
63 ties broken by
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
67 broken by
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
96 utilization.
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
101 of this case.
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. */
127 #include "config.h"
128 #include "system.h"
129 #include "coretypes.h"
130 #include "tm.h"
131 #include "diagnostic-core.h"
132 #include "hard-reg-set.h"
133 #include "rtl.h"
134 #include "tm_p.h"
135 #include "regs.h"
136 #include "function.h"
137 #include "flags.h"
138 #include "insn-config.h"
139 #include "insn-attr.h"
140 #include "except.h"
141 #include "recog.h"
142 #include "sched-int.h"
143 #include "target.h"
144 #include "common/common-target.h"
145 #include "params.h"
146 #include "vecprim.h"
147 #include "dbgcnt.h"
148 #include "cfgloop.h"
149 #include "ira.h"
150 #include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.h. */
151 #include "hashtab.h"
152 #include "dumpfile.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. */
160 int issue_rate;
162 /* This can be set to true by a backend if the scheduler should not
163 enable a DCE pass. */
164 bool sched_no_dce;
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
188 scheduled. */
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).
195 N=1: same as -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)
217 /* Cached cost of the instruction. Use insn_cost to get cost of the
218 insn. -1 here means that the field is not initialized. */
219 #define INSN_COST(INSN) (HID (INSN)->cost)
221 /* If INSN_TICK of an instruction is equal to INVALID_TICK,
222 then it should be recalculated from scratch. */
223 #define INVALID_TICK (-(max_insn_queue_index + 1))
224 /* The minimal value of the INSN_TICK of an instruction. */
225 #define MIN_TICK (-max_insn_queue_index)
227 /* List of important notes we must keep around. This is a pointer to the
228 last element in the list. */
229 rtx note_list;
231 static struct spec_info_def spec_info_var;
232 /* Description of the speculative part of the scheduling.
233 If NULL - no speculation. */
234 spec_info_t spec_info = NULL;
236 /* True, if recovery block was added during scheduling of current block.
237 Used to determine, if we need to fix INSN_TICKs. */
238 static bool haifa_recovery_bb_recently_added_p;
240 /* True, if recovery block was added during this scheduling pass.
241 Used to determine if we should have empty memory pools of dependencies
242 after finishing current region. */
243 bool haifa_recovery_bb_ever_added_p;
245 /* Counters of different types of speculative instructions. */
246 static int nr_begin_data, nr_be_in_data, nr_begin_control, nr_be_in_control;
248 /* Array used in {unlink, restore}_bb_notes. */
249 static rtx *bb_header = 0;
251 /* Basic block after which recovery blocks will be created. */
252 static basic_block before_recovery;
254 /* Basic block just before the EXIT_BLOCK and after recovery, if we have
255 created it. */
256 basic_block after_recovery;
258 /* FALSE if we add bb to another region, so we don't need to initialize it. */
259 bool adding_bb_to_current_region_p = true;
261 /* Queues, etc. */
263 /* An instruction is ready to be scheduled when all insns preceding it
264 have already been scheduled. It is important to ensure that all
265 insns which use its result will not be executed until its result
266 has been computed. An insn is maintained in one of four structures:
268 (P) the "Pending" set of insns which cannot be scheduled until
269 their dependencies have been satisfied.
270 (Q) the "Queued" set of insns that can be scheduled when sufficient
271 time has passed.
272 (R) the "Ready" list of unscheduled, uncommitted insns.
273 (S) the "Scheduled" list of insns.
275 Initially, all insns are either "Pending" or "Ready" depending on
276 whether their dependencies are satisfied.
278 Insns move from the "Ready" list to the "Scheduled" list as they
279 are committed to the schedule. As this occurs, the insns in the
280 "Pending" list have their dependencies satisfied and move to either
281 the "Ready" list or the "Queued" set depending on whether
282 sufficient time has passed to make them ready. As time passes,
283 insns move from the "Queued" set to the "Ready" list.
285 The "Pending" list (P) are the insns in the INSN_FORW_DEPS of the
286 unscheduled insns, i.e., those that are ready, queued, and pending.
287 The "Queued" set (Q) is implemented by the variable `insn_queue'.
288 The "Ready" list (R) is implemented by the variables `ready' and
289 `n_ready'.
290 The "Scheduled" list (S) is the new insn chain built by this pass.
292 The transition (R->S) is implemented in the scheduling loop in
293 `schedule_block' when the best insn to schedule is chosen.
294 The transitions (P->R and P->Q) are implemented in `schedule_insn' as
295 insns move from the ready list to the scheduled list.
296 The transition (Q->R) is implemented in 'queue_to_insn' as time
297 passes or stalls are introduced. */
299 /* Implement a circular buffer to delay instructions until sufficient
300 time has passed. For the new pipeline description interface,
301 MAX_INSN_QUEUE_INDEX is a power of two minus one which is not less
302 than maximal time of instruction execution computed by genattr.c on
303 the base maximal time of functional unit reservations and getting a
304 result. This is the longest time an insn may be queued. */
306 static rtx *insn_queue;
307 static int q_ptr = 0;
308 static int q_size = 0;
309 #define NEXT_Q(X) (((X)+1) & max_insn_queue_index)
310 #define NEXT_Q_AFTER(X, C) (((X)+C) & max_insn_queue_index)
312 #define QUEUE_SCHEDULED (-3)
313 #define QUEUE_NOWHERE (-2)
314 #define QUEUE_READY (-1)
315 /* QUEUE_SCHEDULED - INSN is scheduled.
316 QUEUE_NOWHERE - INSN isn't scheduled yet and is neither in
317 queue or ready list.
318 QUEUE_READY - INSN is in ready list.
319 N >= 0 - INSN queued for X [where NEXT_Q_AFTER (q_ptr, X) == N] cycles. */
321 #define QUEUE_INDEX(INSN) (HID (INSN)->queue_index)
323 /* The following variable value refers for all current and future
324 reservations of the processor units. */
325 state_t curr_state;
327 /* The following variable value is size of memory representing all
328 current and future reservations of the processor units. */
329 size_t dfa_state_size;
331 /* The following array is used to find the best insn from ready when
332 the automaton pipeline interface is used. */
333 char *ready_try = NULL;
335 /* The ready list. */
336 struct ready_list ready = {NULL, 0, 0, 0, 0};
338 /* The pointer to the ready list (to be removed). */
339 static struct ready_list *readyp = &ready;
341 /* Scheduling clock. */
342 static int clock_var;
344 /* Clock at which the previous instruction was issued. */
345 static int last_clock_var;
347 /* Set to true if, when queuing a shadow insn, we discover that it would be
348 scheduled too late. */
349 static bool must_backtrack;
351 /* The following variable value is number of essential insns issued on
352 the current cycle. An insn is essential one if it changes the
353 processors state. */
354 int cycle_issued_insns;
356 /* This records the actual schedule. It is built up during the main phase
357 of schedule_block, and afterwards used to reorder the insns in the RTL. */
358 static VEC(rtx, heap) *scheduled_insns;
360 static int may_trap_exp (const_rtx, int);
362 /* Nonzero iff the address is comprised from at most 1 register. */
363 #define CONST_BASED_ADDRESS_P(x) \
364 (REG_P (x) \
365 || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
366 || (GET_CODE (x) == LO_SUM)) \
367 && (CONSTANT_P (XEXP (x, 0)) \
368 || CONSTANT_P (XEXP (x, 1)))))
370 /* Returns a class that insn with GET_DEST(insn)=x may belong to,
371 as found by analyzing insn's expression. */
374 static int haifa_luid_for_non_insn (rtx x);
376 /* Haifa version of sched_info hooks common to all headers. */
377 const struct common_sched_info_def haifa_common_sched_info =
379 NULL, /* fix_recovery_cfg */
380 NULL, /* add_block */
381 NULL, /* estimate_number_of_insns */
382 haifa_luid_for_non_insn, /* luid_for_non_insn */
383 SCHED_PASS_UNKNOWN /* sched_pass_id */
386 /* Mapping from instruction UID to its Logical UID. */
387 VEC (int, heap) *sched_luids = NULL;
389 /* Next LUID to assign to an instruction. */
390 int sched_max_luid = 1;
392 /* Haifa Instruction Data. */
393 VEC (haifa_insn_data_def, heap) *h_i_d = NULL;
395 void (* sched_init_only_bb) (basic_block, basic_block);
397 /* Split block function. Different schedulers might use different functions
398 to handle their internal data consistent. */
399 basic_block (* sched_split_block) (basic_block, rtx);
401 /* Create empty basic block after the specified block. */
402 basic_block (* sched_create_empty_bb) (basic_block);
404 /* Return the number of cycles until INSN is expected to be ready.
405 Return zero if it already is. */
406 static int
407 insn_delay (rtx insn)
409 return MAX (INSN_TICK (insn) - clock_var, 0);
412 static int
413 may_trap_exp (const_rtx x, int is_store)
415 enum rtx_code code;
417 if (x == 0)
418 return TRAP_FREE;
419 code = GET_CODE (x);
420 if (is_store)
422 if (code == MEM && may_trap_p (x))
423 return TRAP_RISKY;
424 else
425 return TRAP_FREE;
427 if (code == MEM)
429 /* The insn uses memory: a volatile load. */
430 if (MEM_VOLATILE_P (x))
431 return IRISKY;
432 /* An exception-free load. */
433 if (!may_trap_p (x))
434 return IFREE;
435 /* A load with 1 base register, to be further checked. */
436 if (CONST_BASED_ADDRESS_P (XEXP (x, 0)))
437 return PFREE_CANDIDATE;
438 /* No info on the load, to be further checked. */
439 return PRISKY_CANDIDATE;
441 else
443 const char *fmt;
444 int i, insn_class = TRAP_FREE;
446 /* Neither store nor load, check if it may cause a trap. */
447 if (may_trap_p (x))
448 return TRAP_RISKY;
449 /* Recursive step: walk the insn... */
450 fmt = GET_RTX_FORMAT (code);
451 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
453 if (fmt[i] == 'e')
455 int tmp_class = may_trap_exp (XEXP (x, i), is_store);
456 insn_class = WORST_CLASS (insn_class, tmp_class);
458 else if (fmt[i] == 'E')
460 int j;
461 for (j = 0; j < XVECLEN (x, i); j++)
463 int tmp_class = may_trap_exp (XVECEXP (x, i, j), is_store);
464 insn_class = WORST_CLASS (insn_class, tmp_class);
465 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
466 break;
469 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
470 break;
472 return insn_class;
476 /* Classifies rtx X of an insn for the purpose of verifying that X can be
477 executed speculatively (and consequently the insn can be moved
478 speculatively), by examining X, returning:
479 TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
480 TRAP_FREE: non-load insn.
481 IFREE: load from a globally safe location.
482 IRISKY: volatile load.
483 PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
484 being either PFREE or PRISKY. */
486 static int
487 haifa_classify_rtx (const_rtx x)
489 int tmp_class = TRAP_FREE;
490 int insn_class = TRAP_FREE;
491 enum rtx_code code;
493 if (GET_CODE (x) == PARALLEL)
495 int i, len = XVECLEN (x, 0);
497 for (i = len - 1; i >= 0; i--)
499 tmp_class = haifa_classify_rtx (XVECEXP (x, 0, i));
500 insn_class = WORST_CLASS (insn_class, tmp_class);
501 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
502 break;
505 else
507 code = GET_CODE (x);
508 switch (code)
510 case CLOBBER:
511 /* Test if it is a 'store'. */
512 tmp_class = may_trap_exp (XEXP (x, 0), 1);
513 break;
514 case SET:
515 /* Test if it is a store. */
516 tmp_class = may_trap_exp (SET_DEST (x), 1);
517 if (tmp_class == TRAP_RISKY)
518 break;
519 /* Test if it is a load. */
520 tmp_class =
521 WORST_CLASS (tmp_class,
522 may_trap_exp (SET_SRC (x), 0));
523 break;
524 case COND_EXEC:
525 tmp_class = haifa_classify_rtx (COND_EXEC_CODE (x));
526 if (tmp_class == TRAP_RISKY)
527 break;
528 tmp_class = WORST_CLASS (tmp_class,
529 may_trap_exp (COND_EXEC_TEST (x), 0));
530 break;
531 case TRAP_IF:
532 tmp_class = TRAP_RISKY;
533 break;
534 default:;
536 insn_class = tmp_class;
539 return insn_class;
543 haifa_classify_insn (const_rtx insn)
545 return haifa_classify_rtx (PATTERN (insn));
548 /* After the scheduler initialization function has been called, this function
549 can be called to enable modulo scheduling. II is the initiation interval
550 we should use, it affects the delays for delay_pairs that were recorded as
551 separated by a given number of stages.
553 MAX_STAGES provides us with a limit
554 after which we give up scheduling; the caller must have unrolled at least
555 as many copies of the loop body and recorded delay_pairs for them.
557 INSNS is the number of real (non-debug) insns in one iteration of
558 the loop. MAX_UID can be used to test whether an insn belongs to
559 the first iteration of the loop; all of them have a uid lower than
560 MAX_UID. */
561 void
562 set_modulo_params (int ii, int max_stages, int insns, int max_uid)
564 modulo_ii = ii;
565 modulo_max_stages = max_stages;
566 modulo_n_insns = insns;
567 modulo_iter0_max_uid = max_uid;
568 modulo_backtracks_left = PARAM_VALUE (PARAM_MAX_MODULO_BACKTRACK_ATTEMPTS);
571 /* A structure to record a pair of insns where the first one is a real
572 insn that has delay slots, and the second is its delayed shadow.
573 I1 is scheduled normally and will emit an assembly instruction,
574 while I2 describes the side effect that takes place at the
575 transition between cycles CYCLES and (CYCLES + 1) after I1. */
576 struct delay_pair
578 struct delay_pair *next_same_i1;
579 rtx i1, i2;
580 int cycles;
581 /* When doing modulo scheduling, we a delay_pair can also be used to
582 show that I1 and I2 are the same insn in a different stage. If that
583 is the case, STAGES will be nonzero. */
584 int stages;
587 /* Two hash tables to record delay_pairs, one indexed by I1 and the other
588 indexed by I2. */
589 static htab_t delay_htab;
590 static htab_t delay_htab_i2;
592 /* Called through htab_traverse. Walk the hashtable using I2 as
593 index, and delete all elements involving an UID higher than
594 that pointed to by *DATA. */
595 static int
596 htab_i2_traverse (void **slot, void *data)
598 int maxuid = *(int *)data;
599 struct delay_pair *p = *(struct delay_pair **)slot;
600 if (INSN_UID (p->i2) >= maxuid || INSN_UID (p->i1) >= maxuid)
602 htab_clear_slot (delay_htab_i2, slot);
604 return 1;
607 /* Called through htab_traverse. Walk the hashtable using I2 as
608 index, and delete all elements involving an UID higher than
609 that pointed to by *DATA. */
610 static int
611 htab_i1_traverse (void **slot, void *data)
613 int maxuid = *(int *)data;
614 struct delay_pair **pslot = (struct delay_pair **)slot;
615 struct delay_pair *p, *first, **pprev;
617 if (INSN_UID ((*pslot)->i1) >= maxuid)
619 htab_clear_slot (delay_htab, slot);
620 return 1;
622 pprev = &first;
623 for (p = *pslot; p; p = p->next_same_i1)
625 if (INSN_UID (p->i2) < maxuid)
627 *pprev = p;
628 pprev = &p->next_same_i1;
631 *pprev = NULL;
632 if (first == NULL)
633 htab_clear_slot (delay_htab, slot);
634 else
635 *pslot = first;
636 return 1;
639 /* Discard all delay pairs which involve an insn with an UID higher
640 than MAX_UID. */
641 void
642 discard_delay_pairs_above (int max_uid)
644 htab_traverse (delay_htab, htab_i1_traverse, &max_uid);
645 htab_traverse (delay_htab_i2, htab_i2_traverse, &max_uid);
648 /* Returns a hash value for X (which really is a delay_pair), based on
649 hashing just I1. */
650 static hashval_t
651 delay_hash_i1 (const void *x)
653 return htab_hash_pointer (((const struct delay_pair *) x)->i1);
656 /* Returns a hash value for X (which really is a delay_pair), based on
657 hashing just I2. */
658 static hashval_t
659 delay_hash_i2 (const void *x)
661 return htab_hash_pointer (((const struct delay_pair *) x)->i2);
664 /* Return nonzero if I1 of pair X is the same as that of pair Y. */
665 static int
666 delay_i1_eq (const void *x, const void *y)
668 return ((const struct delay_pair *) x)->i1 == y;
671 /* Return nonzero if I2 of pair X is the same as that of pair Y. */
672 static int
673 delay_i2_eq (const void *x, const void *y)
675 return ((const struct delay_pair *) x)->i2 == y;
678 /* This function can be called by a port just before it starts the final
679 scheduling pass. It records the fact that an instruction with delay
680 slots has been split into two insns, I1 and I2. The first one will be
681 scheduled normally and initiates the operation. The second one is a
682 shadow which must follow a specific number of cycles after I1; its only
683 purpose is to show the side effect that occurs at that cycle in the RTL.
684 If a JUMP_INSN or a CALL_INSN has been split, I1 should be a normal INSN,
685 while I2 retains the original insn type.
687 There are two ways in which the number of cycles can be specified,
688 involving the CYCLES and STAGES arguments to this function. If STAGES
689 is zero, we just use the value of CYCLES. Otherwise, STAGES is a factor
690 which is multiplied by MODULO_II to give the number of cycles. This is
691 only useful if the caller also calls set_modulo_params to enable modulo
692 scheduling. */
694 void
695 record_delay_slot_pair (rtx i1, rtx i2, int cycles, int stages)
697 struct delay_pair *p = XNEW (struct delay_pair);
698 struct delay_pair **slot;
700 p->i1 = i1;
701 p->i2 = i2;
702 p->cycles = cycles;
703 p->stages = stages;
705 if (!delay_htab)
707 delay_htab = htab_create (10, delay_hash_i1, delay_i1_eq, NULL);
708 delay_htab_i2 = htab_create (10, delay_hash_i2, delay_i2_eq, free);
710 slot = ((struct delay_pair **)
711 htab_find_slot_with_hash (delay_htab, i1, htab_hash_pointer (i1),
712 INSERT));
713 p->next_same_i1 = *slot;
714 *slot = p;
715 slot = ((struct delay_pair **)
716 htab_find_slot_with_hash (delay_htab_i2, i2, htab_hash_pointer (i2),
717 INSERT));
718 *slot = p;
721 /* Examine the delay pair hashtable to see if INSN is a shadow for another,
722 and return the other insn if so. Return NULL otherwise. */
724 real_insn_for_shadow (rtx insn)
726 struct delay_pair *pair;
728 if (delay_htab == NULL)
729 return NULL_RTX;
731 pair
732 = (struct delay_pair *)htab_find_with_hash (delay_htab_i2, insn,
733 htab_hash_pointer (insn));
734 if (!pair || pair->stages > 0)
735 return NULL_RTX;
736 return pair->i1;
739 /* For a pair P of insns, return the fixed distance in cycles from the first
740 insn after which the second must be scheduled. */
741 static int
742 pair_delay (struct delay_pair *p)
744 if (p->stages == 0)
745 return p->cycles;
746 else
747 return p->stages * modulo_ii;
750 /* Given an insn INSN, add a dependence on its delayed shadow if it
751 has one. Also try to find situations where shadows depend on each other
752 and add dependencies to the real insns to limit the amount of backtracking
753 needed. */
754 void
755 add_delay_dependencies (rtx insn)
757 struct delay_pair *pair;
758 sd_iterator_def sd_it;
759 dep_t dep;
761 if (!delay_htab)
762 return;
764 pair
765 = (struct delay_pair *)htab_find_with_hash (delay_htab_i2, insn,
766 htab_hash_pointer (insn));
767 if (!pair)
768 return;
769 add_dependence (insn, pair->i1, REG_DEP_ANTI);
770 if (pair->stages)
771 return;
773 FOR_EACH_DEP (pair->i2, SD_LIST_BACK, sd_it, dep)
775 rtx pro = DEP_PRO (dep);
776 struct delay_pair *other_pair
777 = (struct delay_pair *)htab_find_with_hash (delay_htab_i2, pro,
778 htab_hash_pointer (pro));
779 if (!other_pair || other_pair->stages)
780 continue;
781 if (pair_delay (other_pair) >= pair_delay (pair))
783 if (sched_verbose >= 4)
785 fprintf (sched_dump, ";;\tadding dependence %d <- %d\n",
786 INSN_UID (other_pair->i1),
787 INSN_UID (pair->i1));
788 fprintf (sched_dump, ";;\tpair1 %d <- %d, cost %d\n",
789 INSN_UID (pair->i1),
790 INSN_UID (pair->i2),
791 pair_delay (pair));
792 fprintf (sched_dump, ";;\tpair2 %d <- %d, cost %d\n",
793 INSN_UID (other_pair->i1),
794 INSN_UID (other_pair->i2),
795 pair_delay (other_pair));
797 add_dependence (pair->i1, other_pair->i1, REG_DEP_ANTI);
802 /* Forward declarations. */
804 static int priority (rtx);
805 static int rank_for_schedule (const void *, const void *);
806 static void swap_sort (rtx *, int);
807 static void queue_insn (rtx, int, const char *);
808 static int schedule_insn (rtx);
809 static void adjust_priority (rtx);
810 static void advance_one_cycle (void);
811 static void extend_h_i_d (void);
814 /* Notes handling mechanism:
815 =========================
816 Generally, NOTES are saved before scheduling and restored after scheduling.
817 The scheduler distinguishes between two types of notes:
819 (1) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes:
820 Before scheduling a region, a pointer to the note is added to the insn
821 that follows or precedes it. (This happens as part of the data dependence
822 computation). After scheduling an insn, the pointer contained in it is
823 used for regenerating the corresponding note (in reemit_notes).
825 (2) All other notes (e.g. INSN_DELETED): Before scheduling a block,
826 these notes are put in a list (in rm_other_notes() and
827 unlink_other_notes ()). After scheduling the block, these notes are
828 inserted at the beginning of the block (in schedule_block()). */
830 static void ready_add (struct ready_list *, rtx, bool);
831 static rtx ready_remove_first (struct ready_list *);
832 static rtx ready_remove_first_dispatch (struct ready_list *ready);
834 static void queue_to_ready (struct ready_list *);
835 static int early_queue_to_ready (state_t, struct ready_list *);
837 static void debug_ready_list (struct ready_list *);
839 /* The following functions are used to implement multi-pass scheduling
840 on the first cycle. */
841 static rtx ready_remove (struct ready_list *, int);
842 static void ready_remove_insn (rtx);
844 static void fix_inter_tick (rtx, rtx);
845 static int fix_tick_ready (rtx);
846 static void change_queue_index (rtx, int);
848 /* The following functions are used to implement scheduling of data/control
849 speculative instructions. */
851 static void extend_h_i_d (void);
852 static void init_h_i_d (rtx);
853 static int haifa_speculate_insn (rtx, ds_t, rtx *);
854 static void generate_recovery_code (rtx);
855 static void process_insn_forw_deps_be_in_spec (rtx, rtx, ds_t);
856 static void begin_speculative_block (rtx);
857 static void add_to_speculative_block (rtx);
858 static void init_before_recovery (basic_block *);
859 static void create_check_block_twin (rtx, bool);
860 static void fix_recovery_deps (basic_block);
861 static bool haifa_change_pattern (rtx, rtx);
862 static void dump_new_block_header (int, basic_block, rtx, rtx);
863 static void restore_bb_notes (basic_block);
864 static void fix_jump_move (rtx);
865 static void move_block_after_check (rtx);
866 static void move_succs (VEC(edge,gc) **, basic_block);
867 static void sched_remove_insn (rtx);
868 static void clear_priorities (rtx, rtx_vec_t *);
869 static void calc_priorities (rtx_vec_t);
870 static void add_jump_dependencies (rtx, rtx);
872 #endif /* INSN_SCHEDULING */
874 /* Point to state used for the current scheduling pass. */
875 struct haifa_sched_info *current_sched_info;
877 #ifndef INSN_SCHEDULING
878 void
879 schedule_insns (void)
882 #else
884 /* Do register pressure sensitive insn scheduling if the flag is set
885 up. */
886 enum sched_pressure_algorithm sched_pressure;
888 /* Map regno -> its pressure class. The map defined only when
889 SCHED_PRESSURE != SCHED_PRESSURE_NONE. */
890 enum reg_class *sched_regno_pressure_class;
892 /* The current register pressure. Only elements corresponding pressure
893 classes are defined. */
894 static int curr_reg_pressure[N_REG_CLASSES];
896 /* Saved value of the previous array. */
897 static int saved_reg_pressure[N_REG_CLASSES];
899 /* Register living at given scheduling point. */
900 static bitmap curr_reg_live;
902 /* Saved value of the previous array. */
903 static bitmap saved_reg_live;
905 /* Registers mentioned in the current region. */
906 static bitmap region_ref_regs;
908 /* Initiate register pressure relative info for scheduling the current
909 region. Currently it is only clearing register mentioned in the
910 current region. */
911 void
912 sched_init_region_reg_pressure_info (void)
914 bitmap_clear (region_ref_regs);
917 /* PRESSURE[CL] describes the pressure on register class CL. Update it
918 for the birth (if BIRTH_P) or death (if !BIRTH_P) of register REGNO.
919 LIVE tracks the set of live registers; if it is null, assume that
920 every birth or death is genuine. */
921 static inline void
922 mark_regno_birth_or_death (bitmap live, int *pressure, int regno, bool birth_p)
924 enum reg_class pressure_class;
926 pressure_class = sched_regno_pressure_class[regno];
927 if (regno >= FIRST_PSEUDO_REGISTER)
929 if (pressure_class != NO_REGS)
931 if (birth_p)
933 if (!live || bitmap_set_bit (live, regno))
934 pressure[pressure_class]
935 += (ira_reg_class_max_nregs
936 [pressure_class][PSEUDO_REGNO_MODE (regno)]);
938 else
940 if (!live || bitmap_clear_bit (live, regno))
941 pressure[pressure_class]
942 -= (ira_reg_class_max_nregs
943 [pressure_class][PSEUDO_REGNO_MODE (regno)]);
947 else if (pressure_class != NO_REGS
948 && ! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
950 if (birth_p)
952 if (!live || bitmap_set_bit (live, regno))
953 pressure[pressure_class]++;
955 else
957 if (!live || bitmap_clear_bit (live, regno))
958 pressure[pressure_class]--;
963 /* Initiate current register pressure related info from living
964 registers given by LIVE. */
965 static void
966 initiate_reg_pressure_info (bitmap live)
968 int i;
969 unsigned int j;
970 bitmap_iterator bi;
972 for (i = 0; i < ira_pressure_classes_num; i++)
973 curr_reg_pressure[ira_pressure_classes[i]] = 0;
974 bitmap_clear (curr_reg_live);
975 EXECUTE_IF_SET_IN_BITMAP (live, 0, j, bi)
976 if (sched_pressure == SCHED_PRESSURE_MODEL
977 || current_nr_blocks == 1
978 || bitmap_bit_p (region_ref_regs, j))
979 mark_regno_birth_or_death (curr_reg_live, curr_reg_pressure, j, true);
982 /* Mark registers in X as mentioned in the current region. */
983 static void
984 setup_ref_regs (rtx x)
986 int i, j, regno;
987 const RTX_CODE code = GET_CODE (x);
988 const char *fmt;
990 if (REG_P (x))
992 regno = REGNO (x);
993 if (HARD_REGISTER_NUM_P (regno))
994 bitmap_set_range (region_ref_regs, regno,
995 hard_regno_nregs[regno][GET_MODE (x)]);
996 else
997 bitmap_set_bit (region_ref_regs, REGNO (x));
998 return;
1000 fmt = GET_RTX_FORMAT (code);
1001 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1002 if (fmt[i] == 'e')
1003 setup_ref_regs (XEXP (x, i));
1004 else if (fmt[i] == 'E')
1006 for (j = 0; j < XVECLEN (x, i); j++)
1007 setup_ref_regs (XVECEXP (x, i, j));
1011 /* Initiate current register pressure related info at the start of
1012 basic block BB. */
1013 static void
1014 initiate_bb_reg_pressure_info (basic_block bb)
1016 unsigned int i ATTRIBUTE_UNUSED;
1017 rtx insn;
1019 if (current_nr_blocks > 1)
1020 FOR_BB_INSNS (bb, insn)
1021 if (NONDEBUG_INSN_P (insn))
1022 setup_ref_regs (PATTERN (insn));
1023 initiate_reg_pressure_info (df_get_live_in (bb));
1024 #ifdef EH_RETURN_DATA_REGNO
1025 if (bb_has_eh_pred (bb))
1026 for (i = 0; ; ++i)
1028 unsigned int regno = EH_RETURN_DATA_REGNO (i);
1030 if (regno == INVALID_REGNUM)
1031 break;
1032 if (! bitmap_bit_p (df_get_live_in (bb), regno))
1033 mark_regno_birth_or_death (curr_reg_live, curr_reg_pressure,
1034 regno, true);
1036 #endif
1039 /* Save current register pressure related info. */
1040 static void
1041 save_reg_pressure (void)
1043 int i;
1045 for (i = 0; i < ira_pressure_classes_num; i++)
1046 saved_reg_pressure[ira_pressure_classes[i]]
1047 = curr_reg_pressure[ira_pressure_classes[i]];
1048 bitmap_copy (saved_reg_live, curr_reg_live);
1051 /* Restore saved register pressure related info. */
1052 static void
1053 restore_reg_pressure (void)
1055 int i;
1057 for (i = 0; i < ira_pressure_classes_num; i++)
1058 curr_reg_pressure[ira_pressure_classes[i]]
1059 = saved_reg_pressure[ira_pressure_classes[i]];
1060 bitmap_copy (curr_reg_live, saved_reg_live);
1063 /* Return TRUE if the register is dying after its USE. */
1064 static bool
1065 dying_use_p (struct reg_use_data *use)
1067 struct reg_use_data *next;
1069 for (next = use->next_regno_use; next != use; next = next->next_regno_use)
1070 if (NONDEBUG_INSN_P (next->insn)
1071 && QUEUE_INDEX (next->insn) != QUEUE_SCHEDULED)
1072 return false;
1073 return true;
1076 /* Print info about the current register pressure and its excess for
1077 each pressure class. */
1078 static void
1079 print_curr_reg_pressure (void)
1081 int i;
1082 enum reg_class cl;
1084 fprintf (sched_dump, ";;\t");
1085 for (i = 0; i < ira_pressure_classes_num; i++)
1087 cl = ira_pressure_classes[i];
1088 gcc_assert (curr_reg_pressure[cl] >= 0);
1089 fprintf (sched_dump, " %s:%d(%d)", reg_class_names[cl],
1090 curr_reg_pressure[cl],
1091 curr_reg_pressure[cl] - ira_class_hard_regs_num[cl]);
1093 fprintf (sched_dump, "\n");
1096 /* Determine if INSN has a condition that is clobbered if a register
1097 in SET_REGS is modified. */
1098 static bool
1099 cond_clobbered_p (rtx insn, HARD_REG_SET set_regs)
1101 rtx pat = PATTERN (insn);
1102 gcc_assert (GET_CODE (pat) == COND_EXEC);
1103 if (TEST_HARD_REG_BIT (set_regs, REGNO (XEXP (COND_EXEC_TEST (pat), 0))))
1105 sd_iterator_def sd_it;
1106 dep_t dep;
1107 haifa_change_pattern (insn, ORIG_PAT (insn));
1108 FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
1109 DEP_STATUS (dep) &= ~DEP_CANCELLED;
1110 TODO_SPEC (insn) = HARD_DEP;
1111 if (sched_verbose >= 2)
1112 fprintf (sched_dump,
1113 ";;\t\tdequeue insn %s because of clobbered condition\n",
1114 (*current_sched_info->print_insn) (insn, 0));
1115 return true;
1118 return false;
1121 /* This function should be called after modifying the pattern of INSN,
1122 to update scheduler data structures as needed. */
1123 static void
1124 update_insn_after_change (rtx insn)
1126 sd_iterator_def sd_it;
1127 dep_t dep;
1129 dfa_clear_single_insn_cache (insn);
1131 sd_it = sd_iterator_start (insn,
1132 SD_LIST_FORW | SD_LIST_BACK | SD_LIST_RES_BACK);
1133 while (sd_iterator_cond (&sd_it, &dep))
1135 DEP_COST (dep) = UNKNOWN_DEP_COST;
1136 sd_iterator_next (&sd_it);
1139 /* Invalidate INSN_COST, so it'll be recalculated. */
1140 INSN_COST (insn) = -1;
1141 /* Invalidate INSN_TICK, so it'll be recalculated. */
1142 INSN_TICK (insn) = INVALID_TICK;
1145 DEF_VEC_P(dep_t);
1146 DEF_VEC_ALLOC_P(dep_t, heap);
1148 /* Two VECs, one to hold dependencies for which pattern replacements
1149 need to be applied or restored at the start of the next cycle, and
1150 another to hold an integer that is either one, to apply the
1151 corresponding replacement, or zero to restore it. */
1152 static VEC(dep_t, heap) *next_cycle_replace_deps;
1153 static VEC(int, heap) *next_cycle_apply;
1155 static void apply_replacement (dep_t, bool);
1156 static void restore_pattern (dep_t, bool);
1158 /* Look at the remaining dependencies for insn NEXT, and compute and return
1159 the TODO_SPEC value we should use for it. This is called after one of
1160 NEXT's dependencies has been resolved.
1161 We also perform pattern replacements for predication, and for broken
1162 replacement dependencies. The latter is only done if FOR_BACKTRACK is
1163 false. */
1165 static ds_t
1166 recompute_todo_spec (rtx next, bool for_backtrack)
1168 ds_t new_ds;
1169 sd_iterator_def sd_it;
1170 dep_t dep, modify_dep = NULL;
1171 int n_spec = 0;
1172 int n_control = 0;
1173 int n_replace = 0;
1174 bool first_p = true;
1176 if (sd_lists_empty_p (next, SD_LIST_BACK))
1177 /* NEXT has all its dependencies resolved. */
1178 return 0;
1180 if (!sd_lists_empty_p (next, SD_LIST_HARD_BACK))
1181 return HARD_DEP;
1183 /* Now we've got NEXT with speculative deps only.
1184 1. Look at the deps to see what we have to do.
1185 2. Check if we can do 'todo'. */
1186 new_ds = 0;
1188 FOR_EACH_DEP (next, SD_LIST_BACK, sd_it, dep)
1190 rtx pro = DEP_PRO (dep);
1191 ds_t ds = DEP_STATUS (dep) & SPECULATIVE;
1193 if (DEBUG_INSN_P (pro) && !DEBUG_INSN_P (next))
1194 continue;
1196 if (ds)
1198 n_spec++;
1199 if (first_p)
1201 first_p = false;
1203 new_ds = ds;
1205 else
1206 new_ds = ds_merge (new_ds, ds);
1208 else if (DEP_TYPE (dep) == REG_DEP_CONTROL)
1210 if (QUEUE_INDEX (pro) != QUEUE_SCHEDULED)
1212 n_control++;
1213 modify_dep = dep;
1215 DEP_STATUS (dep) &= ~DEP_CANCELLED;
1217 else if (DEP_REPLACE (dep) != NULL)
1219 if (QUEUE_INDEX (pro) != QUEUE_SCHEDULED)
1221 n_replace++;
1222 modify_dep = dep;
1224 DEP_STATUS (dep) &= ~DEP_CANCELLED;
1228 if (n_replace > 0 && n_control == 0 && n_spec == 0)
1230 if (!dbg_cnt (sched_breakdep))
1231 return HARD_DEP;
1232 FOR_EACH_DEP (next, SD_LIST_BACK, sd_it, dep)
1234 struct dep_replacement *desc = DEP_REPLACE (dep);
1235 if (desc != NULL)
1237 if (desc->insn == next && !for_backtrack)
1239 gcc_assert (n_replace == 1);
1240 apply_replacement (dep, true);
1242 DEP_STATUS (dep) |= DEP_CANCELLED;
1245 return 0;
1248 else if (n_control == 1 && n_replace == 0 && n_spec == 0)
1250 rtx pro, other, new_pat;
1251 rtx cond = NULL_RTX;
1252 bool success;
1253 rtx prev = NULL_RTX;
1254 int i;
1255 unsigned regno;
1257 if ((current_sched_info->flags & DO_PREDICATION) == 0
1258 || (ORIG_PAT (next) != NULL_RTX
1259 && PREDICATED_PAT (next) == NULL_RTX))
1260 return HARD_DEP;
1262 pro = DEP_PRO (modify_dep);
1263 other = real_insn_for_shadow (pro);
1264 if (other != NULL_RTX)
1265 pro = other;
1267 cond = sched_get_reverse_condition_uncached (pro);
1268 regno = REGNO (XEXP (cond, 0));
1270 /* Find the last scheduled insn that modifies the condition register.
1271 We can stop looking once we find the insn we depend on through the
1272 REG_DEP_CONTROL; if the condition register isn't modified after it,
1273 we know that it still has the right value. */
1274 if (QUEUE_INDEX (pro) == QUEUE_SCHEDULED)
1275 FOR_EACH_VEC_ELT_REVERSE (rtx, scheduled_insns, i, prev)
1277 HARD_REG_SET t;
1279 find_all_hard_reg_sets (prev, &t);
1280 if (TEST_HARD_REG_BIT (t, regno))
1281 return HARD_DEP;
1282 if (prev == pro)
1283 break;
1285 if (ORIG_PAT (next) == NULL_RTX)
1287 ORIG_PAT (next) = PATTERN (next);
1289 new_pat = gen_rtx_COND_EXEC (VOIDmode, cond, PATTERN (next));
1290 success = haifa_change_pattern (next, new_pat);
1291 if (!success)
1292 return HARD_DEP;
1293 PREDICATED_PAT (next) = new_pat;
1295 else if (PATTERN (next) != PREDICATED_PAT (next))
1297 bool success = haifa_change_pattern (next,
1298 PREDICATED_PAT (next));
1299 gcc_assert (success);
1301 DEP_STATUS (modify_dep) |= DEP_CANCELLED;
1302 return DEP_CONTROL;
1305 if (PREDICATED_PAT (next) != NULL_RTX)
1307 int tick = INSN_TICK (next);
1308 bool success = haifa_change_pattern (next,
1309 ORIG_PAT (next));
1310 INSN_TICK (next) = tick;
1311 gcc_assert (success);
1314 /* We can't handle the case where there are both speculative and control
1315 dependencies, so we return HARD_DEP in such a case. Also fail if
1316 we have speculative dependencies with not enough points, or more than
1317 one control dependency. */
1318 if ((n_spec > 0 && (n_control > 0 || n_replace > 0))
1319 || (n_spec > 0
1320 /* Too few points? */
1321 && ds_weak (new_ds) < spec_info->data_weakness_cutoff)
1322 || n_control > 0
1323 || n_replace > 0)
1324 return HARD_DEP;
1326 return new_ds;
1329 /* Pointer to the last instruction scheduled. */
1330 static rtx last_scheduled_insn;
1332 /* Pointer to the last nondebug instruction scheduled within the
1333 block, or the prev_head of the scheduling block. Used by
1334 rank_for_schedule, so that insns independent of the last scheduled
1335 insn will be preferred over dependent instructions. */
1336 static rtx last_nondebug_scheduled_insn;
1338 /* Pointer that iterates through the list of unscheduled insns if we
1339 have a dbg_cnt enabled. It always points at an insn prior to the
1340 first unscheduled one. */
1341 static rtx nonscheduled_insns_begin;
1343 /* Compute cost of executing INSN.
1344 This is the number of cycles between instruction issue and
1345 instruction results. */
1347 insn_cost (rtx insn)
1349 int cost;
1351 if (sel_sched_p ())
1353 if (recog_memoized (insn) < 0)
1354 return 0;
1356 cost = insn_default_latency (insn);
1357 if (cost < 0)
1358 cost = 0;
1360 return cost;
1363 cost = INSN_COST (insn);
1365 if (cost < 0)
1367 /* A USE insn, or something else we don't need to
1368 understand. We can't pass these directly to
1369 result_ready_cost or insn_default_latency because it will
1370 trigger a fatal error for unrecognizable insns. */
1371 if (recog_memoized (insn) < 0)
1373 INSN_COST (insn) = 0;
1374 return 0;
1376 else
1378 cost = insn_default_latency (insn);
1379 if (cost < 0)
1380 cost = 0;
1382 INSN_COST (insn) = cost;
1386 return cost;
1389 /* Compute cost of dependence LINK.
1390 This is the number of cycles between instruction issue and
1391 instruction results.
1392 ??? We also use this function to call recog_memoized on all insns. */
1394 dep_cost_1 (dep_t link, dw_t dw)
1396 rtx insn = DEP_PRO (link);
1397 rtx used = DEP_CON (link);
1398 int cost;
1400 if (DEP_COST (link) != UNKNOWN_DEP_COST)
1401 return DEP_COST (link);
1403 if (delay_htab)
1405 struct delay_pair *delay_entry;
1406 delay_entry
1407 = (struct delay_pair *)htab_find_with_hash (delay_htab_i2, used,
1408 htab_hash_pointer (used));
1409 if (delay_entry)
1411 if (delay_entry->i1 == insn)
1413 DEP_COST (link) = pair_delay (delay_entry);
1414 return DEP_COST (link);
1419 /* A USE insn should never require the value used to be computed.
1420 This allows the computation of a function's result and parameter
1421 values to overlap the return and call. We don't care about the
1422 dependence cost when only decreasing register pressure. */
1423 if (recog_memoized (used) < 0)
1425 cost = 0;
1426 recog_memoized (insn);
1428 else
1430 enum reg_note dep_type = DEP_TYPE (link);
1432 cost = insn_cost (insn);
1434 if (INSN_CODE (insn) >= 0)
1436 if (dep_type == REG_DEP_ANTI)
1437 cost = 0;
1438 else if (dep_type == REG_DEP_OUTPUT)
1440 cost = (insn_default_latency (insn)
1441 - insn_default_latency (used));
1442 if (cost <= 0)
1443 cost = 1;
1445 else if (bypass_p (insn))
1446 cost = insn_latency (insn, used);
1450 if (targetm.sched.adjust_cost_2)
1451 cost = targetm.sched.adjust_cost_2 (used, (int) dep_type, insn, cost,
1452 dw);
1453 else if (targetm.sched.adjust_cost != NULL)
1455 /* This variable is used for backward compatibility with the
1456 targets. */
1457 rtx dep_cost_rtx_link = alloc_INSN_LIST (NULL_RTX, NULL_RTX);
1459 /* Make it self-cycled, so that if some tries to walk over this
1460 incomplete list he/she will be caught in an endless loop. */
1461 XEXP (dep_cost_rtx_link, 1) = dep_cost_rtx_link;
1463 /* Targets use only REG_NOTE_KIND of the link. */
1464 PUT_REG_NOTE_KIND (dep_cost_rtx_link, DEP_TYPE (link));
1466 cost = targetm.sched.adjust_cost (used, dep_cost_rtx_link,
1467 insn, cost);
1469 free_INSN_LIST_node (dep_cost_rtx_link);
1472 if (cost < 0)
1473 cost = 0;
1476 DEP_COST (link) = cost;
1477 return cost;
1480 /* Compute cost of dependence LINK.
1481 This is the number of cycles between instruction issue and
1482 instruction results. */
1484 dep_cost (dep_t link)
1486 return dep_cost_1 (link, 0);
1489 /* Use this sel-sched.c friendly function in reorder2 instead of increasing
1490 INSN_PRIORITY explicitly. */
1491 void
1492 increase_insn_priority (rtx insn, int amount)
1494 if (!sel_sched_p ())
1496 /* We're dealing with haifa-sched.c INSN_PRIORITY. */
1497 if (INSN_PRIORITY_KNOWN (insn))
1498 INSN_PRIORITY (insn) += amount;
1500 else
1502 /* In sel-sched.c INSN_PRIORITY is not kept up to date.
1503 Use EXPR_PRIORITY instead. */
1504 sel_add_to_insn_priority (insn, amount);
1508 /* Return 'true' if DEP should be included in priority calculations. */
1509 static bool
1510 contributes_to_priority_p (dep_t dep)
1512 if (DEBUG_INSN_P (DEP_CON (dep))
1513 || DEBUG_INSN_P (DEP_PRO (dep)))
1514 return false;
1516 /* Critical path is meaningful in block boundaries only. */
1517 if (!current_sched_info->contributes_to_priority (DEP_CON (dep),
1518 DEP_PRO (dep)))
1519 return false;
1521 if (DEP_REPLACE (dep) != NULL)
1522 return false;
1524 /* If flag COUNT_SPEC_IN_CRITICAL_PATH is set,
1525 then speculative instructions will less likely be
1526 scheduled. That is because the priority of
1527 their producers will increase, and, thus, the
1528 producers will more likely be scheduled, thus,
1529 resolving the dependence. */
1530 if (sched_deps_info->generate_spec_deps
1531 && !(spec_info->flags & COUNT_SPEC_IN_CRITICAL_PATH)
1532 && (DEP_STATUS (dep) & SPECULATIVE))
1533 return false;
1535 return true;
1538 /* Compute the number of nondebug deps in list LIST for INSN. */
1540 static int
1541 dep_list_size (rtx insn, sd_list_types_def list)
1543 sd_iterator_def sd_it;
1544 dep_t dep;
1545 int dbgcount = 0, nodbgcount = 0;
1547 if (!MAY_HAVE_DEBUG_INSNS)
1548 return sd_lists_size (insn, list);
1550 FOR_EACH_DEP (insn, list, sd_it, dep)
1552 if (DEBUG_INSN_P (DEP_CON (dep)))
1553 dbgcount++;
1554 else if (!DEBUG_INSN_P (DEP_PRO (dep)))
1555 nodbgcount++;
1558 gcc_assert (dbgcount + nodbgcount == sd_lists_size (insn, list));
1560 return nodbgcount;
1563 /* Compute the priority number for INSN. */
1564 static int
1565 priority (rtx insn)
1567 if (! INSN_P (insn))
1568 return 0;
1570 /* We should not be interested in priority of an already scheduled insn. */
1571 gcc_assert (QUEUE_INDEX (insn) != QUEUE_SCHEDULED);
1573 if (!INSN_PRIORITY_KNOWN (insn))
1575 int this_priority = -1;
1577 if (dep_list_size (insn, SD_LIST_FORW) == 0)
1578 /* ??? We should set INSN_PRIORITY to insn_cost when and insn has
1579 some forward deps but all of them are ignored by
1580 contributes_to_priority hook. At the moment we set priority of
1581 such insn to 0. */
1582 this_priority = insn_cost (insn);
1583 else
1585 rtx prev_first, twin;
1586 basic_block rec;
1588 /* For recovery check instructions we calculate priority slightly
1589 different than that of normal instructions. Instead of walking
1590 through INSN_FORW_DEPS (check) list, we walk through
1591 INSN_FORW_DEPS list of each instruction in the corresponding
1592 recovery block. */
1594 /* Selective scheduling does not define RECOVERY_BLOCK macro. */
1595 rec = sel_sched_p () ? NULL : RECOVERY_BLOCK (insn);
1596 if (!rec || rec == EXIT_BLOCK_PTR)
1598 prev_first = PREV_INSN (insn);
1599 twin = insn;
1601 else
1603 prev_first = NEXT_INSN (BB_HEAD (rec));
1604 twin = PREV_INSN (BB_END (rec));
1609 sd_iterator_def sd_it;
1610 dep_t dep;
1612 FOR_EACH_DEP (twin, SD_LIST_FORW, sd_it, dep)
1614 rtx next;
1615 int next_priority;
1617 next = DEP_CON (dep);
1619 if (BLOCK_FOR_INSN (next) != rec)
1621 int cost;
1623 if (!contributes_to_priority_p (dep))
1624 continue;
1626 if (twin == insn)
1627 cost = dep_cost (dep);
1628 else
1630 struct _dep _dep1, *dep1 = &_dep1;
1632 init_dep (dep1, insn, next, REG_DEP_ANTI);
1634 cost = dep_cost (dep1);
1637 next_priority = cost + priority (next);
1639 if (next_priority > this_priority)
1640 this_priority = next_priority;
1644 twin = PREV_INSN (twin);
1646 while (twin != prev_first);
1649 if (this_priority < 0)
1651 gcc_assert (this_priority == -1);
1653 this_priority = insn_cost (insn);
1656 INSN_PRIORITY (insn) = this_priority;
1657 INSN_PRIORITY_STATUS (insn) = 1;
1660 return INSN_PRIORITY (insn);
1663 /* Macros and functions for keeping the priority queue sorted, and
1664 dealing with queuing and dequeuing of instructions. */
1666 #define SCHED_SORT(READY, N_READY) \
1667 do { if ((N_READY) == 2) \
1668 swap_sort (READY, N_READY); \
1669 else if ((N_READY) > 2) \
1670 qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \
1671 while (0)
1673 /* For each pressure class CL, set DEATH[CL] to the number of registers
1674 in that class that die in INSN. */
1676 static void
1677 calculate_reg_deaths (rtx insn, int *death)
1679 int i;
1680 struct reg_use_data *use;
1682 for (i = 0; i < ira_pressure_classes_num; i++)
1683 death[ira_pressure_classes[i]] = 0;
1684 for (use = INSN_REG_USE_LIST (insn); use != NULL; use = use->next_insn_use)
1685 if (dying_use_p (use))
1686 mark_regno_birth_or_death (0, death, use->regno, true);
1689 /* Setup info about the current register pressure impact of scheduling
1690 INSN at the current scheduling point. */
1691 static void
1692 setup_insn_reg_pressure_info (rtx insn)
1694 int i, change, before, after, hard_regno;
1695 int excess_cost_change;
1696 enum machine_mode mode;
1697 enum reg_class cl;
1698 struct reg_pressure_data *pressure_info;
1699 int *max_reg_pressure;
1700 static int death[N_REG_CLASSES];
1702 gcc_checking_assert (!DEBUG_INSN_P (insn));
1704 excess_cost_change = 0;
1705 calculate_reg_deaths (insn, death);
1706 pressure_info = INSN_REG_PRESSURE (insn);
1707 max_reg_pressure = INSN_MAX_REG_PRESSURE (insn);
1708 gcc_assert (pressure_info != NULL && max_reg_pressure != NULL);
1709 for (i = 0; i < ira_pressure_classes_num; i++)
1711 cl = ira_pressure_classes[i];
1712 gcc_assert (curr_reg_pressure[cl] >= 0);
1713 change = (int) pressure_info[i].set_increase - death[cl];
1714 before = MAX (0, max_reg_pressure[i] - ira_class_hard_regs_num[cl]);
1715 after = MAX (0, max_reg_pressure[i] + change
1716 - ira_class_hard_regs_num[cl]);
1717 hard_regno = ira_class_hard_regs[cl][0];
1718 gcc_assert (hard_regno >= 0);
1719 mode = reg_raw_mode[hard_regno];
1720 excess_cost_change += ((after - before)
1721 * (ira_memory_move_cost[mode][cl][0]
1722 + ira_memory_move_cost[mode][cl][1]));
1724 INSN_REG_PRESSURE_EXCESS_COST_CHANGE (insn) = excess_cost_change;
1727 /* This is the first page of code related to SCHED_PRESSURE_MODEL.
1728 It tries to make the scheduler take register pressure into account
1729 without introducing too many unnecessary stalls. It hooks into the
1730 main scheduling algorithm at several points:
1732 - Before scheduling starts, model_start_schedule constructs a
1733 "model schedule" for the current block. This model schedule is
1734 chosen solely to keep register pressure down. It does not take the
1735 target's pipeline or the original instruction order into account,
1736 except as a tie-breaker. It also doesn't work to a particular
1737 pressure limit.
1739 This model schedule gives us an idea of what pressure can be
1740 achieved for the block and gives us an example of a schedule that
1741 keeps to that pressure. It also makes the final schedule less
1742 dependent on the original instruction order. This is important
1743 because the original order can either be "wide" (many values live
1744 at once, such as in user-scheduled code) or "narrow" (few values
1745 live at once, such as after loop unrolling, where several
1746 iterations are executed sequentially).
1748 We do not apply this model schedule to the rtx stream. We simply
1749 record it in model_schedule. We also compute the maximum pressure,
1750 MP, that was seen during this schedule.
1752 - Instructions are added to the ready queue even if they require
1753 a stall. The length of the stall is instead computed as:
1755 MAX (INSN_TICK (INSN) - clock_var, 0)
1757 (= insn_delay). This allows rank_for_schedule to choose between
1758 introducing a deliberate stall or increasing pressure.
1760 - Before sorting the ready queue, model_set_excess_costs assigns
1761 a pressure-based cost to each ready instruction in the queue.
1762 This is the instruction's INSN_REG_PRESSURE_EXCESS_COST_CHANGE
1763 (ECC for short) and is effectively measured in cycles.
1765 - rank_for_schedule ranks instructions based on:
1767 ECC (insn) + insn_delay (insn)
1769 then as:
1771 insn_delay (insn)
1773 So, for example, an instruction X1 with an ECC of 1 that can issue
1774 now will win over an instruction X0 with an ECC of zero that would
1775 introduce a stall of one cycle. However, an instruction X2 with an
1776 ECC of 2 that can issue now will lose to both X0 and X1.
1778 - When an instruction is scheduled, model_recompute updates the model
1779 schedule with the new pressures (some of which might now exceed the
1780 original maximum pressure MP). model_update_limit_points then searches
1781 for the new point of maximum pressure, if not already known. */
1783 /* Used to separate high-verbosity debug information for SCHED_PRESSURE_MODEL
1784 from surrounding debug information. */
1785 #define MODEL_BAR \
1786 ";;\t\t+------------------------------------------------------\n"
1788 /* Information about the pressure on a particular register class at a
1789 particular point of the model schedule. */
1790 struct model_pressure_data {
1791 /* The pressure at this point of the model schedule, or -1 if the
1792 point is associated with an instruction that has already been
1793 scheduled. */
1794 int ref_pressure;
1796 /* The maximum pressure during or after this point of the model schedule. */
1797 int max_pressure;
1800 /* Per-instruction information that is used while building the model
1801 schedule. Here, "schedule" refers to the model schedule rather
1802 than the main schedule. */
1803 struct model_insn_info {
1804 /* The instruction itself. */
1805 rtx insn;
1807 /* If this instruction is in model_worklist, these fields link to the
1808 previous (higher-priority) and next (lower-priority) instructions
1809 in the list. */
1810 struct model_insn_info *prev;
1811 struct model_insn_info *next;
1813 /* While constructing the schedule, QUEUE_INDEX describes whether an
1814 instruction has already been added to the schedule (QUEUE_SCHEDULED),
1815 is in model_worklist (QUEUE_READY), or neither (QUEUE_NOWHERE).
1816 old_queue records the value that QUEUE_INDEX had before scheduling
1817 started, so that we can restore it once the schedule is complete. */
1818 int old_queue;
1820 /* The relative importance of an unscheduled instruction. Higher
1821 values indicate greater importance. */
1822 unsigned int model_priority;
1824 /* The length of the longest path of satisfied true dependencies
1825 that leads to this instruction. */
1826 unsigned int depth;
1828 /* The length of the longest path of dependencies of any kind
1829 that leads from this instruction. */
1830 unsigned int alap;
1832 /* The number of predecessor nodes that must still be scheduled. */
1833 int unscheduled_preds;
1836 /* Information about the pressure limit for a particular register class.
1837 This structure is used when applying a model schedule to the main
1838 schedule. */
1839 struct model_pressure_limit {
1840 /* The maximum register pressure seen in the original model schedule. */
1841 int orig_pressure;
1843 /* The maximum register pressure seen in the current model schedule
1844 (which excludes instructions that have already been scheduled). */
1845 int pressure;
1847 /* The point of the current model schedule at which PRESSURE is first
1848 reached. It is set to -1 if the value needs to be recomputed. */
1849 int point;
1852 /* Describes a particular way of measuring register pressure. */
1853 struct model_pressure_group {
1854 /* Index PCI describes the maximum pressure on ira_pressure_classes[PCI]. */
1855 struct model_pressure_limit limits[N_REG_CLASSES];
1857 /* Index (POINT * ira_num_pressure_classes + PCI) describes the pressure
1858 on register class ira_pressure_classes[PCI] at point POINT of the
1859 current model schedule. A POINT of model_num_insns describes the
1860 pressure at the end of the schedule. */
1861 struct model_pressure_data *model;
1864 /* Index POINT gives the instruction at point POINT of the model schedule.
1865 This array doesn't change during main scheduling. */
1866 static VEC (rtx, heap) *model_schedule;
1868 /* The list of instructions in the model worklist, sorted in order of
1869 decreasing priority. */
1870 static struct model_insn_info *model_worklist;
1872 /* Index I describes the instruction with INSN_LUID I. */
1873 static struct model_insn_info *model_insns;
1875 /* The number of instructions in the model schedule. */
1876 static int model_num_insns;
1878 /* The index of the first instruction in model_schedule that hasn't yet been
1879 added to the main schedule, or model_num_insns if all of them have. */
1880 static int model_curr_point;
1882 /* Describes the pressure before each instruction in the model schedule. */
1883 static struct model_pressure_group model_before_pressure;
1885 /* The first unused model_priority value (as used in model_insn_info). */
1886 static unsigned int model_next_priority;
1889 /* The model_pressure_data for ira_pressure_classes[PCI] in GROUP
1890 at point POINT of the model schedule. */
1891 #define MODEL_PRESSURE_DATA(GROUP, POINT, PCI) \
1892 (&(GROUP)->model[(POINT) * ira_pressure_classes_num + (PCI)])
1894 /* The maximum pressure on ira_pressure_classes[PCI] in GROUP at or
1895 after point POINT of the model schedule. */
1896 #define MODEL_MAX_PRESSURE(GROUP, POINT, PCI) \
1897 (MODEL_PRESSURE_DATA (GROUP, POINT, PCI)->max_pressure)
1899 /* The pressure on ira_pressure_classes[PCI] in GROUP at point POINT
1900 of the model schedule. */
1901 #define MODEL_REF_PRESSURE(GROUP, POINT, PCI) \
1902 (MODEL_PRESSURE_DATA (GROUP, POINT, PCI)->ref_pressure)
1904 /* Information about INSN that is used when creating the model schedule. */
1905 #define MODEL_INSN_INFO(INSN) \
1906 (&model_insns[INSN_LUID (INSN)])
1908 /* The instruction at point POINT of the model schedule. */
1909 #define MODEL_INSN(POINT) \
1910 (VEC_index (rtx, model_schedule, POINT))
1913 /* Return INSN's index in the model schedule, or model_num_insns if it
1914 doesn't belong to that schedule. */
1916 static int
1917 model_index (rtx insn)
1919 if (INSN_MODEL_INDEX (insn) == 0)
1920 return model_num_insns;
1921 return INSN_MODEL_INDEX (insn) - 1;
1924 /* Make sure that GROUP->limits is up-to-date for the current point
1925 of the model schedule. */
1927 static void
1928 model_update_limit_points_in_group (struct model_pressure_group *group)
1930 int pci, max_pressure, point;
1932 for (pci = 0; pci < ira_pressure_classes_num; pci++)
1934 /* We may have passed the final point at which the pressure in
1935 group->limits[pci].pressure was reached. Update the limit if so. */
1936 max_pressure = MODEL_MAX_PRESSURE (group, model_curr_point, pci);
1937 group->limits[pci].pressure = max_pressure;
1939 /* Find the point at which MAX_PRESSURE is first reached. We need
1940 to search in three cases:
1942 - We've already moved past the previous pressure point.
1943 In this case we search forward from model_curr_point.
1945 - We scheduled the previous point of maximum pressure ahead of
1946 its position in the model schedule, but doing so didn't bring
1947 the pressure point earlier. In this case we search forward
1948 from that previous pressure point.
1950 - Scheduling an instruction early caused the maximum pressure
1951 to decrease. In this case we will have set the pressure
1952 point to -1, and we search forward from model_curr_point. */
1953 point = MAX (group->limits[pci].point, model_curr_point);
1954 while (point < model_num_insns
1955 && MODEL_REF_PRESSURE (group, point, pci) < max_pressure)
1956 point++;
1957 group->limits[pci].point = point;
1959 gcc_assert (MODEL_REF_PRESSURE (group, point, pci) == max_pressure);
1960 gcc_assert (MODEL_MAX_PRESSURE (group, point, pci) == max_pressure);
1964 /* Make sure that all register-pressure limits are up-to-date for the
1965 current position in the model schedule. */
1967 static void
1968 model_update_limit_points (void)
1970 model_update_limit_points_in_group (&model_before_pressure);
1973 /* Return the model_index of the last unscheduled use in chain USE
1974 outside of USE's instruction. Return -1 if there are no other uses,
1975 or model_num_insns if the register is live at the end of the block. */
1977 static int
1978 model_last_use_except (struct reg_use_data *use)
1980 struct reg_use_data *next;
1981 int last, index;
1983 last = -1;
1984 for (next = use->next_regno_use; next != use; next = next->next_regno_use)
1985 if (NONDEBUG_INSN_P (next->insn)
1986 && QUEUE_INDEX (next->insn) != QUEUE_SCHEDULED)
1988 index = model_index (next->insn);
1989 if (index == model_num_insns)
1990 return model_num_insns;
1991 if (last < index)
1992 last = index;
1994 return last;
1997 /* An instruction with model_index POINT has just been scheduled, and it
1998 adds DELTA to the pressure on ira_pressure_classes[PCI] after POINT - 1.
1999 Update MODEL_REF_PRESSURE (GROUP, POINT, PCI) and
2000 MODEL_MAX_PRESSURE (GROUP, POINT, PCI) accordingly. */
2002 static void
2003 model_start_update_pressure (struct model_pressure_group *group,
2004 int point, int pci, int delta)
2006 int next_max_pressure;
2008 if (point == model_num_insns)
2010 /* The instruction wasn't part of the model schedule; it was moved
2011 from a different block. Update the pressure for the end of
2012 the model schedule. */
2013 MODEL_REF_PRESSURE (group, point, pci) += delta;
2014 MODEL_MAX_PRESSURE (group, point, pci) += delta;
2016 else
2018 /* Record that this instruction has been scheduled. Nothing now
2019 changes between POINT and POINT + 1, so get the maximum pressure
2020 from the latter. If the maximum pressure decreases, the new
2021 pressure point may be before POINT. */
2022 MODEL_REF_PRESSURE (group, point, pci) = -1;
2023 next_max_pressure = MODEL_MAX_PRESSURE (group, point + 1, pci);
2024 if (MODEL_MAX_PRESSURE (group, point, pci) > next_max_pressure)
2026 MODEL_MAX_PRESSURE (group, point, pci) = next_max_pressure;
2027 if (group->limits[pci].point == point)
2028 group->limits[pci].point = -1;
2033 /* Record that scheduling a later instruction has changed the pressure
2034 at point POINT of the model schedule by DELTA (which might be 0).
2035 Update GROUP accordingly. Return nonzero if these changes might
2036 trigger changes to previous points as well. */
2038 static int
2039 model_update_pressure (struct model_pressure_group *group,
2040 int point, int pci, int delta)
2042 int ref_pressure, max_pressure, next_max_pressure;
2044 /* If POINT hasn't yet been scheduled, update its pressure. */
2045 ref_pressure = MODEL_REF_PRESSURE (group, point, pci);
2046 if (ref_pressure >= 0 && delta != 0)
2048 ref_pressure += delta;
2049 MODEL_REF_PRESSURE (group, point, pci) = ref_pressure;
2051 /* Check whether the maximum pressure in the overall schedule
2052 has increased. (This means that the MODEL_MAX_PRESSURE of
2053 every point <= POINT will need to increae too; see below.) */
2054 if (group->limits[pci].pressure < ref_pressure)
2055 group->limits[pci].pressure = ref_pressure;
2057 /* If we are at maximum pressure, and the maximum pressure
2058 point was previously unknown or later than POINT,
2059 bring it forward. */
2060 if (group->limits[pci].pressure == ref_pressure
2061 && !IN_RANGE (group->limits[pci].point, 0, point))
2062 group->limits[pci].point = point;
2064 /* If POINT used to be the point of maximum pressure, but isn't
2065 any longer, we need to recalculate it using a forward walk. */
2066 if (group->limits[pci].pressure > ref_pressure
2067 && group->limits[pci].point == point)
2068 group->limits[pci].point = -1;
2071 /* Update the maximum pressure at POINT. Changes here might also
2072 affect the maximum pressure at POINT - 1. */
2073 next_max_pressure = MODEL_MAX_PRESSURE (group, point + 1, pci);
2074 max_pressure = MAX (ref_pressure, next_max_pressure);
2075 if (MODEL_MAX_PRESSURE (group, point, pci) != max_pressure)
2077 MODEL_MAX_PRESSURE (group, point, pci) = max_pressure;
2078 return 1;
2080 return 0;
2083 /* INSN has just been scheduled. Update the model schedule accordingly. */
2085 static void
2086 model_recompute (rtx insn)
2088 struct {
2089 int last_use;
2090 int regno;
2091 } uses[FIRST_PSEUDO_REGISTER + MAX_RECOG_OPERANDS];
2092 struct reg_use_data *use;
2093 struct reg_pressure_data *reg_pressure;
2094 int delta[N_REG_CLASSES];
2095 int pci, point, mix, new_last, cl, ref_pressure, queue;
2096 unsigned int i, num_uses, num_pending_births;
2097 bool print_p;
2099 /* The destinations of INSN were previously live from POINT onwards, but are
2100 now live from model_curr_point onwards. Set up DELTA accordingly. */
2101 point = model_index (insn);
2102 reg_pressure = INSN_REG_PRESSURE (insn);
2103 for (pci = 0; pci < ira_pressure_classes_num; pci++)
2105 cl = ira_pressure_classes[pci];
2106 delta[cl] = reg_pressure[pci].set_increase;
2109 /* Record which registers previously died at POINT, but which now die
2110 before POINT. Adjust DELTA so that it represents the effect of
2111 this change after POINT - 1. Set NUM_PENDING_BIRTHS to the number of
2112 registers that will be born in the range [model_curr_point, POINT). */
2113 num_uses = 0;
2114 num_pending_births = 0;
2115 for (use = INSN_REG_USE_LIST (insn); use != NULL; use = use->next_insn_use)
2117 new_last = model_last_use_except (use);
2118 if (new_last < point)
2120 gcc_assert (num_uses < ARRAY_SIZE (uses));
2121 uses[num_uses].last_use = new_last;
2122 uses[num_uses].regno = use->regno;
2123 /* This register is no longer live after POINT - 1. */
2124 mark_regno_birth_or_death (NULL, delta, use->regno, false);
2125 num_uses++;
2126 if (new_last >= 0)
2127 num_pending_births++;
2131 /* Update the MODEL_REF_PRESSURE and MODEL_MAX_PRESSURE for POINT.
2132 Also set each group pressure limit for POINT. */
2133 for (pci = 0; pci < ira_pressure_classes_num; pci++)
2135 cl = ira_pressure_classes[pci];
2136 model_start_update_pressure (&model_before_pressure,
2137 point, pci, delta[cl]);
2140 /* Walk the model schedule backwards, starting immediately before POINT. */
2141 print_p = false;
2142 if (point != model_curr_point)
2145 point--;
2146 insn = MODEL_INSN (point);
2147 queue = QUEUE_INDEX (insn);
2149 if (queue != QUEUE_SCHEDULED)
2151 /* DELTA describes the effect of the move on the register pressure
2152 after POINT. Make it describe the effect on the pressure
2153 before POINT. */
2154 i = 0;
2155 while (i < num_uses)
2157 if (uses[i].last_use == point)
2159 /* This register is now live again. */
2160 mark_regno_birth_or_death (NULL, delta,
2161 uses[i].regno, true);
2163 /* Remove this use from the array. */
2164 uses[i] = uses[num_uses - 1];
2165 num_uses--;
2166 num_pending_births--;
2168 else
2169 i++;
2172 if (sched_verbose >= 5)
2174 char buf[2048];
2176 if (!print_p)
2178 fprintf (sched_dump, MODEL_BAR);
2179 fprintf (sched_dump, ";;\t\t| New pressure for model"
2180 " schedule\n");
2181 fprintf (sched_dump, MODEL_BAR);
2182 print_p = true;
2185 print_pattern (buf, PATTERN (insn), 0);
2186 fprintf (sched_dump, ";;\t\t| %3d %4d %-30s ",
2187 point, INSN_UID (insn), buf);
2188 for (pci = 0; pci < ira_pressure_classes_num; pci++)
2190 cl = ira_pressure_classes[pci];
2191 ref_pressure = MODEL_REF_PRESSURE (&model_before_pressure,
2192 point, pci);
2193 fprintf (sched_dump, " %s:[%d->%d]",
2194 reg_class_names[ira_pressure_classes[pci]],
2195 ref_pressure, ref_pressure + delta[cl]);
2197 fprintf (sched_dump, "\n");
2201 /* Adjust the pressure at POINT. Set MIX to nonzero if POINT - 1
2202 might have changed as well. */
2203 mix = num_pending_births;
2204 for (pci = 0; pci < ira_pressure_classes_num; pci++)
2206 cl = ira_pressure_classes[pci];
2207 mix |= delta[cl];
2208 mix |= model_update_pressure (&model_before_pressure,
2209 point, pci, delta[cl]);
2212 while (mix && point > model_curr_point);
2214 if (print_p)
2215 fprintf (sched_dump, MODEL_BAR);
2218 /* After DEP, which was cancelled, has been resolved for insn NEXT,
2219 check whether the insn's pattern needs restoring. */
2220 static bool
2221 must_restore_pattern_p (rtx next, dep_t dep)
2223 if (QUEUE_INDEX (next) == QUEUE_SCHEDULED)
2224 return false;
2226 if (DEP_TYPE (dep) == REG_DEP_CONTROL)
2228 gcc_assert (ORIG_PAT (next) != NULL_RTX);
2229 gcc_assert (next == DEP_CON (dep));
2231 else
2233 struct dep_replacement *desc = DEP_REPLACE (dep);
2234 if (desc->insn != next)
2236 gcc_assert (*desc->loc == desc->orig);
2237 return false;
2240 return true;
2243 /* model_spill_cost (CL, P, P') returns the cost of increasing the
2244 pressure on CL from P to P'. We use this to calculate a "base ECC",
2245 baseECC (CL, X), for each pressure class CL and each instruction X.
2246 Supposing X changes the pressure on CL from P to P', and that the
2247 maximum pressure on CL in the current model schedule is MP', then:
2249 * if X occurs before or at the next point of maximum pressure in
2250 the model schedule and P' > MP', then:
2252 baseECC (CL, X) = model_spill_cost (CL, MP, P')
2254 The idea is that the pressure after scheduling a fixed set of
2255 instructions -- in this case, the set up to and including the
2256 next maximum pressure point -- is going to be the same regardless
2257 of the order; we simply want to keep the intermediate pressure
2258 under control. Thus X has a cost of zero unless scheduling it
2259 now would exceed MP'.
2261 If all increases in the set are by the same amount, no zero-cost
2262 instruction will ever cause the pressure to exceed MP'. However,
2263 if X is instead moved past an instruction X' with pressure in the
2264 range (MP' - (P' - P), MP'), the pressure at X' will increase
2265 beyond MP'. Since baseECC is very much a heuristic anyway,
2266 it doesn't seem worth the overhead of tracking cases like these.
2268 The cost of exceeding MP' is always based on the original maximum
2269 pressure MP. This is so that going 2 registers over the original
2270 limit has the same cost regardless of whether it comes from two
2271 separate +1 deltas or from a single +2 delta.
2273 * if X occurs after the next point of maximum pressure in the model
2274 schedule and P' > P, then:
2276 baseECC (CL, X) = model_spill_cost (CL, MP, MP' + (P' - P))
2278 That is, if we move X forward across a point of maximum pressure,
2279 and if X increases the pressure by P' - P, then we conservatively
2280 assume that scheduling X next would increase the maximum pressure
2281 by P' - P. Again, the cost of doing this is based on the original
2282 maximum pressure MP, for the same reason as above.
2284 * if P' < P, P > MP, and X occurs at or after the next point of
2285 maximum pressure, then:
2287 baseECC (CL, X) = -model_spill_cost (CL, MAX (MP, P'), P)
2289 That is, if we have already exceeded the original maximum pressure MP,
2290 and if X might reduce the maximum pressure again -- or at least push
2291 it further back, and thus allow more scheduling freedom -- it is given
2292 a negative cost to reflect the improvement.
2294 * otherwise,
2296 baseECC (CL, X) = 0
2298 In this case, X is not expected to affect the maximum pressure MP',
2299 so it has zero cost.
2301 We then create a combined value baseECC (X) that is the sum of
2302 baseECC (CL, X) for each pressure class CL.
2304 baseECC (X) could itself be used as the ECC value described above.
2305 However, this is often too conservative, in the sense that it
2306 tends to make high-priority instructions that increase pressure
2307 wait too long in cases where introducing a spill would be better.
2308 For this reason the final ECC is a priority-adjusted form of
2309 baseECC (X). Specifically, we calculate:
2311 P (X) = INSN_PRIORITY (X) - insn_delay (X) - baseECC (X)
2312 baseP = MAX { P (X) | baseECC (X) <= 0 }
2314 Then:
2316 ECC (X) = MAX (MIN (baseP - P (X), baseECC (X)), 0)
2318 Thus an instruction's effect on pressure is ignored if it has a high
2319 enough priority relative to the ones that don't increase pressure.
2320 Negative values of baseECC (X) do not increase the priority of X
2321 itself, but they do make it harder for other instructions to
2322 increase the pressure further.
2324 This pressure cost is deliberately timid. The intention has been
2325 to choose a heuristic that rarely interferes with the normal list
2326 scheduler in cases where that scheduler would produce good code.
2327 We simply want to curb some of its worst excesses. */
2329 /* Return the cost of increasing the pressure in class CL from FROM to TO.
2331 Here we use the very simplistic cost model that every register above
2332 ira_class_hard_regs_num[CL] has a spill cost of 1. We could use other
2333 measures instead, such as one based on MEMORY_MOVE_COST. However:
2335 (1) In order for an instruction to be scheduled, the higher cost
2336 would need to be justified in a single saving of that many stalls.
2337 This is overly pessimistic, because the benefit of spilling is
2338 often to avoid a sequence of several short stalls rather than
2339 a single long one.
2341 (2) The cost is still arbitrary. Because we are not allocating
2342 registers during scheduling, we have no way of knowing for
2343 sure how many memory accesses will be required by each spill,
2344 where the spills will be placed within the block, or even
2345 which block(s) will contain the spills.
2347 So a higher cost than 1 is often too conservative in practice,
2348 forcing blocks to contain unnecessary stalls instead of spill code.
2349 The simple cost below seems to be the best compromise. It reduces
2350 the interference with the normal list scheduler, which helps make
2351 it more suitable for a default-on option. */
2353 static int
2354 model_spill_cost (int cl, int from, int to)
2356 from = MAX (from, ira_class_hard_regs_num[cl]);
2357 return MAX (to, from) - from;
2360 /* Return baseECC (ira_pressure_classes[PCI], POINT), given that
2361 P = curr_reg_pressure[ira_pressure_classes[PCI]] and that
2362 P' = P + DELTA. */
2364 static int
2365 model_excess_group_cost (struct model_pressure_group *group,
2366 int point, int pci, int delta)
2368 int pressure, cl;
2370 cl = ira_pressure_classes[pci];
2371 if (delta < 0 && point >= group->limits[pci].point)
2373 pressure = MAX (group->limits[pci].orig_pressure,
2374 curr_reg_pressure[cl] + delta);
2375 return -model_spill_cost (cl, pressure, curr_reg_pressure[cl]);
2378 if (delta > 0)
2380 if (point > group->limits[pci].point)
2381 pressure = group->limits[pci].pressure + delta;
2382 else
2383 pressure = curr_reg_pressure[cl] + delta;
2385 if (pressure > group->limits[pci].pressure)
2386 return model_spill_cost (cl, group->limits[pci].orig_pressure,
2387 pressure);
2390 return 0;
2393 /* Return baseECC (MODEL_INSN (INSN)). Dump the costs to sched_dump
2394 if PRINT_P. */
2396 static int
2397 model_excess_cost (rtx insn, bool print_p)
2399 int point, pci, cl, cost, this_cost, delta;
2400 struct reg_pressure_data *insn_reg_pressure;
2401 int insn_death[N_REG_CLASSES];
2403 calculate_reg_deaths (insn, insn_death);
2404 point = model_index (insn);
2405 insn_reg_pressure = INSN_REG_PRESSURE (insn);
2406 cost = 0;
2408 if (print_p)
2409 fprintf (sched_dump, ";;\t\t| %3d %4d | %4d %+3d |", point,
2410 INSN_UID (insn), INSN_PRIORITY (insn), insn_delay (insn));
2412 /* Sum up the individual costs for each register class. */
2413 for (pci = 0; pci < ira_pressure_classes_num; pci++)
2415 cl = ira_pressure_classes[pci];
2416 delta = insn_reg_pressure[pci].set_increase - insn_death[cl];
2417 this_cost = model_excess_group_cost (&model_before_pressure,
2418 point, pci, delta);
2419 cost += this_cost;
2420 if (print_p)
2421 fprintf (sched_dump, " %s:[%d base cost %d]",
2422 reg_class_names[cl], delta, this_cost);
2425 if (print_p)
2426 fprintf (sched_dump, "\n");
2428 return cost;
2431 /* Dump the next points of maximum pressure for GROUP. */
2433 static void
2434 model_dump_pressure_points (struct model_pressure_group *group)
2436 int pci, cl;
2438 fprintf (sched_dump, ";;\t\t| pressure points");
2439 for (pci = 0; pci < ira_pressure_classes_num; pci++)
2441 cl = ira_pressure_classes[pci];
2442 fprintf (sched_dump, " %s:[%d->%d at ", reg_class_names[cl],
2443 curr_reg_pressure[cl], group->limits[pci].pressure);
2444 if (group->limits[pci].point < model_num_insns)
2445 fprintf (sched_dump, "%d:%d]", group->limits[pci].point,
2446 INSN_UID (MODEL_INSN (group->limits[pci].point)));
2447 else
2448 fprintf (sched_dump, "end]");
2450 fprintf (sched_dump, "\n");
2453 /* Set INSN_REG_PRESSURE_EXCESS_COST_CHANGE for INSNS[0...COUNT-1]. */
2455 static void
2456 model_set_excess_costs (rtx *insns, int count)
2458 int i, cost, priority_base, priority;
2459 bool print_p;
2461 /* Record the baseECC value for each instruction in the model schedule,
2462 except that negative costs are converted to zero ones now rather thatn
2463 later. Do not assign a cost to debug instructions, since they must
2464 not change code-generation decisions. Experiments suggest we also
2465 get better results by not assigning a cost to instructions from
2466 a different block.
2468 Set PRIORITY_BASE to baseP in the block comment above. This is the
2469 maximum priority of the "cheap" instructions, which should always
2470 include the next model instruction. */
2471 priority_base = 0;
2472 print_p = false;
2473 for (i = 0; i < count; i++)
2474 if (INSN_MODEL_INDEX (insns[i]))
2476 if (sched_verbose >= 6 && !print_p)
2478 fprintf (sched_dump, MODEL_BAR);
2479 fprintf (sched_dump, ";;\t\t| Pressure costs for ready queue\n");
2480 model_dump_pressure_points (&model_before_pressure);
2481 fprintf (sched_dump, MODEL_BAR);
2482 print_p = true;
2484 cost = model_excess_cost (insns[i], print_p);
2485 if (cost <= 0)
2487 priority = INSN_PRIORITY (insns[i]) - insn_delay (insns[i]) - cost;
2488 priority_base = MAX (priority_base, priority);
2489 cost = 0;
2491 INSN_REG_PRESSURE_EXCESS_COST_CHANGE (insns[i]) = cost;
2493 if (print_p)
2494 fprintf (sched_dump, MODEL_BAR);
2496 /* Use MAX (baseECC, 0) and baseP to calculcate ECC for each
2497 instruction. */
2498 for (i = 0; i < count; i++)
2500 cost = INSN_REG_PRESSURE_EXCESS_COST_CHANGE (insns[i]);
2501 priority = INSN_PRIORITY (insns[i]) - insn_delay (insns[i]);
2502 if (cost > 0 && priority > priority_base)
2504 cost += priority_base - priority;
2505 INSN_REG_PRESSURE_EXCESS_COST_CHANGE (insns[i]) = MAX (cost, 0);
2510 /* Returns a positive value if x is preferred; returns a negative value if
2511 y is preferred. Should never return 0, since that will make the sort
2512 unstable. */
2514 static int
2515 rank_for_schedule (const void *x, const void *y)
2517 rtx tmp = *(const rtx *) y;
2518 rtx tmp2 = *(const rtx *) x;
2519 int tmp_class, tmp2_class;
2520 int val, priority_val, info_val;
2522 if (MAY_HAVE_DEBUG_INSNS)
2524 /* Schedule debug insns as early as possible. */
2525 if (DEBUG_INSN_P (tmp) && !DEBUG_INSN_P (tmp2))
2526 return -1;
2527 else if (!DEBUG_INSN_P (tmp) && DEBUG_INSN_P (tmp2))
2528 return 1;
2529 else if (DEBUG_INSN_P (tmp) && DEBUG_INSN_P (tmp2))
2530 return INSN_LUID (tmp) - INSN_LUID (tmp2);
2533 /* The insn in a schedule group should be issued the first. */
2534 if (flag_sched_group_heuristic &&
2535 SCHED_GROUP_P (tmp) != SCHED_GROUP_P (tmp2))
2536 return SCHED_GROUP_P (tmp2) ? 1 : -1;
2538 /* Make sure that priority of TMP and TMP2 are initialized. */
2539 gcc_assert (INSN_PRIORITY_KNOWN (tmp) && INSN_PRIORITY_KNOWN (tmp2));
2541 if (sched_pressure != SCHED_PRESSURE_NONE)
2543 int diff;
2545 /* Prefer insn whose scheduling results in the smallest register
2546 pressure excess. */
2547 if ((diff = (INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp)
2548 + insn_delay (tmp)
2549 - INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp2)
2550 - insn_delay (tmp2))))
2551 return diff;
2554 if (sched_pressure != SCHED_PRESSURE_NONE
2555 && (INSN_TICK (tmp2) > clock_var || INSN_TICK (tmp) > clock_var))
2557 if (INSN_TICK (tmp) <= clock_var)
2558 return -1;
2559 else if (INSN_TICK (tmp2) <= clock_var)
2560 return 1;
2561 else
2562 return INSN_TICK (tmp) - INSN_TICK (tmp2);
2565 /* If we are doing backtracking in this schedule, prefer insns that
2566 have forward dependencies with negative cost against an insn that
2567 was already scheduled. */
2568 if (current_sched_info->flags & DO_BACKTRACKING)
2570 priority_val = FEEDS_BACKTRACK_INSN (tmp2) - FEEDS_BACKTRACK_INSN (tmp);
2571 if (priority_val)
2572 return priority_val;
2575 /* Prefer insn with higher priority. */
2576 priority_val = INSN_PRIORITY (tmp2) - INSN_PRIORITY (tmp);
2578 if (flag_sched_critical_path_heuristic && priority_val)
2579 return priority_val;
2581 /* Prefer speculative insn with greater dependencies weakness. */
2582 if (flag_sched_spec_insn_heuristic && spec_info)
2584 ds_t ds1, ds2;
2585 dw_t dw1, dw2;
2586 int dw;
2588 ds1 = TODO_SPEC (tmp) & SPECULATIVE;
2589 if (ds1)
2590 dw1 = ds_weak (ds1);
2591 else
2592 dw1 = NO_DEP_WEAK;
2594 ds2 = TODO_SPEC (tmp2) & SPECULATIVE;
2595 if (ds2)
2596 dw2 = ds_weak (ds2);
2597 else
2598 dw2 = NO_DEP_WEAK;
2600 dw = dw2 - dw1;
2601 if (dw > (NO_DEP_WEAK / 8) || dw < -(NO_DEP_WEAK / 8))
2602 return dw;
2605 info_val = (*current_sched_info->rank) (tmp, tmp2);
2606 if(flag_sched_rank_heuristic && info_val)
2607 return info_val;
2609 /* Compare insns based on their relation to the last scheduled
2610 non-debug insn. */
2611 if (flag_sched_last_insn_heuristic && last_nondebug_scheduled_insn)
2613 dep_t dep1;
2614 dep_t dep2;
2615 rtx last = last_nondebug_scheduled_insn;
2617 /* Classify the instructions into three classes:
2618 1) Data dependent on last schedule insn.
2619 2) Anti/Output dependent on last scheduled insn.
2620 3) Independent of last scheduled insn, or has latency of one.
2621 Choose the insn from the highest numbered class if different. */
2622 dep1 = sd_find_dep_between (last, tmp, true);
2624 if (dep1 == NULL || dep_cost (dep1) == 1)
2625 tmp_class = 3;
2626 else if (/* Data dependence. */
2627 DEP_TYPE (dep1) == REG_DEP_TRUE)
2628 tmp_class = 1;
2629 else
2630 tmp_class = 2;
2632 dep2 = sd_find_dep_between (last, tmp2, true);
2634 if (dep2 == NULL || dep_cost (dep2) == 1)
2635 tmp2_class = 3;
2636 else if (/* Data dependence. */
2637 DEP_TYPE (dep2) == REG_DEP_TRUE)
2638 tmp2_class = 1;
2639 else
2640 tmp2_class = 2;
2642 if ((val = tmp2_class - tmp_class))
2643 return val;
2646 /* Prefer instructions that occur earlier in the model schedule. */
2647 if (sched_pressure == SCHED_PRESSURE_MODEL)
2649 int diff;
2651 diff = model_index (tmp) - model_index (tmp2);
2652 if (diff != 0)
2653 return diff;
2656 /* Prefer the insn which has more later insns that depend on it.
2657 This gives the scheduler more freedom when scheduling later
2658 instructions at the expense of added register pressure. */
2660 val = (dep_list_size (tmp2, SD_LIST_FORW)
2661 - dep_list_size (tmp, SD_LIST_FORW));
2663 if (flag_sched_dep_count_heuristic && val != 0)
2664 return val;
2666 /* If insns are equally good, sort by INSN_LUID (original insn order),
2667 so that we make the sort stable. This minimizes instruction movement,
2668 thus minimizing sched's effect on debugging and cross-jumping. */
2669 return INSN_LUID (tmp) - INSN_LUID (tmp2);
2672 /* Resort the array A in which only element at index N may be out of order. */
2674 HAIFA_INLINE static void
2675 swap_sort (rtx *a, int n)
2677 rtx insn = a[n - 1];
2678 int i = n - 2;
2680 while (i >= 0 && rank_for_schedule (a + i, &insn) >= 0)
2682 a[i + 1] = a[i];
2683 i -= 1;
2685 a[i + 1] = insn;
2688 /* Add INSN to the insn queue so that it can be executed at least
2689 N_CYCLES after the currently executing insn. Preserve insns
2690 chain for debugging purposes. REASON will be printed in debugging
2691 output. */
2693 HAIFA_INLINE static void
2694 queue_insn (rtx insn, int n_cycles, const char *reason)
2696 int next_q = NEXT_Q_AFTER (q_ptr, n_cycles);
2697 rtx link = alloc_INSN_LIST (insn, insn_queue[next_q]);
2698 int new_tick;
2700 gcc_assert (n_cycles <= max_insn_queue_index);
2701 gcc_assert (!DEBUG_INSN_P (insn));
2703 insn_queue[next_q] = link;
2704 q_size += 1;
2706 if (sched_verbose >= 2)
2708 fprintf (sched_dump, ";;\t\tReady-->Q: insn %s: ",
2709 (*current_sched_info->print_insn) (insn, 0));
2711 fprintf (sched_dump, "queued for %d cycles (%s).\n", n_cycles, reason);
2714 QUEUE_INDEX (insn) = next_q;
2716 if (current_sched_info->flags & DO_BACKTRACKING)
2718 new_tick = clock_var + n_cycles;
2719 if (INSN_TICK (insn) == INVALID_TICK || INSN_TICK (insn) < new_tick)
2720 INSN_TICK (insn) = new_tick;
2722 if (INSN_EXACT_TICK (insn) != INVALID_TICK
2723 && INSN_EXACT_TICK (insn) < clock_var + n_cycles)
2725 must_backtrack = true;
2726 if (sched_verbose >= 2)
2727 fprintf (sched_dump, ";;\t\tcausing a backtrack.\n");
2732 /* Remove INSN from queue. */
2733 static void
2734 queue_remove (rtx insn)
2736 gcc_assert (QUEUE_INDEX (insn) >= 0);
2737 remove_free_INSN_LIST_elem (insn, &insn_queue[QUEUE_INDEX (insn)]);
2738 q_size--;
2739 QUEUE_INDEX (insn) = QUEUE_NOWHERE;
2742 /* Return a pointer to the bottom of the ready list, i.e. the insn
2743 with the lowest priority. */
2745 rtx *
2746 ready_lastpos (struct ready_list *ready)
2748 gcc_assert (ready->n_ready >= 1);
2749 return ready->vec + ready->first - ready->n_ready + 1;
2752 /* Add an element INSN to the ready list so that it ends up with the
2753 lowest/highest priority depending on FIRST_P. */
2755 HAIFA_INLINE static void
2756 ready_add (struct ready_list *ready, rtx insn, bool first_p)
2758 if (!first_p)
2760 if (ready->first == ready->n_ready)
2762 memmove (ready->vec + ready->veclen - ready->n_ready,
2763 ready_lastpos (ready),
2764 ready->n_ready * sizeof (rtx));
2765 ready->first = ready->veclen - 1;
2767 ready->vec[ready->first - ready->n_ready] = insn;
2769 else
2771 if (ready->first == ready->veclen - 1)
2773 if (ready->n_ready)
2774 /* ready_lastpos() fails when called with (ready->n_ready == 0). */
2775 memmove (ready->vec + ready->veclen - ready->n_ready - 1,
2776 ready_lastpos (ready),
2777 ready->n_ready * sizeof (rtx));
2778 ready->first = ready->veclen - 2;
2780 ready->vec[++(ready->first)] = insn;
2783 ready->n_ready++;
2784 if (DEBUG_INSN_P (insn))
2785 ready->n_debug++;
2787 gcc_assert (QUEUE_INDEX (insn) != QUEUE_READY);
2788 QUEUE_INDEX (insn) = QUEUE_READY;
2790 if (INSN_EXACT_TICK (insn) != INVALID_TICK
2791 && INSN_EXACT_TICK (insn) < clock_var)
2793 must_backtrack = true;
2797 /* Remove the element with the highest priority from the ready list and
2798 return it. */
2800 HAIFA_INLINE static rtx
2801 ready_remove_first (struct ready_list *ready)
2803 rtx t;
2805 gcc_assert (ready->n_ready);
2806 t = ready->vec[ready->first--];
2807 ready->n_ready--;
2808 if (DEBUG_INSN_P (t))
2809 ready->n_debug--;
2810 /* If the queue becomes empty, reset it. */
2811 if (ready->n_ready == 0)
2812 ready->first = ready->veclen - 1;
2814 gcc_assert (QUEUE_INDEX (t) == QUEUE_READY);
2815 QUEUE_INDEX (t) = QUEUE_NOWHERE;
2817 return t;
2820 /* The following code implements multi-pass scheduling for the first
2821 cycle. In other words, we will try to choose ready insn which
2822 permits to start maximum number of insns on the same cycle. */
2824 /* Return a pointer to the element INDEX from the ready. INDEX for
2825 insn with the highest priority is 0, and the lowest priority has
2826 N_READY - 1. */
2829 ready_element (struct ready_list *ready, int index)
2831 gcc_assert (ready->n_ready && index < ready->n_ready);
2833 return ready->vec[ready->first - index];
2836 /* Remove the element INDEX from the ready list and return it. INDEX
2837 for insn with the highest priority is 0, and the lowest priority
2838 has N_READY - 1. */
2840 HAIFA_INLINE static rtx
2841 ready_remove (struct ready_list *ready, int index)
2843 rtx t;
2844 int i;
2846 if (index == 0)
2847 return ready_remove_first (ready);
2848 gcc_assert (ready->n_ready && index < ready->n_ready);
2849 t = ready->vec[ready->first - index];
2850 ready->n_ready--;
2851 if (DEBUG_INSN_P (t))
2852 ready->n_debug--;
2853 for (i = index; i < ready->n_ready; i++)
2854 ready->vec[ready->first - i] = ready->vec[ready->first - i - 1];
2855 QUEUE_INDEX (t) = QUEUE_NOWHERE;
2856 return t;
2859 /* Remove INSN from the ready list. */
2860 static void
2861 ready_remove_insn (rtx insn)
2863 int i;
2865 for (i = 0; i < readyp->n_ready; i++)
2866 if (ready_element (readyp, i) == insn)
2868 ready_remove (readyp, i);
2869 return;
2871 gcc_unreachable ();
2874 /* Sort the ready list READY by ascending priority, using the SCHED_SORT
2875 macro. */
2877 void
2878 ready_sort (struct ready_list *ready)
2880 int i;
2881 rtx *first = ready_lastpos (ready);
2883 if (sched_pressure == SCHED_PRESSURE_WEIGHTED)
2885 for (i = 0; i < ready->n_ready; i++)
2886 if (!DEBUG_INSN_P (first[i]))
2887 setup_insn_reg_pressure_info (first[i]);
2889 if (sched_pressure == SCHED_PRESSURE_MODEL
2890 && model_curr_point < model_num_insns)
2891 model_set_excess_costs (first, ready->n_ready);
2892 SCHED_SORT (first, ready->n_ready);
2895 /* PREV is an insn that is ready to execute. Adjust its priority if that
2896 will help shorten or lengthen register lifetimes as appropriate. Also
2897 provide a hook for the target to tweak itself. */
2899 HAIFA_INLINE static void
2900 adjust_priority (rtx prev)
2902 /* ??? There used to be code here to try and estimate how an insn
2903 affected register lifetimes, but it did it by looking at REG_DEAD
2904 notes, which we removed in schedule_region. Nor did it try to
2905 take into account register pressure or anything useful like that.
2907 Revisit when we have a machine model to work with and not before. */
2909 if (targetm.sched.adjust_priority)
2910 INSN_PRIORITY (prev) =
2911 targetm.sched.adjust_priority (prev, INSN_PRIORITY (prev));
2914 /* Advance DFA state STATE on one cycle. */
2915 void
2916 advance_state (state_t state)
2918 if (targetm.sched.dfa_pre_advance_cycle)
2919 targetm.sched.dfa_pre_advance_cycle ();
2921 if (targetm.sched.dfa_pre_cycle_insn)
2922 state_transition (state,
2923 targetm.sched.dfa_pre_cycle_insn ());
2925 state_transition (state, NULL);
2927 if (targetm.sched.dfa_post_cycle_insn)
2928 state_transition (state,
2929 targetm.sched.dfa_post_cycle_insn ());
2931 if (targetm.sched.dfa_post_advance_cycle)
2932 targetm.sched.dfa_post_advance_cycle ();
2935 /* Advance time on one cycle. */
2936 HAIFA_INLINE static void
2937 advance_one_cycle (void)
2939 advance_state (curr_state);
2940 if (sched_verbose >= 6)
2941 fprintf (sched_dump, ";;\tAdvanced a state.\n");
2944 /* Update register pressure after scheduling INSN. */
2945 static void
2946 update_register_pressure (rtx insn)
2948 struct reg_use_data *use;
2949 struct reg_set_data *set;
2951 gcc_checking_assert (!DEBUG_INSN_P (insn));
2953 for (use = INSN_REG_USE_LIST (insn); use != NULL; use = use->next_insn_use)
2954 if (dying_use_p (use))
2955 mark_regno_birth_or_death (curr_reg_live, curr_reg_pressure,
2956 use->regno, false);
2957 for (set = INSN_REG_SET_LIST (insn); set != NULL; set = set->next_insn_set)
2958 mark_regno_birth_or_death (curr_reg_live, curr_reg_pressure,
2959 set->regno, true);
2962 /* Set up or update (if UPDATE_P) max register pressure (see its
2963 meaning in sched-int.h::_haifa_insn_data) for all current BB insns
2964 after insn AFTER. */
2965 static void
2966 setup_insn_max_reg_pressure (rtx after, bool update_p)
2968 int i, p;
2969 bool eq_p;
2970 rtx insn;
2971 static int max_reg_pressure[N_REG_CLASSES];
2973 save_reg_pressure ();
2974 for (i = 0; i < ira_pressure_classes_num; i++)
2975 max_reg_pressure[ira_pressure_classes[i]]
2976 = curr_reg_pressure[ira_pressure_classes[i]];
2977 for (insn = NEXT_INSN (after);
2978 insn != NULL_RTX && ! BARRIER_P (insn)
2979 && BLOCK_FOR_INSN (insn) == BLOCK_FOR_INSN (after);
2980 insn = NEXT_INSN (insn))
2981 if (NONDEBUG_INSN_P (insn))
2983 eq_p = true;
2984 for (i = 0; i < ira_pressure_classes_num; i++)
2986 p = max_reg_pressure[ira_pressure_classes[i]];
2987 if (INSN_MAX_REG_PRESSURE (insn)[i] != p)
2989 eq_p = false;
2990 INSN_MAX_REG_PRESSURE (insn)[i]
2991 = max_reg_pressure[ira_pressure_classes[i]];
2994 if (update_p && eq_p)
2995 break;
2996 update_register_pressure (insn);
2997 for (i = 0; i < ira_pressure_classes_num; i++)
2998 if (max_reg_pressure[ira_pressure_classes[i]]
2999 < curr_reg_pressure[ira_pressure_classes[i]])
3000 max_reg_pressure[ira_pressure_classes[i]]
3001 = curr_reg_pressure[ira_pressure_classes[i]];
3003 restore_reg_pressure ();
3006 /* Update the current register pressure after scheduling INSN. Update
3007 also max register pressure for unscheduled insns of the current
3008 BB. */
3009 static void
3010 update_reg_and_insn_max_reg_pressure (rtx insn)
3012 int i;
3013 int before[N_REG_CLASSES];
3015 for (i = 0; i < ira_pressure_classes_num; i++)
3016 before[i] = curr_reg_pressure[ira_pressure_classes[i]];
3017 update_register_pressure (insn);
3018 for (i = 0; i < ira_pressure_classes_num; i++)
3019 if (curr_reg_pressure[ira_pressure_classes[i]] != before[i])
3020 break;
3021 if (i < ira_pressure_classes_num)
3022 setup_insn_max_reg_pressure (insn, true);
3025 /* Set up register pressure at the beginning of basic block BB whose
3026 insns starting after insn AFTER. Set up also max register pressure
3027 for all insns of the basic block. */
3028 void
3029 sched_setup_bb_reg_pressure_info (basic_block bb, rtx after)
3031 gcc_assert (sched_pressure == SCHED_PRESSURE_WEIGHTED);
3032 initiate_bb_reg_pressure_info (bb);
3033 setup_insn_max_reg_pressure (after, false);
3036 /* If doing predication while scheduling, verify whether INSN, which
3037 has just been scheduled, clobbers the conditions of any
3038 instructions that must be predicated in order to break their
3039 dependencies. If so, remove them from the queues so that they will
3040 only be scheduled once their control dependency is resolved. */
3042 static void
3043 check_clobbered_conditions (rtx insn)
3045 HARD_REG_SET t;
3046 int i;
3048 if ((current_sched_info->flags & DO_PREDICATION) == 0)
3049 return;
3051 find_all_hard_reg_sets (insn, &t);
3053 restart:
3054 for (i = 0; i < ready.n_ready; i++)
3056 rtx x = ready_element (&ready, i);
3057 if (TODO_SPEC (x) == DEP_CONTROL && cond_clobbered_p (x, t))
3059 ready_remove_insn (x);
3060 goto restart;
3063 for (i = 0; i <= max_insn_queue_index; i++)
3065 rtx link;
3066 int q = NEXT_Q_AFTER (q_ptr, i);
3068 restart_queue:
3069 for (link = insn_queue[q]; link; link = XEXP (link, 1))
3071 rtx x = XEXP (link, 0);
3072 if (TODO_SPEC (x) == DEP_CONTROL && cond_clobbered_p (x, t))
3074 queue_remove (x);
3075 goto restart_queue;
3081 /* Return (in order):
3083 - positive if INSN adversely affects the pressure on one
3084 register class
3086 - negative if INSN reduces the pressure on one register class
3088 - 0 if INSN doesn't affect the pressure on any register class. */
3090 static int
3091 model_classify_pressure (struct model_insn_info *insn)
3093 struct reg_pressure_data *reg_pressure;
3094 int death[N_REG_CLASSES];
3095 int pci, cl, sum;
3097 calculate_reg_deaths (insn->insn, death);
3098 reg_pressure = INSN_REG_PRESSURE (insn->insn);
3099 sum = 0;
3100 for (pci = 0; pci < ira_pressure_classes_num; pci++)
3102 cl = ira_pressure_classes[pci];
3103 if (death[cl] < reg_pressure[pci].set_increase)
3104 return 1;
3105 sum += reg_pressure[pci].set_increase - death[cl];
3107 return sum;
3110 /* Return true if INSN1 should come before INSN2 in the model schedule. */
3112 static int
3113 model_order_p (struct model_insn_info *insn1, struct model_insn_info *insn2)
3115 unsigned int height1, height2;
3116 unsigned int priority1, priority2;
3118 /* Prefer instructions with a higher model priority. */
3119 if (insn1->model_priority != insn2->model_priority)
3120 return insn1->model_priority > insn2->model_priority;
3122 /* Combine the length of the longest path of satisfied true dependencies
3123 that leads to each instruction (depth) with the length of the longest
3124 path of any dependencies that leads from the instruction (alap).
3125 Prefer instructions with the greatest combined length. If the combined
3126 lengths are equal, prefer instructions with the greatest depth.
3128 The idea is that, if we have a set S of "equal" instructions that each
3129 have ALAP value X, and we pick one such instruction I, any true-dependent
3130 successors of I that have ALAP value X - 1 should be preferred over S.
3131 This encourages the schedule to be "narrow" rather than "wide".
3132 However, if I is a low-priority instruction that we decided to
3133 schedule because of its model_classify_pressure, and if there
3134 is a set of higher-priority instructions T, the aforementioned
3135 successors of I should not have the edge over T. */
3136 height1 = insn1->depth + insn1->alap;
3137 height2 = insn2->depth + insn2->alap;
3138 if (height1 != height2)
3139 return height1 > height2;
3140 if (insn1->depth != insn2->depth)
3141 return insn1->depth > insn2->depth;
3143 /* We have no real preference between INSN1 an INSN2 as far as attempts
3144 to reduce pressure go. Prefer instructions with higher priorities. */
3145 priority1 = INSN_PRIORITY (insn1->insn);
3146 priority2 = INSN_PRIORITY (insn2->insn);
3147 if (priority1 != priority2)
3148 return priority1 > priority2;
3150 /* Use the original rtl sequence as a tie-breaker. */
3151 return insn1 < insn2;
3154 /* Add INSN to the model worklist immediately after PREV. Add it to the
3155 beginning of the list if PREV is null. */
3157 static void
3158 model_add_to_worklist_at (struct model_insn_info *insn,
3159 struct model_insn_info *prev)
3161 gcc_assert (QUEUE_INDEX (insn->insn) == QUEUE_NOWHERE);
3162 QUEUE_INDEX (insn->insn) = QUEUE_READY;
3164 insn->prev = prev;
3165 if (prev)
3167 insn->next = prev->next;
3168 prev->next = insn;
3170 else
3172 insn->next = model_worklist;
3173 model_worklist = insn;
3175 if (insn->next)
3176 insn->next->prev = insn;
3179 /* Remove INSN from the model worklist. */
3181 static void
3182 model_remove_from_worklist (struct model_insn_info *insn)
3184 gcc_assert (QUEUE_INDEX (insn->insn) == QUEUE_READY);
3185 QUEUE_INDEX (insn->insn) = QUEUE_NOWHERE;
3187 if (insn->prev)
3188 insn->prev->next = insn->next;
3189 else
3190 model_worklist = insn->next;
3191 if (insn->next)
3192 insn->next->prev = insn->prev;
3195 /* Add INSN to the model worklist. Start looking for a suitable position
3196 between neighbors PREV and NEXT, testing at most MAX_SCHED_READY_INSNS
3197 insns either side. A null PREV indicates the beginning of the list and
3198 a null NEXT indicates the end. */
3200 static void
3201 model_add_to_worklist (struct model_insn_info *insn,
3202 struct model_insn_info *prev,
3203 struct model_insn_info *next)
3205 int count;
3207 count = MAX_SCHED_READY_INSNS;
3208 if (count > 0 && prev && model_order_p (insn, prev))
3211 count--;
3212 prev = prev->prev;
3214 while (count > 0 && prev && model_order_p (insn, prev));
3215 else
3216 while (count > 0 && next && model_order_p (next, insn))
3218 count--;
3219 prev = next;
3220 next = next->next;
3222 model_add_to_worklist_at (insn, prev);
3225 /* INSN may now have a higher priority (in the model_order_p sense)
3226 than before. Move it up the worklist if necessary. */
3228 static void
3229 model_promote_insn (struct model_insn_info *insn)
3231 struct model_insn_info *prev;
3232 int count;
3234 prev = insn->prev;
3235 count = MAX_SCHED_READY_INSNS;
3236 while (count > 0 && prev && model_order_p (insn, prev))
3238 count--;
3239 prev = prev->prev;
3241 if (prev != insn->prev)
3243 model_remove_from_worklist (insn);
3244 model_add_to_worklist_at (insn, prev);
3248 /* Add INSN to the end of the model schedule. */
3250 static void
3251 model_add_to_schedule (rtx insn)
3253 unsigned int point;
3255 gcc_assert (QUEUE_INDEX (insn) == QUEUE_NOWHERE);
3256 QUEUE_INDEX (insn) = QUEUE_SCHEDULED;
3258 point = VEC_length (rtx, model_schedule);
3259 VEC_quick_push (rtx, model_schedule, insn);
3260 INSN_MODEL_INDEX (insn) = point + 1;
3263 /* Analyze the instructions that are to be scheduled, setting up
3264 MODEL_INSN_INFO (...) and model_num_insns accordingly. Add ready
3265 instructions to model_worklist. */
3267 static void
3268 model_analyze_insns (void)
3270 rtx start, end, iter;
3271 sd_iterator_def sd_it;
3272 dep_t dep;
3273 struct model_insn_info *insn, *con;
3275 model_num_insns = 0;
3276 start = PREV_INSN (current_sched_info->next_tail);
3277 end = current_sched_info->prev_head;
3278 for (iter = start; iter != end; iter = PREV_INSN (iter))
3279 if (NONDEBUG_INSN_P (iter))
3281 insn = MODEL_INSN_INFO (iter);
3282 insn->insn = iter;
3283 FOR_EACH_DEP (iter, SD_LIST_FORW, sd_it, dep)
3285 con = MODEL_INSN_INFO (DEP_CON (dep));
3286 if (con->insn && insn->alap < con->alap + 1)
3287 insn->alap = con->alap + 1;
3290 insn->old_queue = QUEUE_INDEX (iter);
3291 QUEUE_INDEX (iter) = QUEUE_NOWHERE;
3293 insn->unscheduled_preds = dep_list_size (iter, SD_LIST_HARD_BACK);
3294 if (insn->unscheduled_preds == 0)
3295 model_add_to_worklist (insn, NULL, model_worklist);
3297 model_num_insns++;
3301 /* The global state describes the register pressure at the start of the
3302 model schedule. Initialize GROUP accordingly. */
3304 static void
3305 model_init_pressure_group (struct model_pressure_group *group)
3307 int pci, cl;
3309 for (pci = 0; pci < ira_pressure_classes_num; pci++)
3311 cl = ira_pressure_classes[pci];
3312 group->limits[pci].pressure = curr_reg_pressure[cl];
3313 group->limits[pci].point = 0;
3315 /* Use index model_num_insns to record the state after the last
3316 instruction in the model schedule. */
3317 group->model = XNEWVEC (struct model_pressure_data,
3318 (model_num_insns + 1) * ira_pressure_classes_num);
3321 /* Record that MODEL_REF_PRESSURE (GROUP, POINT, PCI) is PRESSURE.
3322 Update the maximum pressure for the whole schedule. */
3324 static void
3325 model_record_pressure (struct model_pressure_group *group,
3326 int point, int pci, int pressure)
3328 MODEL_REF_PRESSURE (group, point, pci) = pressure;
3329 if (group->limits[pci].pressure < pressure)
3331 group->limits[pci].pressure = pressure;
3332 group->limits[pci].point = point;
3336 /* INSN has just been added to the end of the model schedule. Record its
3337 register-pressure information. */
3339 static void
3340 model_record_pressures (struct model_insn_info *insn)
3342 struct reg_pressure_data *reg_pressure;
3343 int point, pci, cl, delta;
3344 int death[N_REG_CLASSES];
3346 point = model_index (insn->insn);
3347 if (sched_verbose >= 2)
3349 char buf[2048];
3351 if (point == 0)
3353 fprintf (sched_dump, "\n;;\tModel schedule:\n;;\n");
3354 fprintf (sched_dump, ";;\t| idx insn | mpri hght dpth prio |\n");
3356 print_pattern (buf, PATTERN (insn->insn), 0);
3357 fprintf (sched_dump, ";;\t| %3d %4d | %4d %4d %4d %4d | %-30s ",
3358 point, INSN_UID (insn->insn), insn->model_priority,
3359 insn->depth + insn->alap, insn->depth,
3360 INSN_PRIORITY (insn->insn), buf);
3362 calculate_reg_deaths (insn->insn, death);
3363 reg_pressure = INSN_REG_PRESSURE (insn->insn);
3364 for (pci = 0; pci < ira_pressure_classes_num; pci++)
3366 cl = ira_pressure_classes[pci];
3367 delta = reg_pressure[pci].set_increase - death[cl];
3368 if (sched_verbose >= 2)
3369 fprintf (sched_dump, " %s:[%d,%+d]", reg_class_names[cl],
3370 curr_reg_pressure[cl], delta);
3371 model_record_pressure (&model_before_pressure, point, pci,
3372 curr_reg_pressure[cl]);
3374 if (sched_verbose >= 2)
3375 fprintf (sched_dump, "\n");
3378 /* All instructions have been added to the model schedule. Record the
3379 final register pressure in GROUP and set up all MODEL_MAX_PRESSUREs. */
3381 static void
3382 model_record_final_pressures (struct model_pressure_group *group)
3384 int point, pci, max_pressure, ref_pressure, cl;
3386 for (pci = 0; pci < ira_pressure_classes_num; pci++)
3388 /* Record the final pressure for this class. */
3389 cl = ira_pressure_classes[pci];
3390 point = model_num_insns;
3391 ref_pressure = curr_reg_pressure[cl];
3392 model_record_pressure (group, point, pci, ref_pressure);
3394 /* Record the original maximum pressure. */
3395 group->limits[pci].orig_pressure = group->limits[pci].pressure;
3397 /* Update the MODEL_MAX_PRESSURE for every point of the schedule. */
3398 max_pressure = ref_pressure;
3399 MODEL_MAX_PRESSURE (group, point, pci) = max_pressure;
3400 while (point > 0)
3402 point--;
3403 ref_pressure = MODEL_REF_PRESSURE (group, point, pci);
3404 max_pressure = MAX (max_pressure, ref_pressure);
3405 MODEL_MAX_PRESSURE (group, point, pci) = max_pressure;
3410 /* Update all successors of INSN, given that INSN has just been scheduled. */
3412 static void
3413 model_add_successors_to_worklist (struct model_insn_info *insn)
3415 sd_iterator_def sd_it;
3416 struct model_insn_info *con;
3417 dep_t dep;
3419 FOR_EACH_DEP (insn->insn, SD_LIST_FORW, sd_it, dep)
3421 con = MODEL_INSN_INFO (DEP_CON (dep));
3422 /* Ignore debug instructions, and instructions from other blocks. */
3423 if (con->insn)
3425 con->unscheduled_preds--;
3427 /* Update the depth field of each true-dependent successor.
3428 Increasing the depth gives them a higher priority than
3429 before. */
3430 if (DEP_TYPE (dep) == REG_DEP_TRUE && con->depth < insn->depth + 1)
3432 con->depth = insn->depth + 1;
3433 if (QUEUE_INDEX (con->insn) == QUEUE_READY)
3434 model_promote_insn (con);
3437 /* If this is a true dependency, or if there are no remaining
3438 dependencies for CON (meaning that CON only had non-true
3439 dependencies), make sure that CON is on the worklist.
3440 We don't bother otherwise because it would tend to fill the
3441 worklist with a lot of low-priority instructions that are not
3442 yet ready to issue. */
3443 if ((con->depth > 0 || con->unscheduled_preds == 0)
3444 && QUEUE_INDEX (con->insn) == QUEUE_NOWHERE)
3445 model_add_to_worklist (con, insn, insn->next);
3450 /* Give INSN a higher priority than any current instruction, then give
3451 unscheduled predecessors of INSN a higher priority still. If any of
3452 those predecessors are not on the model worklist, do the same for its
3453 predecessors, and so on. */
3455 static void
3456 model_promote_predecessors (struct model_insn_info *insn)
3458 struct model_insn_info *pro, *first;
3459 sd_iterator_def sd_it;
3460 dep_t dep;
3462 if (sched_verbose >= 7)
3463 fprintf (sched_dump, ";;\t+--- priority of %d = %d, priority of",
3464 INSN_UID (insn->insn), model_next_priority);
3465 insn->model_priority = model_next_priority++;
3466 model_remove_from_worklist (insn);
3467 model_add_to_worklist_at (insn, NULL);
3469 first = NULL;
3470 for (;;)
3472 FOR_EACH_DEP (insn->insn, SD_LIST_HARD_BACK, sd_it, dep)
3474 pro = MODEL_INSN_INFO (DEP_PRO (dep));
3475 /* The first test is to ignore debug instructions, and instructions
3476 from other blocks. */
3477 if (pro->insn
3478 && pro->model_priority != model_next_priority
3479 && QUEUE_INDEX (pro->insn) != QUEUE_SCHEDULED)
3481 pro->model_priority = model_next_priority;
3482 if (sched_verbose >= 7)
3483 fprintf (sched_dump, " %d", INSN_UID (pro->insn));
3484 if (QUEUE_INDEX (pro->insn) == QUEUE_READY)
3486 /* PRO is already in the worklist, but it now has
3487 a higher priority than before. Move it at the
3488 appropriate place. */
3489 model_remove_from_worklist (pro);
3490 model_add_to_worklist (pro, NULL, model_worklist);
3492 else
3494 /* PRO isn't in the worklist. Recursively process
3495 its predecessors until we find one that is. */
3496 pro->next = first;
3497 first = pro;
3501 if (!first)
3502 break;
3503 insn = first;
3504 first = insn->next;
3506 if (sched_verbose >= 7)
3507 fprintf (sched_dump, " = %d\n", model_next_priority);
3508 model_next_priority++;
3511 /* Pick one instruction from model_worklist and process it. */
3513 static void
3514 model_choose_insn (void)
3516 struct model_insn_info *insn, *fallback;
3517 int count;
3519 if (sched_verbose >= 7)
3521 fprintf (sched_dump, ";;\t+--- worklist:\n");
3522 insn = model_worklist;
3523 count = MAX_SCHED_READY_INSNS;
3524 while (count > 0 && insn)
3526 fprintf (sched_dump, ";;\t+--- %d [%d, %d, %d, %d]\n",
3527 INSN_UID (insn->insn), insn->model_priority,
3528 insn->depth + insn->alap, insn->depth,
3529 INSN_PRIORITY (insn->insn));
3530 count--;
3531 insn = insn->next;
3535 /* Look for a ready instruction whose model_classify_priority is zero
3536 or negative, picking the highest-priority one. Adding such an
3537 instruction to the schedule now should do no harm, and may actually
3538 do some good.
3540 Failing that, see whether there is an instruction with the highest
3541 extant model_priority that is not yet ready, but which would reduce
3542 pressure if it became ready. This is designed to catch cases like:
3544 (set (mem (reg R1)) (reg R2))
3546 where the instruction is the last remaining use of R1 and where the
3547 value of R2 is not yet available (or vice versa). The death of R1
3548 means that this instruction already reduces pressure. It is of
3549 course possible that the computation of R2 involves other registers
3550 that are hard to kill, but such cases are rare enough for this
3551 heuristic to be a win in general.
3553 Failing that, just pick the highest-priority instruction in the
3554 worklist. */
3555 count = MAX_SCHED_READY_INSNS;
3556 insn = model_worklist;
3557 fallback = 0;
3558 for (;;)
3560 if (count == 0 || !insn)
3562 insn = fallback ? fallback : model_worklist;
3563 break;
3565 if (insn->unscheduled_preds)
3567 if (model_worklist->model_priority == insn->model_priority
3568 && !fallback
3569 && model_classify_pressure (insn) < 0)
3570 fallback = insn;
3572 else
3574 if (model_classify_pressure (insn) <= 0)
3575 break;
3577 count--;
3578 insn = insn->next;
3581 if (sched_verbose >= 7 && insn != model_worklist)
3583 if (insn->unscheduled_preds)
3584 fprintf (sched_dump, ";;\t+--- promoting insn %d, with dependencies\n",
3585 INSN_UID (insn->insn));
3586 else
3587 fprintf (sched_dump, ";;\t+--- promoting insn %d, which is ready\n",
3588 INSN_UID (insn->insn));
3590 if (insn->unscheduled_preds)
3591 /* INSN isn't yet ready to issue. Give all its predecessors the
3592 highest priority. */
3593 model_promote_predecessors (insn);
3594 else
3596 /* INSN is ready. Add it to the end of model_schedule and
3597 process its successors. */
3598 model_add_successors_to_worklist (insn);
3599 model_remove_from_worklist (insn);
3600 model_add_to_schedule (insn->insn);
3601 model_record_pressures (insn);
3602 update_register_pressure (insn->insn);
3606 /* Restore all QUEUE_INDEXs to the values that they had before
3607 model_start_schedule was called. */
3609 static void
3610 model_reset_queue_indices (void)
3612 unsigned int i;
3613 rtx insn;
3615 FOR_EACH_VEC_ELT (rtx, model_schedule, i, insn)
3616 QUEUE_INDEX (insn) = MODEL_INSN_INFO (insn)->old_queue;
3619 /* We have calculated the model schedule and spill costs. Print a summary
3620 to sched_dump. */
3622 static void
3623 model_dump_pressure_summary (void)
3625 int pci, cl;
3627 fprintf (sched_dump, ";; Pressure summary:");
3628 for (pci = 0; pci < ira_pressure_classes_num; pci++)
3630 cl = ira_pressure_classes[pci];
3631 fprintf (sched_dump, " %s:%d", reg_class_names[cl],
3632 model_before_pressure.limits[pci].pressure);
3634 fprintf (sched_dump, "\n\n");
3637 /* Initialize the SCHED_PRESSURE_MODEL information for the current
3638 scheduling region. */
3640 static void
3641 model_start_schedule (void)
3643 basic_block bb;
3645 model_next_priority = 1;
3646 model_schedule = VEC_alloc (rtx, heap, sched_max_luid);
3647 model_insns = XCNEWVEC (struct model_insn_info, sched_max_luid);
3649 bb = BLOCK_FOR_INSN (NEXT_INSN (current_sched_info->prev_head));
3650 initiate_reg_pressure_info (df_get_live_in (bb));
3652 model_analyze_insns ();
3653 model_init_pressure_group (&model_before_pressure);
3654 while (model_worklist)
3655 model_choose_insn ();
3656 gcc_assert (model_num_insns == (int) VEC_length (rtx, model_schedule));
3657 if (sched_verbose >= 2)
3658 fprintf (sched_dump, "\n");
3660 model_record_final_pressures (&model_before_pressure);
3661 model_reset_queue_indices ();
3663 XDELETEVEC (model_insns);
3665 model_curr_point = 0;
3666 initiate_reg_pressure_info (df_get_live_in (bb));
3667 if (sched_verbose >= 1)
3668 model_dump_pressure_summary ();
3671 /* Free the information associated with GROUP. */
3673 static void
3674 model_finalize_pressure_group (struct model_pressure_group *group)
3676 XDELETEVEC (group->model);
3679 /* Free the information created by model_start_schedule. */
3681 static void
3682 model_end_schedule (void)
3684 model_finalize_pressure_group (&model_before_pressure);
3685 VEC_free (rtx, heap, model_schedule);
3688 /* A structure that holds local state for the loop in schedule_block. */
3689 struct sched_block_state
3691 /* True if no real insns have been scheduled in the current cycle. */
3692 bool first_cycle_insn_p;
3693 /* True if a shadow insn has been scheduled in the current cycle, which
3694 means that no more normal insns can be issued. */
3695 bool shadows_only_p;
3696 /* True if we're winding down a modulo schedule, which means that we only
3697 issue insns with INSN_EXACT_TICK set. */
3698 bool modulo_epilogue;
3699 /* Initialized with the machine's issue rate every cycle, and updated
3700 by calls to the variable_issue hook. */
3701 int can_issue_more;
3704 /* INSN is the "currently executing insn". Launch each insn which was
3705 waiting on INSN. READY is the ready list which contains the insns
3706 that are ready to fire. CLOCK is the current cycle. The function
3707 returns necessary cycle advance after issuing the insn (it is not
3708 zero for insns in a schedule group). */
3710 static int
3711 schedule_insn (rtx insn)
3713 sd_iterator_def sd_it;
3714 dep_t dep;
3715 int i;
3716 int advance = 0;
3718 if (sched_verbose >= 1)
3720 struct reg_pressure_data *pressure_info;
3721 char buf[2048];
3723 print_insn (buf, insn, 0);
3724 buf[40] = 0;
3725 fprintf (sched_dump, ";;\t%3i--> %-40s:", clock_var, buf);
3727 if (recog_memoized (insn) < 0)
3728 fprintf (sched_dump, "nothing");
3729 else
3730 print_reservation (sched_dump, insn);
3731 pressure_info = INSN_REG_PRESSURE (insn);
3732 if (pressure_info != NULL)
3734 fputc (':', sched_dump);
3735 for (i = 0; i < ira_pressure_classes_num; i++)
3736 fprintf (sched_dump, "%s%+d(%d)",
3737 reg_class_names[ira_pressure_classes[i]],
3738 pressure_info[i].set_increase, pressure_info[i].change);
3740 if (sched_pressure == SCHED_PRESSURE_MODEL
3741 && model_curr_point < model_num_insns
3742 && model_index (insn) == model_curr_point)
3743 fprintf (sched_dump, ":model %d", model_curr_point);
3744 fputc ('\n', sched_dump);
3747 if (sched_pressure == SCHED_PRESSURE_WEIGHTED && !DEBUG_INSN_P (insn))
3748 update_reg_and_insn_max_reg_pressure (insn);
3750 /* Scheduling instruction should have all its dependencies resolved and
3751 should have been removed from the ready list. */
3752 gcc_assert (sd_lists_empty_p (insn, SD_LIST_HARD_BACK));
3754 /* Reset debug insns invalidated by moving this insn. */
3755 if (MAY_HAVE_DEBUG_INSNS && !DEBUG_INSN_P (insn))
3756 for (sd_it = sd_iterator_start (insn, SD_LIST_BACK);
3757 sd_iterator_cond (&sd_it, &dep);)
3759 rtx dbg = DEP_PRO (dep);
3760 struct reg_use_data *use, *next;
3762 if (DEP_STATUS (dep) & DEP_CANCELLED)
3764 sd_iterator_next (&sd_it);
3765 continue;
3768 gcc_assert (DEBUG_INSN_P (dbg));
3770 if (sched_verbose >= 6)
3771 fprintf (sched_dump, ";;\t\tresetting: debug insn %d\n",
3772 INSN_UID (dbg));
3774 /* ??? Rather than resetting the debug insn, we might be able
3775 to emit a debug temp before the just-scheduled insn, but
3776 this would involve checking that the expression at the
3777 point of the debug insn is equivalent to the expression
3778 before the just-scheduled insn. They might not be: the
3779 expression in the debug insn may depend on other insns not
3780 yet scheduled that set MEMs, REGs or even other debug
3781 insns. It's not clear that attempting to preserve debug
3782 information in these cases is worth the effort, given how
3783 uncommon these resets are and the likelihood that the debug
3784 temps introduced won't survive the schedule change. */
3785 INSN_VAR_LOCATION_LOC (dbg) = gen_rtx_UNKNOWN_VAR_LOC ();
3786 df_insn_rescan (dbg);
3788 /* Unknown location doesn't use any registers. */
3789 for (use = INSN_REG_USE_LIST (dbg); use != NULL; use = next)
3791 struct reg_use_data *prev = use;
3793 /* Remove use from the cyclic next_regno_use chain first. */
3794 while (prev->next_regno_use != use)
3795 prev = prev->next_regno_use;
3796 prev->next_regno_use = use->next_regno_use;
3797 next = use->next_insn_use;
3798 free (use);
3800 INSN_REG_USE_LIST (dbg) = NULL;
3802 /* We delete rather than resolve these deps, otherwise we
3803 crash in sched_free_deps(), because forward deps are
3804 expected to be released before backward deps. */
3805 sd_delete_dep (sd_it);
3808 gcc_assert (QUEUE_INDEX (insn) == QUEUE_NOWHERE);
3809 QUEUE_INDEX (insn) = QUEUE_SCHEDULED;
3811 if (sched_pressure == SCHED_PRESSURE_MODEL
3812 && model_curr_point < model_num_insns
3813 && NONDEBUG_INSN_P (insn))
3815 if (model_index (insn) == model_curr_point)
3817 model_curr_point++;
3818 while (model_curr_point < model_num_insns
3819 && (QUEUE_INDEX (MODEL_INSN (model_curr_point))
3820 == QUEUE_SCHEDULED));
3821 else
3822 model_recompute (insn);
3823 model_update_limit_points ();
3824 update_register_pressure (insn);
3825 if (sched_verbose >= 2)
3826 print_curr_reg_pressure ();
3829 gcc_assert (INSN_TICK (insn) >= MIN_TICK);
3830 if (INSN_TICK (insn) > clock_var)
3831 /* INSN has been prematurely moved from the queue to the ready list.
3832 This is possible only if following flag is set. */
3833 gcc_assert (flag_sched_stalled_insns);
3835 /* ??? Probably, if INSN is scheduled prematurely, we should leave
3836 INSN_TICK untouched. This is a machine-dependent issue, actually. */
3837 INSN_TICK (insn) = clock_var;
3839 check_clobbered_conditions (insn);
3841 /* Update dependent instructions. First, see if by scheduling this insn
3842 now we broke a dependence in a way that requires us to change another
3843 insn. */
3844 for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
3845 sd_iterator_cond (&sd_it, &dep); sd_iterator_next (&sd_it))
3847 struct dep_replacement *desc = DEP_REPLACE (dep);
3848 rtx pro = DEP_PRO (dep);
3849 if (QUEUE_INDEX (pro) != QUEUE_SCHEDULED
3850 && desc != NULL && desc->insn == pro)
3851 apply_replacement (dep, false);
3854 /* Go through and resolve forward dependencies. */
3855 for (sd_it = sd_iterator_start (insn, SD_LIST_FORW);
3856 sd_iterator_cond (&sd_it, &dep);)
3858 rtx next = DEP_CON (dep);
3859 bool cancelled = (DEP_STATUS (dep) & DEP_CANCELLED) != 0;
3861 /* Resolve the dependence between INSN and NEXT.
3862 sd_resolve_dep () moves current dep to another list thus
3863 advancing the iterator. */
3864 sd_resolve_dep (sd_it);
3866 if (cancelled)
3868 if (must_restore_pattern_p (next, dep))
3869 restore_pattern (dep, false);
3870 continue;
3873 /* Don't bother trying to mark next as ready if insn is a debug
3874 insn. If insn is the last hard dependency, it will have
3875 already been discounted. */
3876 if (DEBUG_INSN_P (insn) && !DEBUG_INSN_P (next))
3877 continue;
3879 if (!IS_SPECULATION_BRANCHY_CHECK_P (insn))
3881 int effective_cost;
3883 effective_cost = try_ready (next);
3885 if (effective_cost >= 0
3886 && SCHED_GROUP_P (next)
3887 && advance < effective_cost)
3888 advance = effective_cost;
3890 else
3891 /* Check always has only one forward dependence (to the first insn in
3892 the recovery block), therefore, this will be executed only once. */
3894 gcc_assert (sd_lists_empty_p (insn, SD_LIST_FORW));
3895 fix_recovery_deps (RECOVERY_BLOCK (insn));
3899 /* Annotate the instruction with issue information -- TImode
3900 indicates that the instruction is expected not to be able
3901 to issue on the same cycle as the previous insn. A machine
3902 may use this information to decide how the instruction should
3903 be aligned. */
3904 if (issue_rate > 1
3905 && GET_CODE (PATTERN (insn)) != USE
3906 && GET_CODE (PATTERN (insn)) != CLOBBER
3907 && !DEBUG_INSN_P (insn))
3909 if (reload_completed)
3910 PUT_MODE (insn, clock_var > last_clock_var ? TImode : VOIDmode);
3911 last_clock_var = clock_var;
3914 return advance;
3917 /* Functions for handling of notes. */
3919 /* Add note list that ends on FROM_END to the end of TO_ENDP. */
3920 void
3921 concat_note_lists (rtx from_end, rtx *to_endp)
3923 rtx from_start;
3925 /* It's easy when have nothing to concat. */
3926 if (from_end == NULL)
3927 return;
3929 /* It's also easy when destination is empty. */
3930 if (*to_endp == NULL)
3932 *to_endp = from_end;
3933 return;
3936 from_start = from_end;
3937 while (PREV_INSN (from_start) != NULL)
3938 from_start = PREV_INSN (from_start);
3940 PREV_INSN (from_start) = *to_endp;
3941 NEXT_INSN (*to_endp) = from_start;
3942 *to_endp = from_end;
3945 /* Delete notes between HEAD and TAIL and put them in the chain
3946 of notes ended by NOTE_LIST. */
3947 void
3948 remove_notes (rtx head, rtx tail)
3950 rtx next_tail, insn, next;
3952 note_list = 0;
3953 if (head == tail && !INSN_P (head))
3954 return;
3956 next_tail = NEXT_INSN (tail);
3957 for (insn = head; insn != next_tail; insn = next)
3959 next = NEXT_INSN (insn);
3960 if (!NOTE_P (insn))
3961 continue;
3963 switch (NOTE_KIND (insn))
3965 case NOTE_INSN_BASIC_BLOCK:
3966 continue;
3968 case NOTE_INSN_EPILOGUE_BEG:
3969 if (insn != tail)
3971 remove_insn (insn);
3972 add_reg_note (next, REG_SAVE_NOTE,
3973 GEN_INT (NOTE_INSN_EPILOGUE_BEG));
3974 break;
3976 /* FALLTHRU */
3978 default:
3979 remove_insn (insn);
3981 /* Add the note to list that ends at NOTE_LIST. */
3982 PREV_INSN (insn) = note_list;
3983 NEXT_INSN (insn) = NULL_RTX;
3984 if (note_list)
3985 NEXT_INSN (note_list) = insn;
3986 note_list = insn;
3987 break;
3990 gcc_assert ((sel_sched_p () || insn != tail) && insn != head);
3994 /* A structure to record enough data to allow us to backtrack the scheduler to
3995 a previous state. */
3996 struct haifa_saved_data
3998 /* Next entry on the list. */
3999 struct haifa_saved_data *next;
4001 /* Backtracking is associated with scheduling insns that have delay slots.
4002 DELAY_PAIR points to the structure that contains the insns involved, and
4003 the number of cycles between them. */
4004 struct delay_pair *delay_pair;
4006 /* Data used by the frontend (e.g. sched-ebb or sched-rgn). */
4007 void *fe_saved_data;
4008 /* Data used by the backend. */
4009 void *be_saved_data;
4011 /* Copies of global state. */
4012 int clock_var, last_clock_var;
4013 struct ready_list ready;
4014 state_t curr_state;
4016 rtx last_scheduled_insn;
4017 rtx last_nondebug_scheduled_insn;
4018 int cycle_issued_insns;
4020 /* Copies of state used in the inner loop of schedule_block. */
4021 struct sched_block_state sched_block;
4023 /* We don't need to save q_ptr, as its value is arbitrary and we can set it
4024 to 0 when restoring. */
4025 int q_size;
4026 rtx *insn_queue;
4028 /* Describe pattern replacements that occurred since this backtrack point
4029 was queued. */
4030 VEC (dep_t, heap) *replacement_deps;
4031 VEC (int, heap) *replace_apply;
4033 /* A copy of the next-cycle replacement vectors at the time of the backtrack
4034 point. */
4035 VEC (dep_t, heap) *next_cycle_deps;
4036 VEC (int, heap) *next_cycle_apply;
4039 /* A record, in reverse order, of all scheduled insns which have delay slots
4040 and may require backtracking. */
4041 static struct haifa_saved_data *backtrack_queue;
4043 /* For every dependency of INSN, set the FEEDS_BACKTRACK_INSN bit according
4044 to SET_P. */
4045 static void
4046 mark_backtrack_feeds (rtx insn, int set_p)
4048 sd_iterator_def sd_it;
4049 dep_t dep;
4050 FOR_EACH_DEP (insn, SD_LIST_HARD_BACK, sd_it, dep)
4052 FEEDS_BACKTRACK_INSN (DEP_PRO (dep)) = set_p;
4056 /* Save the current scheduler state so that we can backtrack to it
4057 later if necessary. PAIR gives the insns that make it necessary to
4058 save this point. SCHED_BLOCK is the local state of schedule_block
4059 that need to be saved. */
4060 static void
4061 save_backtrack_point (struct delay_pair *pair,
4062 struct sched_block_state sched_block)
4064 int i;
4065 struct haifa_saved_data *save = XNEW (struct haifa_saved_data);
4067 save->curr_state = xmalloc (dfa_state_size);
4068 memcpy (save->curr_state, curr_state, dfa_state_size);
4070 save->ready.first = ready.first;
4071 save->ready.n_ready = ready.n_ready;
4072 save->ready.n_debug = ready.n_debug;
4073 save->ready.veclen = ready.veclen;
4074 save->ready.vec = XNEWVEC (rtx, ready.veclen);
4075 memcpy (save->ready.vec, ready.vec, ready.veclen * sizeof (rtx));
4077 save->insn_queue = XNEWVEC (rtx, max_insn_queue_index + 1);
4078 save->q_size = q_size;
4079 for (i = 0; i <= max_insn_queue_index; i++)
4081 int q = NEXT_Q_AFTER (q_ptr, i);
4082 save->insn_queue[i] = copy_INSN_LIST (insn_queue[q]);
4085 save->clock_var = clock_var;
4086 save->last_clock_var = last_clock_var;
4087 save->cycle_issued_insns = cycle_issued_insns;
4088 save->last_scheduled_insn = last_scheduled_insn;
4089 save->last_nondebug_scheduled_insn = last_nondebug_scheduled_insn;
4091 save->sched_block = sched_block;
4093 save->replacement_deps = NULL;
4094 save->replace_apply = NULL;
4095 save->next_cycle_deps = VEC_copy (dep_t, heap, next_cycle_replace_deps);
4096 save->next_cycle_apply = VEC_copy (int, heap, next_cycle_apply);
4098 if (current_sched_info->save_state)
4099 save->fe_saved_data = (*current_sched_info->save_state) ();
4101 if (targetm.sched.alloc_sched_context)
4103 save->be_saved_data = targetm.sched.alloc_sched_context ();
4104 targetm.sched.init_sched_context (save->be_saved_data, false);
4106 else
4107 save->be_saved_data = NULL;
4109 save->delay_pair = pair;
4111 save->next = backtrack_queue;
4112 backtrack_queue = save;
4114 while (pair)
4116 mark_backtrack_feeds (pair->i2, 1);
4117 INSN_TICK (pair->i2) = INVALID_TICK;
4118 INSN_EXACT_TICK (pair->i2) = clock_var + pair_delay (pair);
4119 SHADOW_P (pair->i2) = pair->stages == 0;
4120 pair = pair->next_same_i1;
4124 /* Walk the ready list and all queues. If any insns have unresolved backwards
4125 dependencies, these must be cancelled deps, broken by predication. Set or
4126 clear (depending on SET) the DEP_CANCELLED bit in DEP_STATUS. */
4128 static void
4129 toggle_cancelled_flags (bool set)
4131 int i;
4132 sd_iterator_def sd_it;
4133 dep_t dep;
4135 if (ready.n_ready > 0)
4137 rtx *first = ready_lastpos (&ready);
4138 for (i = 0; i < ready.n_ready; i++)
4139 FOR_EACH_DEP (first[i], SD_LIST_BACK, sd_it, dep)
4140 if (!DEBUG_INSN_P (DEP_PRO (dep)))
4142 if (set)
4143 DEP_STATUS (dep) |= DEP_CANCELLED;
4144 else
4145 DEP_STATUS (dep) &= ~DEP_CANCELLED;
4148 for (i = 0; i <= max_insn_queue_index; i++)
4150 int q = NEXT_Q_AFTER (q_ptr, i);
4151 rtx link;
4152 for (link = insn_queue[q]; link; link = XEXP (link, 1))
4154 rtx insn = XEXP (link, 0);
4155 FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
4156 if (!DEBUG_INSN_P (DEP_PRO (dep)))
4158 if (set)
4159 DEP_STATUS (dep) |= DEP_CANCELLED;
4160 else
4161 DEP_STATUS (dep) &= ~DEP_CANCELLED;
4167 /* Undo the replacements that have occurred after backtrack point SAVE
4168 was placed. */
4169 static void
4170 undo_replacements_for_backtrack (struct haifa_saved_data *save)
4172 while (!VEC_empty (dep_t, save->replacement_deps))
4174 dep_t dep = VEC_pop (dep_t, save->replacement_deps);
4175 int apply_p = VEC_pop (int, save->replace_apply);
4177 if (apply_p)
4178 restore_pattern (dep, true);
4179 else
4180 apply_replacement (dep, true);
4182 VEC_free (dep_t, heap, save->replacement_deps);
4183 VEC_free (int, heap, save->replace_apply);
4186 /* Pop entries from the SCHEDULED_INSNS vector up to and including INSN.
4187 Restore their dependencies to an unresolved state, and mark them as
4188 queued nowhere. */
4190 static void
4191 unschedule_insns_until (rtx insn)
4193 VEC (rtx, heap) *recompute_vec;
4195 recompute_vec = VEC_alloc (rtx, heap, 0);
4197 /* Make two passes over the insns to be unscheduled. First, we clear out
4198 dependencies and other trivial bookkeeping. */
4199 for (;;)
4201 rtx last;
4202 sd_iterator_def sd_it;
4203 dep_t dep;
4205 last = VEC_pop (rtx, scheduled_insns);
4207 /* This will be changed by restore_backtrack_point if the insn is in
4208 any queue. */
4209 QUEUE_INDEX (last) = QUEUE_NOWHERE;
4210 if (last != insn)
4211 INSN_TICK (last) = INVALID_TICK;
4213 if (modulo_ii > 0 && INSN_UID (last) < modulo_iter0_max_uid)
4214 modulo_insns_scheduled--;
4216 for (sd_it = sd_iterator_start (last, SD_LIST_RES_FORW);
4217 sd_iterator_cond (&sd_it, &dep);)
4219 rtx con = DEP_CON (dep);
4220 sd_unresolve_dep (sd_it);
4221 if (!MUST_RECOMPUTE_SPEC_P (con))
4223 MUST_RECOMPUTE_SPEC_P (con) = 1;
4224 VEC_safe_push (rtx, heap, recompute_vec, con);
4228 if (last == insn)
4229 break;
4232 /* A second pass, to update ready and speculation status for insns
4233 depending on the unscheduled ones. The first pass must have
4234 popped the scheduled_insns vector up to the point where we
4235 restart scheduling, as recompute_todo_spec requires it to be
4236 up-to-date. */
4237 while (!VEC_empty (rtx, recompute_vec))
4239 rtx con;
4241 con = VEC_pop (rtx, recompute_vec);
4242 MUST_RECOMPUTE_SPEC_P (con) = 0;
4243 if (!sd_lists_empty_p (con, SD_LIST_HARD_BACK))
4245 TODO_SPEC (con) = HARD_DEP;
4246 INSN_TICK (con) = INVALID_TICK;
4247 if (PREDICATED_PAT (con) != NULL_RTX)
4248 haifa_change_pattern (con, ORIG_PAT (con));
4250 else if (QUEUE_INDEX (con) != QUEUE_SCHEDULED)
4251 TODO_SPEC (con) = recompute_todo_spec (con, true);
4253 VEC_free (rtx, heap, recompute_vec);
4256 /* Restore scheduler state from the topmost entry on the backtracking queue.
4257 PSCHED_BLOCK_P points to the local data of schedule_block that we must
4258 overwrite with the saved data.
4259 The caller must already have called unschedule_insns_until. */
4261 static void
4262 restore_last_backtrack_point (struct sched_block_state *psched_block)
4264 rtx link;
4265 int i;
4266 struct haifa_saved_data *save = backtrack_queue;
4268 backtrack_queue = save->next;
4270 if (current_sched_info->restore_state)
4271 (*current_sched_info->restore_state) (save->fe_saved_data);
4273 if (targetm.sched.alloc_sched_context)
4275 targetm.sched.set_sched_context (save->be_saved_data);
4276 targetm.sched.free_sched_context (save->be_saved_data);
4279 /* Do this first since it clobbers INSN_TICK of the involved
4280 instructions. */
4281 undo_replacements_for_backtrack (save);
4283 /* Clear the QUEUE_INDEX of everything in the ready list or one
4284 of the queues. */
4285 if (ready.n_ready > 0)
4287 rtx *first = ready_lastpos (&ready);
4288 for (i = 0; i < ready.n_ready; i++)
4290 rtx insn = first[i];
4291 QUEUE_INDEX (insn) = QUEUE_NOWHERE;
4292 INSN_TICK (insn) = INVALID_TICK;
4295 for (i = 0; i <= max_insn_queue_index; i++)
4297 int q = NEXT_Q_AFTER (q_ptr, i);
4299 for (link = insn_queue[q]; link; link = XEXP (link, 1))
4301 rtx x = XEXP (link, 0);
4302 QUEUE_INDEX (x) = QUEUE_NOWHERE;
4303 INSN_TICK (x) = INVALID_TICK;
4305 free_INSN_LIST_list (&insn_queue[q]);
4308 free (ready.vec);
4309 ready = save->ready;
4311 if (ready.n_ready > 0)
4313 rtx *first = ready_lastpos (&ready);
4314 for (i = 0; i < ready.n_ready; i++)
4316 rtx insn = first[i];
4317 QUEUE_INDEX (insn) = QUEUE_READY;
4318 TODO_SPEC (insn) = recompute_todo_spec (insn, true);
4319 INSN_TICK (insn) = save->clock_var;
4323 q_ptr = 0;
4324 q_size = save->q_size;
4325 for (i = 0; i <= max_insn_queue_index; i++)
4327 int q = NEXT_Q_AFTER (q_ptr, i);
4329 insn_queue[q] = save->insn_queue[q];
4331 for (link = insn_queue[q]; link; link = XEXP (link, 1))
4333 rtx x = XEXP (link, 0);
4334 QUEUE_INDEX (x) = i;
4335 TODO_SPEC (x) = recompute_todo_spec (x, true);
4336 INSN_TICK (x) = save->clock_var + i;
4339 free (save->insn_queue);
4341 toggle_cancelled_flags (true);
4343 clock_var = save->clock_var;
4344 last_clock_var = save->last_clock_var;
4345 cycle_issued_insns = save->cycle_issued_insns;
4346 last_scheduled_insn = save->last_scheduled_insn;
4347 last_nondebug_scheduled_insn = save->last_nondebug_scheduled_insn;
4349 *psched_block = save->sched_block;
4351 memcpy (curr_state, save->curr_state, dfa_state_size);
4352 free (save->curr_state);
4354 mark_backtrack_feeds (save->delay_pair->i2, 0);
4356 gcc_assert (VEC_empty (dep_t, next_cycle_replace_deps));
4357 next_cycle_replace_deps = VEC_copy (dep_t, heap, save->next_cycle_deps);
4358 next_cycle_apply = VEC_copy (int, heap, save->next_cycle_apply);
4360 free (save);
4362 for (save = backtrack_queue; save; save = save->next)
4364 mark_backtrack_feeds (save->delay_pair->i2, 1);
4368 /* Discard all data associated with the topmost entry in the backtrack
4369 queue. If RESET_TICK is false, we just want to free the data. If true,
4370 we are doing this because we discovered a reason to backtrack. In the
4371 latter case, also reset the INSN_TICK for the shadow insn. */
4372 static void
4373 free_topmost_backtrack_point (bool reset_tick)
4375 struct haifa_saved_data *save = backtrack_queue;
4376 int i;
4378 backtrack_queue = save->next;
4380 if (reset_tick)
4382 struct delay_pair *pair = save->delay_pair;
4383 while (pair)
4385 INSN_TICK (pair->i2) = INVALID_TICK;
4386 INSN_EXACT_TICK (pair->i2) = INVALID_TICK;
4387 pair = pair->next_same_i1;
4389 undo_replacements_for_backtrack (save);
4391 else
4393 VEC_free (dep_t, heap, save->replacement_deps);
4394 VEC_free (int, heap, save->replace_apply);
4397 if (targetm.sched.free_sched_context)
4398 targetm.sched.free_sched_context (save->be_saved_data);
4399 if (current_sched_info->restore_state)
4400 free (save->fe_saved_data);
4401 for (i = 0; i <= max_insn_queue_index; i++)
4402 free_INSN_LIST_list (&save->insn_queue[i]);
4403 free (save->insn_queue);
4404 free (save->curr_state);
4405 free (save->ready.vec);
4406 free (save);
4409 /* Free the entire backtrack queue. */
4410 static void
4411 free_backtrack_queue (void)
4413 while (backtrack_queue)
4414 free_topmost_backtrack_point (false);
4417 /* Apply a replacement described by DESC. If IMMEDIATELY is false, we
4418 may have to postpone the replacement until the start of the next cycle,
4419 at which point we will be called again with IMMEDIATELY true. This is
4420 only done for machines which have instruction packets with explicit
4421 parallelism however. */
4422 static void
4423 apply_replacement (dep_t dep, bool immediately)
4425 struct dep_replacement *desc = DEP_REPLACE (dep);
4426 if (!immediately && targetm.sched.exposed_pipeline && reload_completed)
4428 VEC_safe_push (dep_t, heap, next_cycle_replace_deps, dep);
4429 VEC_safe_push (int, heap, next_cycle_apply, 1);
4431 else
4433 bool success;
4435 if (QUEUE_INDEX (desc->insn) == QUEUE_SCHEDULED)
4436 return;
4438 if (sched_verbose >= 5)
4439 fprintf (sched_dump, "applying replacement for insn %d\n",
4440 INSN_UID (desc->insn));
4442 success = validate_change (desc->insn, desc->loc, desc->newval, 0);
4443 gcc_assert (success);
4445 update_insn_after_change (desc->insn);
4446 if ((TODO_SPEC (desc->insn) & (HARD_DEP | DEP_POSTPONED)) == 0)
4447 fix_tick_ready (desc->insn);
4449 if (backtrack_queue != NULL)
4451 VEC_safe_push (dep_t, heap, backtrack_queue->replacement_deps, dep);
4452 VEC_safe_push (int, heap, backtrack_queue->replace_apply, 1);
4457 /* We have determined that a pattern involved in DEP must be restored.
4458 If IMMEDIATELY is false, we may have to postpone the replacement
4459 until the start of the next cycle, at which point we will be called
4460 again with IMMEDIATELY true. */
4461 static void
4462 restore_pattern (dep_t dep, bool immediately)
4464 rtx next = DEP_CON (dep);
4465 int tick = INSN_TICK (next);
4467 /* If we already scheduled the insn, the modified version is
4468 correct. */
4469 if (QUEUE_INDEX (next) == QUEUE_SCHEDULED)
4470 return;
4472 if (!immediately && targetm.sched.exposed_pipeline && reload_completed)
4474 VEC_safe_push (dep_t, heap, next_cycle_replace_deps, dep);
4475 VEC_safe_push (int, heap, next_cycle_apply, 0);
4476 return;
4480 if (DEP_TYPE (dep) == REG_DEP_CONTROL)
4482 if (sched_verbose >= 5)
4483 fprintf (sched_dump, "restoring pattern for insn %d\n",
4484 INSN_UID (next));
4485 haifa_change_pattern (next, ORIG_PAT (next));
4487 else
4489 struct dep_replacement *desc = DEP_REPLACE (dep);
4490 bool success;
4492 if (sched_verbose >= 5)
4493 fprintf (sched_dump, "restoring pattern for insn %d\n",
4494 INSN_UID (desc->insn));
4495 tick = INSN_TICK (desc->insn);
4497 success = validate_change (desc->insn, desc->loc, desc->orig, 0);
4498 gcc_assert (success);
4499 update_insn_after_change (desc->insn);
4500 if (backtrack_queue != NULL)
4502 VEC_safe_push (dep_t, heap, backtrack_queue->replacement_deps, dep);
4503 VEC_safe_push (int, heap, backtrack_queue->replace_apply, 0);
4506 INSN_TICK (next) = tick;
4507 if (TODO_SPEC (next) == DEP_POSTPONED)
4508 return;
4510 if (sd_lists_empty_p (next, SD_LIST_BACK))
4511 TODO_SPEC (next) = 0;
4512 else if (!sd_lists_empty_p (next, SD_LIST_HARD_BACK))
4513 TODO_SPEC (next) = HARD_DEP;
4516 /* Perform pattern replacements that were queued up until the next
4517 cycle. */
4518 static void
4519 perform_replacements_new_cycle (void)
4521 int i;
4522 dep_t dep;
4523 FOR_EACH_VEC_ELT (dep_t, next_cycle_replace_deps, i, dep)
4525 int apply_p = VEC_index (int, next_cycle_apply, i);
4526 if (apply_p)
4527 apply_replacement (dep, true);
4528 else
4529 restore_pattern (dep, true);
4531 VEC_truncate (dep_t, next_cycle_replace_deps, 0);
4532 VEC_truncate (int, next_cycle_apply, 0);
4535 /* Compute INSN_TICK_ESTIMATE for INSN. PROCESSED is a bitmap of
4536 instructions we've previously encountered, a set bit prevents
4537 recursion. BUDGET is a limit on how far ahead we look, it is
4538 reduced on recursive calls. Return true if we produced a good
4539 estimate, or false if we exceeded the budget. */
4540 static bool
4541 estimate_insn_tick (bitmap processed, rtx insn, int budget)
4543 sd_iterator_def sd_it;
4544 dep_t dep;
4545 int earliest = INSN_TICK (insn);
4547 FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
4549 rtx pro = DEP_PRO (dep);
4550 int t;
4552 if (DEP_STATUS (dep) & DEP_CANCELLED)
4553 continue;
4555 if (QUEUE_INDEX (pro) == QUEUE_SCHEDULED)
4556 gcc_assert (INSN_TICK (pro) + dep_cost (dep) <= INSN_TICK (insn));
4557 else
4559 int cost = dep_cost (dep);
4560 if (cost >= budget)
4561 return false;
4562 if (!bitmap_bit_p (processed, INSN_LUID (pro)))
4564 if (!estimate_insn_tick (processed, pro, budget - cost))
4565 return false;
4567 gcc_assert (INSN_TICK_ESTIMATE (pro) != INVALID_TICK);
4568 t = INSN_TICK_ESTIMATE (pro) + cost;
4569 if (earliest == INVALID_TICK || t > earliest)
4570 earliest = t;
4573 bitmap_set_bit (processed, INSN_LUID (insn));
4574 INSN_TICK_ESTIMATE (insn) = earliest;
4575 return true;
4578 /* Examine the pair of insns in P, and estimate (optimistically, assuming
4579 infinite resources) the cycle in which the delayed shadow can be issued.
4580 Return the number of cycles that must pass before the real insn can be
4581 issued in order to meet this constraint. */
4582 static int
4583 estimate_shadow_tick (struct delay_pair *p)
4585 bitmap_head processed;
4586 int t;
4587 bool cutoff;
4588 bitmap_initialize (&processed, 0);
4590 cutoff = !estimate_insn_tick (&processed, p->i2,
4591 max_insn_queue_index + pair_delay (p));
4592 bitmap_clear (&processed);
4593 if (cutoff)
4594 return max_insn_queue_index;
4595 t = INSN_TICK_ESTIMATE (p->i2) - (clock_var + pair_delay (p) + 1);
4596 if (t > 0)
4597 return t;
4598 return 0;
4601 /* If INSN has no unresolved backwards dependencies, add it to the schedule and
4602 recursively resolve all its forward dependencies. */
4603 static void
4604 resolve_dependencies (rtx insn)
4606 sd_iterator_def sd_it;
4607 dep_t dep;
4609 /* Don't use sd_lists_empty_p; it ignores debug insns. */
4610 if (DEPS_LIST_FIRST (INSN_HARD_BACK_DEPS (insn)) != NULL
4611 || DEPS_LIST_FIRST (INSN_SPEC_BACK_DEPS (insn)) != NULL)
4612 return;
4614 if (sched_verbose >= 4)
4615 fprintf (sched_dump, ";;\tquickly resolving %d\n", INSN_UID (insn));
4617 if (QUEUE_INDEX (insn) >= 0)
4618 queue_remove (insn);
4620 VEC_safe_push (rtx, heap, scheduled_insns, insn);
4622 /* Update dependent instructions. */
4623 for (sd_it = sd_iterator_start (insn, SD_LIST_FORW);
4624 sd_iterator_cond (&sd_it, &dep);)
4626 rtx next = DEP_CON (dep);
4628 if (sched_verbose >= 4)
4629 fprintf (sched_dump, ";;\t\tdep %d against %d\n", INSN_UID (insn),
4630 INSN_UID (next));
4632 /* Resolve the dependence between INSN and NEXT.
4633 sd_resolve_dep () moves current dep to another list thus
4634 advancing the iterator. */
4635 sd_resolve_dep (sd_it);
4637 if (!IS_SPECULATION_BRANCHY_CHECK_P (insn))
4639 resolve_dependencies (next);
4641 else
4642 /* Check always has only one forward dependence (to the first insn in
4643 the recovery block), therefore, this will be executed only once. */
4645 gcc_assert (sd_lists_empty_p (insn, SD_LIST_FORW));
4651 /* Return the head and tail pointers of ebb starting at BEG and ending
4652 at END. */
4653 void
4654 get_ebb_head_tail (basic_block beg, basic_block end, rtx *headp, rtx *tailp)
4656 rtx beg_head = BB_HEAD (beg);
4657 rtx beg_tail = BB_END (beg);
4658 rtx end_head = BB_HEAD (end);
4659 rtx end_tail = BB_END (end);
4661 /* Don't include any notes or labels at the beginning of the BEG
4662 basic block, or notes at the end of the END basic blocks. */
4664 if (LABEL_P (beg_head))
4665 beg_head = NEXT_INSN (beg_head);
4667 while (beg_head != beg_tail)
4668 if (NOTE_P (beg_head))
4669 beg_head = NEXT_INSN (beg_head);
4670 else if (DEBUG_INSN_P (beg_head))
4672 rtx note, next;
4674 for (note = NEXT_INSN (beg_head);
4675 note != beg_tail;
4676 note = next)
4678 next = NEXT_INSN (note);
4679 if (NOTE_P (note))
4681 if (sched_verbose >= 9)
4682 fprintf (sched_dump, "reorder %i\n", INSN_UID (note));
4684 reorder_insns_nobb (note, note, PREV_INSN (beg_head));
4686 if (BLOCK_FOR_INSN (note) != beg)
4687 df_insn_change_bb (note, beg);
4689 else if (!DEBUG_INSN_P (note))
4690 break;
4693 break;
4695 else
4696 break;
4698 *headp = beg_head;
4700 if (beg == end)
4701 end_head = beg_head;
4702 else if (LABEL_P (end_head))
4703 end_head = NEXT_INSN (end_head);
4705 while (end_head != end_tail)
4706 if (NOTE_P (end_tail))
4707 end_tail = PREV_INSN (end_tail);
4708 else if (DEBUG_INSN_P (end_tail))
4710 rtx note, prev;
4712 for (note = PREV_INSN (end_tail);
4713 note != end_head;
4714 note = prev)
4716 prev = PREV_INSN (note);
4717 if (NOTE_P (note))
4719 if (sched_verbose >= 9)
4720 fprintf (sched_dump, "reorder %i\n", INSN_UID (note));
4722 reorder_insns_nobb (note, note, end_tail);
4724 if (end_tail == BB_END (end))
4725 BB_END (end) = note;
4727 if (BLOCK_FOR_INSN (note) != end)
4728 df_insn_change_bb (note, end);
4730 else if (!DEBUG_INSN_P (note))
4731 break;
4734 break;
4736 else
4737 break;
4739 *tailp = end_tail;
4742 /* Return nonzero if there are no real insns in the range [ HEAD, TAIL ]. */
4745 no_real_insns_p (const_rtx head, const_rtx tail)
4747 while (head != NEXT_INSN (tail))
4749 if (!NOTE_P (head) && !LABEL_P (head))
4750 return 0;
4751 head = NEXT_INSN (head);
4753 return 1;
4756 /* Restore-other-notes: NOTE_LIST is the end of a chain of notes
4757 previously found among the insns. Insert them just before HEAD. */
4759 restore_other_notes (rtx head, basic_block head_bb)
4761 if (note_list != 0)
4763 rtx note_head = note_list;
4765 if (head)
4766 head_bb = BLOCK_FOR_INSN (head);
4767 else
4768 head = NEXT_INSN (bb_note (head_bb));
4770 while (PREV_INSN (note_head))
4772 set_block_for_insn (note_head, head_bb);
4773 note_head = PREV_INSN (note_head);
4775 /* In the above cycle we've missed this note. */
4776 set_block_for_insn (note_head, head_bb);
4778 PREV_INSN (note_head) = PREV_INSN (head);
4779 NEXT_INSN (PREV_INSN (head)) = note_head;
4780 PREV_INSN (head) = note_list;
4781 NEXT_INSN (note_list) = head;
4783 if (BLOCK_FOR_INSN (head) != head_bb)
4784 BB_END (head_bb) = note_list;
4786 head = note_head;
4789 return head;
4792 /* When we know we are going to discard the schedule due to a failed attempt
4793 at modulo scheduling, undo all replacements. */
4794 static void
4795 undo_all_replacements (void)
4797 rtx insn;
4798 int i;
4800 FOR_EACH_VEC_ELT (rtx, scheduled_insns, i, insn)
4802 sd_iterator_def sd_it;
4803 dep_t dep;
4805 /* See if we must undo a replacement. */
4806 for (sd_it = sd_iterator_start (insn, SD_LIST_RES_FORW);
4807 sd_iterator_cond (&sd_it, &dep); sd_iterator_next (&sd_it))
4809 struct dep_replacement *desc = DEP_REPLACE (dep);
4810 if (desc != NULL)
4811 validate_change (desc->insn, desc->loc, desc->orig, 0);
4816 /* Move insns that became ready to fire from queue to ready list. */
4818 static void
4819 queue_to_ready (struct ready_list *ready)
4821 rtx insn;
4822 rtx link;
4823 rtx skip_insn;
4825 q_ptr = NEXT_Q (q_ptr);
4827 if (dbg_cnt (sched_insn) == false)
4829 /* If debug counter is activated do not requeue the first
4830 nonscheduled insn. */
4831 skip_insn = nonscheduled_insns_begin;
4834 skip_insn = next_nonnote_nondebug_insn (skip_insn);
4836 while (QUEUE_INDEX (skip_insn) == QUEUE_SCHEDULED);
4838 else
4839 skip_insn = NULL_RTX;
4841 /* Add all pending insns that can be scheduled without stalls to the
4842 ready list. */
4843 for (link = insn_queue[q_ptr]; link; link = XEXP (link, 1))
4845 insn = XEXP (link, 0);
4846 q_size -= 1;
4848 if (sched_verbose >= 2)
4849 fprintf (sched_dump, ";;\t\tQ-->Ready: insn %s: ",
4850 (*current_sched_info->print_insn) (insn, 0));
4852 /* If the ready list is full, delay the insn for 1 cycle.
4853 See the comment in schedule_block for the rationale. */
4854 if (!reload_completed
4855 && (ready->n_ready - ready->n_debug > MAX_SCHED_READY_INSNS
4856 || (sched_pressure == SCHED_PRESSURE_MODEL
4857 /* Limit pressure recalculations to MAX_SCHED_READY_INSNS
4858 instructions too. */
4859 && model_index (insn) > (model_curr_point
4860 + MAX_SCHED_READY_INSNS)))
4861 && !(sched_pressure == SCHED_PRESSURE_MODEL
4862 && model_curr_point < model_num_insns
4863 /* Always allow the next model instruction to issue. */
4864 && model_index (insn) == model_curr_point)
4865 && !SCHED_GROUP_P (insn)
4866 && insn != skip_insn)
4867 queue_insn (insn, 1, "ready full");
4868 else
4870 ready_add (ready, insn, false);
4871 if (sched_verbose >= 2)
4872 fprintf (sched_dump, "moving to ready without stalls\n");
4875 free_INSN_LIST_list (&insn_queue[q_ptr]);
4877 /* If there are no ready insns, stall until one is ready and add all
4878 of the pending insns at that point to the ready list. */
4879 if (ready->n_ready == 0)
4881 int stalls;
4883 for (stalls = 1; stalls <= max_insn_queue_index; stalls++)
4885 if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
4887 for (; link; link = XEXP (link, 1))
4889 insn = XEXP (link, 0);
4890 q_size -= 1;
4892 if (sched_verbose >= 2)
4893 fprintf (sched_dump, ";;\t\tQ-->Ready: insn %s: ",
4894 (*current_sched_info->print_insn) (insn, 0));
4896 ready_add (ready, insn, false);
4897 if (sched_verbose >= 2)
4898 fprintf (sched_dump, "moving to ready with %d stalls\n", stalls);
4900 free_INSN_LIST_list (&insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]);
4902 advance_one_cycle ();
4904 break;
4907 advance_one_cycle ();
4910 q_ptr = NEXT_Q_AFTER (q_ptr, stalls);
4911 clock_var += stalls;
4915 /* Used by early_queue_to_ready. Determines whether it is "ok" to
4916 prematurely move INSN from the queue to the ready list. Currently,
4917 if a target defines the hook 'is_costly_dependence', this function
4918 uses the hook to check whether there exist any dependences which are
4919 considered costly by the target, between INSN and other insns that
4920 have already been scheduled. Dependences are checked up to Y cycles
4921 back, with default Y=1; The flag -fsched-stalled-insns-dep=Y allows
4922 controlling this value.
4923 (Other considerations could be taken into account instead (or in
4924 addition) depending on user flags and target hooks. */
4926 static bool
4927 ok_for_early_queue_removal (rtx insn)
4929 if (targetm.sched.is_costly_dependence)
4931 rtx prev_insn;
4932 int n_cycles;
4933 int i = VEC_length (rtx, scheduled_insns);
4934 for (n_cycles = flag_sched_stalled_insns_dep; n_cycles; n_cycles--)
4936 while (i-- > 0)
4938 int cost;
4940 prev_insn = VEC_index (rtx, scheduled_insns, i);
4942 if (!NOTE_P (prev_insn))
4944 dep_t dep;
4946 dep = sd_find_dep_between (prev_insn, insn, true);
4948 if (dep != NULL)
4950 cost = dep_cost (dep);
4952 if (targetm.sched.is_costly_dependence (dep, cost,
4953 flag_sched_stalled_insns_dep - n_cycles))
4954 return false;
4958 if (GET_MODE (prev_insn) == TImode) /* end of dispatch group */
4959 break;
4962 if (i == 0)
4963 break;
4967 return true;
4971 /* Remove insns from the queue, before they become "ready" with respect
4972 to FU latency considerations. */
4974 static int
4975 early_queue_to_ready (state_t state, struct ready_list *ready)
4977 rtx insn;
4978 rtx link;
4979 rtx next_link;
4980 rtx prev_link;
4981 bool move_to_ready;
4982 int cost;
4983 state_t temp_state = alloca (dfa_state_size);
4984 int stalls;
4985 int insns_removed = 0;
4988 Flag '-fsched-stalled-insns=X' determines the aggressiveness of this
4989 function:
4991 X == 0: There is no limit on how many queued insns can be removed
4992 prematurely. (flag_sched_stalled_insns = -1).
4994 X >= 1: Only X queued insns can be removed prematurely in each
4995 invocation. (flag_sched_stalled_insns = X).
4997 Otherwise: Early queue removal is disabled.
4998 (flag_sched_stalled_insns = 0)
5001 if (! flag_sched_stalled_insns)
5002 return 0;
5004 for (stalls = 0; stalls <= max_insn_queue_index; stalls++)
5006 if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
5008 if (sched_verbose > 6)
5009 fprintf (sched_dump, ";; look at index %d + %d\n", q_ptr, stalls);
5011 prev_link = 0;
5012 while (link)
5014 next_link = XEXP (link, 1);
5015 insn = XEXP (link, 0);
5016 if (insn && sched_verbose > 6)
5017 print_rtl_single (sched_dump, insn);
5019 memcpy (temp_state, state, dfa_state_size);
5020 if (recog_memoized (insn) < 0)
5021 /* non-negative to indicate that it's not ready
5022 to avoid infinite Q->R->Q->R... */
5023 cost = 0;
5024 else
5025 cost = state_transition (temp_state, insn);
5027 if (sched_verbose >= 6)
5028 fprintf (sched_dump, "transition cost = %d\n", cost);
5030 move_to_ready = false;
5031 if (cost < 0)
5033 move_to_ready = ok_for_early_queue_removal (insn);
5034 if (move_to_ready == true)
5036 /* move from Q to R */
5037 q_size -= 1;
5038 ready_add (ready, insn, false);
5040 if (prev_link)
5041 XEXP (prev_link, 1) = next_link;
5042 else
5043 insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = next_link;
5045 free_INSN_LIST_node (link);
5047 if (sched_verbose >= 2)
5048 fprintf (sched_dump, ";;\t\tEarly Q-->Ready: insn %s\n",
5049 (*current_sched_info->print_insn) (insn, 0));
5051 insns_removed++;
5052 if (insns_removed == flag_sched_stalled_insns)
5053 /* Remove no more than flag_sched_stalled_insns insns
5054 from Q at a time. */
5055 return insns_removed;
5059 if (move_to_ready == false)
5060 prev_link = link;
5062 link = next_link;
5063 } /* while link */
5064 } /* if link */
5066 } /* for stalls.. */
5068 return insns_removed;
5072 /* Print the ready list for debugging purposes. Callable from debugger. */
5074 static void
5075 debug_ready_list (struct ready_list *ready)
5077 rtx *p;
5078 int i;
5080 if (ready->n_ready == 0)
5082 fprintf (sched_dump, "\n");
5083 return;
5086 p = ready_lastpos (ready);
5087 for (i = 0; i < ready->n_ready; i++)
5089 fprintf (sched_dump, " %s:%d",
5090 (*current_sched_info->print_insn) (p[i], 0),
5091 INSN_LUID (p[i]));
5092 if (sched_pressure != SCHED_PRESSURE_NONE)
5093 fprintf (sched_dump, "(cost=%d",
5094 INSN_REG_PRESSURE_EXCESS_COST_CHANGE (p[i]));
5095 if (INSN_TICK (p[i]) > clock_var)
5096 fprintf (sched_dump, ":delay=%d", INSN_TICK (p[i]) - clock_var);
5097 if (sched_pressure != SCHED_PRESSURE_NONE)
5098 fprintf (sched_dump, ")");
5100 fprintf (sched_dump, "\n");
5103 /* Search INSN for REG_SAVE_NOTE notes and convert them back into insn
5104 NOTEs. This is used for NOTE_INSN_EPILOGUE_BEG, so that sched-ebb
5105 replaces the epilogue note in the correct basic block. */
5106 void
5107 reemit_notes (rtx insn)
5109 rtx note, last = insn;
5111 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
5113 if (REG_NOTE_KIND (note) == REG_SAVE_NOTE)
5115 enum insn_note note_type = (enum insn_note) INTVAL (XEXP (note, 0));
5117 last = emit_note_before (note_type, last);
5118 remove_note (insn, note);
5123 /* Move INSN. Reemit notes if needed. Update CFG, if needed. */
5124 static void
5125 move_insn (rtx insn, rtx last, rtx nt)
5127 if (PREV_INSN (insn) != last)
5129 basic_block bb;
5130 rtx note;
5131 int jump_p = 0;
5133 bb = BLOCK_FOR_INSN (insn);
5135 /* BB_HEAD is either LABEL or NOTE. */
5136 gcc_assert (BB_HEAD (bb) != insn);
5138 if (BB_END (bb) == insn)
5139 /* If this is last instruction in BB, move end marker one
5140 instruction up. */
5142 /* Jumps are always placed at the end of basic block. */
5143 jump_p = control_flow_insn_p (insn);
5145 gcc_assert (!jump_p
5146 || ((common_sched_info->sched_pass_id == SCHED_RGN_PASS)
5147 && IS_SPECULATION_BRANCHY_CHECK_P (insn))
5148 || (common_sched_info->sched_pass_id
5149 == SCHED_EBB_PASS));
5151 gcc_assert (BLOCK_FOR_INSN (PREV_INSN (insn)) == bb);
5153 BB_END (bb) = PREV_INSN (insn);
5156 gcc_assert (BB_END (bb) != last);
5158 if (jump_p)
5159 /* We move the block note along with jump. */
5161 gcc_assert (nt);
5163 note = NEXT_INSN (insn);
5164 while (NOTE_NOT_BB_P (note) && note != nt)
5165 note = NEXT_INSN (note);
5167 if (note != nt
5168 && (LABEL_P (note)
5169 || BARRIER_P (note)))
5170 note = NEXT_INSN (note);
5172 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
5174 else
5175 note = insn;
5177 NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (note);
5178 PREV_INSN (NEXT_INSN (note)) = PREV_INSN (insn);
5180 NEXT_INSN (note) = NEXT_INSN (last);
5181 PREV_INSN (NEXT_INSN (last)) = note;
5183 NEXT_INSN (last) = insn;
5184 PREV_INSN (insn) = last;
5186 bb = BLOCK_FOR_INSN (last);
5188 if (jump_p)
5190 fix_jump_move (insn);
5192 if (BLOCK_FOR_INSN (insn) != bb)
5193 move_block_after_check (insn);
5195 gcc_assert (BB_END (bb) == last);
5198 df_insn_change_bb (insn, bb);
5200 /* Update BB_END, if needed. */
5201 if (BB_END (bb) == last)
5202 BB_END (bb) = insn;
5205 SCHED_GROUP_P (insn) = 0;
5208 /* Return true if scheduling INSN will finish current clock cycle. */
5209 static bool
5210 insn_finishes_cycle_p (rtx insn)
5212 if (SCHED_GROUP_P (insn))
5213 /* After issuing INSN, rest of the sched_group will be forced to issue
5214 in order. Don't make any plans for the rest of cycle. */
5215 return true;
5217 /* Finishing the block will, apparently, finish the cycle. */
5218 if (current_sched_info->insn_finishes_block_p
5219 && current_sched_info->insn_finishes_block_p (insn))
5220 return true;
5222 return false;
5225 /* Define type for target data used in multipass scheduling. */
5226 #ifndef TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DATA_T
5227 # define TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DATA_T int
5228 #endif
5229 typedef TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DATA_T first_cycle_multipass_data_t;
5231 /* The following structure describe an entry of the stack of choices. */
5232 struct choice_entry
5234 /* Ordinal number of the issued insn in the ready queue. */
5235 int index;
5236 /* The number of the rest insns whose issues we should try. */
5237 int rest;
5238 /* The number of issued essential insns. */
5239 int n;
5240 /* State after issuing the insn. */
5241 state_t state;
5242 /* Target-specific data. */
5243 first_cycle_multipass_data_t target_data;
5246 /* The following array is used to implement a stack of choices used in
5247 function max_issue. */
5248 static struct choice_entry *choice_stack;
5250 /* This holds the value of the target dfa_lookahead hook. */
5251 int dfa_lookahead;
5253 /* The following variable value is maximal number of tries of issuing
5254 insns for the first cycle multipass insn scheduling. We define
5255 this value as constant*(DFA_LOOKAHEAD**ISSUE_RATE). We would not
5256 need this constraint if all real insns (with non-negative codes)
5257 had reservations because in this case the algorithm complexity is
5258 O(DFA_LOOKAHEAD**ISSUE_RATE). Unfortunately, the dfa descriptions
5259 might be incomplete and such insn might occur. For such
5260 descriptions, the complexity of algorithm (without the constraint)
5261 could achieve DFA_LOOKAHEAD ** N , where N is the queue length. */
5262 static int max_lookahead_tries;
5264 /* The following value is value of hook
5265 `first_cycle_multipass_dfa_lookahead' at the last call of
5266 `max_issue'. */
5267 static int cached_first_cycle_multipass_dfa_lookahead = 0;
5269 /* The following value is value of `issue_rate' at the last call of
5270 `sched_init'. */
5271 static int cached_issue_rate = 0;
5273 /* The following function returns maximal (or close to maximal) number
5274 of insns which can be issued on the same cycle and one of which
5275 insns is insns with the best rank (the first insn in READY). To
5276 make this function tries different samples of ready insns. READY
5277 is current queue `ready'. Global array READY_TRY reflects what
5278 insns are already issued in this try. The function stops immediately,
5279 if it reached the such a solution, that all instruction can be issued.
5280 INDEX will contain index of the best insn in READY. The following
5281 function is used only for first cycle multipass scheduling.
5283 PRIVILEGED_N >= 0
5285 This function expects recognized insns only. All USEs,
5286 CLOBBERs, etc must be filtered elsewhere. */
5288 max_issue (struct ready_list *ready, int privileged_n, state_t state,
5289 bool first_cycle_insn_p, int *index)
5291 int n, i, all, n_ready, best, delay, tries_num;
5292 int more_issue;
5293 struct choice_entry *top;
5294 rtx insn;
5296 n_ready = ready->n_ready;
5297 gcc_assert (dfa_lookahead >= 1 && privileged_n >= 0
5298 && privileged_n <= n_ready);
5300 /* Init MAX_LOOKAHEAD_TRIES. */
5301 if (cached_first_cycle_multipass_dfa_lookahead != dfa_lookahead)
5303 cached_first_cycle_multipass_dfa_lookahead = dfa_lookahead;
5304 max_lookahead_tries = 100;
5305 for (i = 0; i < issue_rate; i++)
5306 max_lookahead_tries *= dfa_lookahead;
5309 /* Init max_points. */
5310 more_issue = issue_rate - cycle_issued_insns;
5311 gcc_assert (more_issue >= 0);
5313 /* The number of the issued insns in the best solution. */
5314 best = 0;
5316 top = choice_stack;
5318 /* Set initial state of the search. */
5319 memcpy (top->state, state, dfa_state_size);
5320 top->rest = dfa_lookahead;
5321 top->n = 0;
5322 if (targetm.sched.first_cycle_multipass_begin)
5323 targetm.sched.first_cycle_multipass_begin (&top->target_data,
5324 ready_try, n_ready,
5325 first_cycle_insn_p);
5327 /* Count the number of the insns to search among. */
5328 for (all = i = 0; i < n_ready; i++)
5329 if (!ready_try [i])
5330 all++;
5332 /* I is the index of the insn to try next. */
5333 i = 0;
5334 tries_num = 0;
5335 for (;;)
5337 if (/* If we've reached a dead end or searched enough of what we have
5338 been asked... */
5339 top->rest == 0
5340 /* or have nothing else to try... */
5341 || i >= n_ready
5342 /* or should not issue more. */
5343 || top->n >= more_issue)
5345 /* ??? (... || i == n_ready). */
5346 gcc_assert (i <= n_ready);
5348 /* We should not issue more than issue_rate instructions. */
5349 gcc_assert (top->n <= more_issue);
5351 if (top == choice_stack)
5352 break;
5354 if (best < top - choice_stack)
5356 if (privileged_n)
5358 n = privileged_n;
5359 /* Try to find issued privileged insn. */
5360 while (n && !ready_try[--n])
5364 if (/* If all insns are equally good... */
5365 privileged_n == 0
5366 /* Or a privileged insn will be issued. */
5367 || ready_try[n])
5368 /* Then we have a solution. */
5370 best = top - choice_stack;
5371 /* This is the index of the insn issued first in this
5372 solution. */
5373 *index = choice_stack [1].index;
5374 if (top->n == more_issue || best == all)
5375 break;
5379 /* Set ready-list index to point to the last insn
5380 ('i++' below will advance it to the next insn). */
5381 i = top->index;
5383 /* Backtrack. */
5384 ready_try [i] = 0;
5386 if (targetm.sched.first_cycle_multipass_backtrack)
5387 targetm.sched.first_cycle_multipass_backtrack (&top->target_data,
5388 ready_try, n_ready);
5390 top--;
5391 memcpy (state, top->state, dfa_state_size);
5393 else if (!ready_try [i])
5395 tries_num++;
5396 if (tries_num > max_lookahead_tries)
5397 break;
5398 insn = ready_element (ready, i);
5399 delay = state_transition (state, insn);
5400 if (delay < 0)
5402 if (state_dead_lock_p (state)
5403 || insn_finishes_cycle_p (insn))
5404 /* We won't issue any more instructions in the next
5405 choice_state. */
5406 top->rest = 0;
5407 else
5408 top->rest--;
5410 n = top->n;
5411 if (memcmp (top->state, state, dfa_state_size) != 0)
5412 n++;
5414 /* Advance to the next choice_entry. */
5415 top++;
5416 /* Initialize it. */
5417 top->rest = dfa_lookahead;
5418 top->index = i;
5419 top->n = n;
5420 memcpy (top->state, state, dfa_state_size);
5421 ready_try [i] = 1;
5423 if (targetm.sched.first_cycle_multipass_issue)
5424 targetm.sched.first_cycle_multipass_issue (&top->target_data,
5425 ready_try, n_ready,
5426 insn,
5427 &((top - 1)
5428 ->target_data));
5430 i = -1;
5434 /* Increase ready-list index. */
5435 i++;
5438 if (targetm.sched.first_cycle_multipass_end)
5439 targetm.sched.first_cycle_multipass_end (best != 0
5440 ? &choice_stack[1].target_data
5441 : NULL);
5443 /* Restore the original state of the DFA. */
5444 memcpy (state, choice_stack->state, dfa_state_size);
5446 return best;
5449 /* The following function chooses insn from READY and modifies
5450 READY. The following function is used only for first
5451 cycle multipass scheduling.
5452 Return:
5453 -1 if cycle should be advanced,
5454 0 if INSN_PTR is set to point to the desirable insn,
5455 1 if choose_ready () should be restarted without advancing the cycle. */
5456 static int
5457 choose_ready (struct ready_list *ready, bool first_cycle_insn_p,
5458 rtx *insn_ptr)
5460 int lookahead;
5462 if (dbg_cnt (sched_insn) == false)
5464 rtx insn = nonscheduled_insns_begin;
5467 insn = next_nonnote_insn (insn);
5469 while (QUEUE_INDEX (insn) == QUEUE_SCHEDULED);
5471 if (QUEUE_INDEX (insn) == QUEUE_READY)
5472 /* INSN is in the ready_list. */
5474 nonscheduled_insns_begin = insn;
5475 ready_remove_insn (insn);
5476 *insn_ptr = insn;
5477 return 0;
5480 /* INSN is in the queue. Advance cycle to move it to the ready list. */
5481 return -1;
5484 lookahead = 0;
5486 if (targetm.sched.first_cycle_multipass_dfa_lookahead)
5487 lookahead = targetm.sched.first_cycle_multipass_dfa_lookahead ();
5488 if (lookahead <= 0 || SCHED_GROUP_P (ready_element (ready, 0))
5489 || DEBUG_INSN_P (ready_element (ready, 0)))
5491 if (targetm.sched.dispatch (NULL_RTX, IS_DISPATCH_ON))
5492 *insn_ptr = ready_remove_first_dispatch (ready);
5493 else
5494 *insn_ptr = ready_remove_first (ready);
5496 return 0;
5498 else
5500 /* Try to choose the better insn. */
5501 int index = 0, i, n;
5502 rtx insn;
5503 int try_data = 1, try_control = 1;
5504 ds_t ts;
5506 insn = ready_element (ready, 0);
5507 if (INSN_CODE (insn) < 0)
5509 *insn_ptr = ready_remove_first (ready);
5510 return 0;
5513 if (spec_info
5514 && spec_info->flags & (PREFER_NON_DATA_SPEC
5515 | PREFER_NON_CONTROL_SPEC))
5517 for (i = 0, n = ready->n_ready; i < n; i++)
5519 rtx x;
5520 ds_t s;
5522 x = ready_element (ready, i);
5523 s = TODO_SPEC (x);
5525 if (spec_info->flags & PREFER_NON_DATA_SPEC
5526 && !(s & DATA_SPEC))
5528 try_data = 0;
5529 if (!(spec_info->flags & PREFER_NON_CONTROL_SPEC)
5530 || !try_control)
5531 break;
5534 if (spec_info->flags & PREFER_NON_CONTROL_SPEC
5535 && !(s & CONTROL_SPEC))
5537 try_control = 0;
5538 if (!(spec_info->flags & PREFER_NON_DATA_SPEC) || !try_data)
5539 break;
5544 ts = TODO_SPEC (insn);
5545 if ((ts & SPECULATIVE)
5546 && (((!try_data && (ts & DATA_SPEC))
5547 || (!try_control && (ts & CONTROL_SPEC)))
5548 || (targetm.sched.first_cycle_multipass_dfa_lookahead_guard_spec
5549 && !targetm.sched
5550 .first_cycle_multipass_dfa_lookahead_guard_spec (insn))))
5551 /* Discard speculative instruction that stands first in the ready
5552 list. */
5554 change_queue_index (insn, 1);
5555 return 1;
5558 ready_try[0] = 0;
5560 for (i = 1; i < ready->n_ready; i++)
5562 insn = ready_element (ready, i);
5564 ready_try [i]
5565 = ((!try_data && (TODO_SPEC (insn) & DATA_SPEC))
5566 || (!try_control && (TODO_SPEC (insn) & CONTROL_SPEC)));
5569 /* Let the target filter the search space. */
5570 for (i = 1; i < ready->n_ready; i++)
5571 if (!ready_try[i])
5573 insn = ready_element (ready, i);
5575 /* If this insn is recognizable we should have already
5576 recognized it earlier.
5577 ??? Not very clear where this is supposed to be done.
5578 See dep_cost_1. */
5579 gcc_checking_assert (INSN_CODE (insn) >= 0
5580 || recog_memoized (insn) < 0);
5582 ready_try [i]
5583 = (/* INSN_CODE check can be omitted here as it is also done later
5584 in max_issue (). */
5585 INSN_CODE (insn) < 0
5586 || (targetm.sched.first_cycle_multipass_dfa_lookahead_guard
5587 && !targetm.sched.first_cycle_multipass_dfa_lookahead_guard
5588 (insn)));
5591 if (max_issue (ready, 1, curr_state, first_cycle_insn_p, &index) == 0)
5593 *insn_ptr = ready_remove_first (ready);
5594 if (sched_verbose >= 4)
5595 fprintf (sched_dump, ";;\t\tChosen insn (but can't issue) : %s \n",
5596 (*current_sched_info->print_insn) (*insn_ptr, 0));
5597 return 0;
5599 else
5601 if (sched_verbose >= 4)
5602 fprintf (sched_dump, ";;\t\tChosen insn : %s\n",
5603 (*current_sched_info->print_insn)
5604 (ready_element (ready, index), 0));
5606 *insn_ptr = ready_remove (ready, index);
5607 return 0;
5612 /* This function is called when we have successfully scheduled a
5613 block. It uses the schedule stored in the scheduled_insns vector
5614 to rearrange the RTL. PREV_HEAD is used as the anchor to which we
5615 append the scheduled insns; TAIL is the insn after the scheduled
5616 block. TARGET_BB is the argument passed to schedule_block. */
5618 static void
5619 commit_schedule (rtx prev_head, rtx tail, basic_block *target_bb)
5621 unsigned int i;
5622 rtx insn;
5624 last_scheduled_insn = prev_head;
5625 for (i = 0;
5626 VEC_iterate (rtx, scheduled_insns, i, insn);
5627 i++)
5629 if (control_flow_insn_p (last_scheduled_insn)
5630 || current_sched_info->advance_target_bb (*target_bb, insn))
5632 *target_bb = current_sched_info->advance_target_bb (*target_bb, 0);
5634 if (sched_verbose)
5636 rtx x;
5638 x = next_real_insn (last_scheduled_insn);
5639 gcc_assert (x);
5640 dump_new_block_header (1, *target_bb, x, tail);
5643 last_scheduled_insn = bb_note (*target_bb);
5646 if (current_sched_info->begin_move_insn)
5647 (*current_sched_info->begin_move_insn) (insn, last_scheduled_insn);
5648 move_insn (insn, last_scheduled_insn,
5649 current_sched_info->next_tail);
5650 if (!DEBUG_INSN_P (insn))
5651 reemit_notes (insn);
5652 last_scheduled_insn = insn;
5655 VEC_truncate (rtx, scheduled_insns, 0);
5658 /* Examine all insns on the ready list and queue those which can't be
5659 issued in this cycle. TEMP_STATE is temporary scheduler state we
5660 can use as scratch space. If FIRST_CYCLE_INSN_P is true, no insns
5661 have been issued for the current cycle, which means it is valid to
5662 issue an asm statement.
5664 If SHADOWS_ONLY_P is true, we eliminate all real insns and only
5665 leave those for which SHADOW_P is true. If MODULO_EPILOGUE is true,
5666 we only leave insns which have an INSN_EXACT_TICK. */
5668 static void
5669 prune_ready_list (state_t temp_state, bool first_cycle_insn_p,
5670 bool shadows_only_p, bool modulo_epilogue_p)
5672 int i, pass;
5673 bool sched_group_found = false;
5674 int min_cost_group = 1;
5676 for (i = 0; i < ready.n_ready; i++)
5678 rtx insn = ready_element (&ready, i);
5679 if (SCHED_GROUP_P (insn))
5681 sched_group_found = true;
5682 break;
5686 /* Make two passes if there's a SCHED_GROUP_P insn; make sure to handle
5687 such an insn first and note its cost, then schedule all other insns
5688 for one cycle later. */
5689 for (pass = sched_group_found ? 0 : 1; pass < 2; )
5691 int n = ready.n_ready;
5692 for (i = 0; i < n; i++)
5694 rtx insn = ready_element (&ready, i);
5695 int cost = 0;
5696 const char *reason = "resource conflict";
5698 if (DEBUG_INSN_P (insn))
5699 continue;
5701 if (sched_group_found && !SCHED_GROUP_P (insn))
5703 if (pass == 0)
5704 continue;
5705 cost = min_cost_group;
5706 reason = "not in sched group";
5708 else if (modulo_epilogue_p
5709 && INSN_EXACT_TICK (insn) == INVALID_TICK)
5711 cost = max_insn_queue_index;
5712 reason = "not an epilogue insn";
5714 else if (shadows_only_p && !SHADOW_P (insn))
5716 cost = 1;
5717 reason = "not a shadow";
5719 else if (recog_memoized (insn) < 0)
5721 if (!first_cycle_insn_p
5722 && (GET_CODE (PATTERN (insn)) == ASM_INPUT
5723 || asm_noperands (PATTERN (insn)) >= 0))
5724 cost = 1;
5725 reason = "asm";
5727 else if (sched_pressure != SCHED_PRESSURE_NONE)
5729 if (sched_pressure == SCHED_PRESSURE_MODEL
5730 && INSN_TICK (insn) <= clock_var)
5732 memcpy (temp_state, curr_state, dfa_state_size);
5733 if (state_transition (temp_state, insn) >= 0)
5734 INSN_TICK (insn) = clock_var + 1;
5736 cost = 0;
5738 else
5740 int delay_cost = 0;
5742 if (delay_htab)
5744 struct delay_pair *delay_entry;
5745 delay_entry
5746 = (struct delay_pair *)htab_find_with_hash (delay_htab, insn,
5747 htab_hash_pointer (insn));
5748 while (delay_entry && delay_cost == 0)
5750 delay_cost = estimate_shadow_tick (delay_entry);
5751 if (delay_cost > max_insn_queue_index)
5752 delay_cost = max_insn_queue_index;
5753 delay_entry = delay_entry->next_same_i1;
5757 memcpy (temp_state, curr_state, dfa_state_size);
5758 cost = state_transition (temp_state, insn);
5759 if (cost < 0)
5760 cost = 0;
5761 else if (cost == 0)
5762 cost = 1;
5763 if (cost < delay_cost)
5765 cost = delay_cost;
5766 reason = "shadow tick";
5769 if (cost >= 1)
5771 if (SCHED_GROUP_P (insn) && cost > min_cost_group)
5772 min_cost_group = cost;
5773 ready_remove (&ready, i);
5774 queue_insn (insn, cost, reason);
5775 if (i + 1 < n)
5776 break;
5779 if (i == n)
5780 pass++;
5784 /* Called when we detect that the schedule is impossible. We examine the
5785 backtrack queue to find the earliest insn that caused this condition. */
5787 static struct haifa_saved_data *
5788 verify_shadows (void)
5790 struct haifa_saved_data *save, *earliest_fail = NULL;
5791 for (save = backtrack_queue; save; save = save->next)
5793 int t;
5794 struct delay_pair *pair = save->delay_pair;
5795 rtx i1 = pair->i1;
5797 for (; pair; pair = pair->next_same_i1)
5799 rtx i2 = pair->i2;
5801 if (QUEUE_INDEX (i2) == QUEUE_SCHEDULED)
5802 continue;
5804 t = INSN_TICK (i1) + pair_delay (pair);
5805 if (t < clock_var)
5807 if (sched_verbose >= 2)
5808 fprintf (sched_dump,
5809 ";;\t\tfailed delay requirements for %d/%d (%d->%d)"
5810 ", not ready\n",
5811 INSN_UID (pair->i1), INSN_UID (pair->i2),
5812 INSN_TICK (pair->i1), INSN_EXACT_TICK (pair->i2));
5813 earliest_fail = save;
5814 break;
5816 if (QUEUE_INDEX (i2) >= 0)
5818 int queued_for = INSN_TICK (i2);
5820 if (t < queued_for)
5822 if (sched_verbose >= 2)
5823 fprintf (sched_dump,
5824 ";;\t\tfailed delay requirements for %d/%d"
5825 " (%d->%d), queued too late\n",
5826 INSN_UID (pair->i1), INSN_UID (pair->i2),
5827 INSN_TICK (pair->i1), INSN_EXACT_TICK (pair->i2));
5828 earliest_fail = save;
5829 break;
5835 return earliest_fail;
5838 /* Use forward list scheduling to rearrange insns of block pointed to by
5839 TARGET_BB, possibly bringing insns from subsequent blocks in the same
5840 region. */
5842 bool
5843 schedule_block (basic_block *target_bb, state_t init_state)
5845 int i;
5846 bool success = modulo_ii == 0;
5847 struct sched_block_state ls;
5848 state_t temp_state = NULL; /* It is used for multipass scheduling. */
5849 int sort_p, advance, start_clock_var;
5851 /* Head/tail info for this block. */
5852 rtx prev_head = current_sched_info->prev_head;
5853 rtx next_tail = current_sched_info->next_tail;
5854 rtx head = NEXT_INSN (prev_head);
5855 rtx tail = PREV_INSN (next_tail);
5857 if ((current_sched_info->flags & DONT_BREAK_DEPENDENCIES) == 0
5858 && sched_pressure != SCHED_PRESSURE_MODEL)
5859 find_modifiable_mems (head, tail);
5861 /* We used to have code to avoid getting parameters moved from hard
5862 argument registers into pseudos.
5864 However, it was removed when it proved to be of marginal benefit
5865 and caused problems because schedule_block and compute_forward_dependences
5866 had different notions of what the "head" insn was. */
5868 gcc_assert (head != tail || INSN_P (head));
5870 haifa_recovery_bb_recently_added_p = false;
5872 backtrack_queue = NULL;
5874 /* Debug info. */
5875 if (sched_verbose)
5876 dump_new_block_header (0, *target_bb, head, tail);
5878 if (init_state == NULL)
5879 state_reset (curr_state);
5880 else
5881 memcpy (curr_state, init_state, dfa_state_size);
5883 /* Clear the ready list. */
5884 ready.first = ready.veclen - 1;
5885 ready.n_ready = 0;
5886 ready.n_debug = 0;
5888 /* It is used for first cycle multipass scheduling. */
5889 temp_state = alloca (dfa_state_size);
5891 if (targetm.sched.init)
5892 targetm.sched.init (sched_dump, sched_verbose, ready.veclen);
5894 /* We start inserting insns after PREV_HEAD. */
5895 last_scheduled_insn = nonscheduled_insns_begin = prev_head;
5896 last_nondebug_scheduled_insn = NULL_RTX;
5898 gcc_assert ((NOTE_P (last_scheduled_insn)
5899 || DEBUG_INSN_P (last_scheduled_insn))
5900 && BLOCK_FOR_INSN (last_scheduled_insn) == *target_bb);
5902 /* Initialize INSN_QUEUE. Q_SIZE is the total number of insns in the
5903 queue. */
5904 q_ptr = 0;
5905 q_size = 0;
5907 insn_queue = XALLOCAVEC (rtx, max_insn_queue_index + 1);
5908 memset (insn_queue, 0, (max_insn_queue_index + 1) * sizeof (rtx));
5910 /* Start just before the beginning of time. */
5911 clock_var = -1;
5913 /* We need queue and ready lists and clock_var be initialized
5914 in try_ready () (which is called through init_ready_list ()). */
5915 (*current_sched_info->init_ready_list) ();
5917 if (sched_pressure == SCHED_PRESSURE_MODEL)
5918 model_start_schedule ();
5920 /* The algorithm is O(n^2) in the number of ready insns at any given
5921 time in the worst case. Before reload we are more likely to have
5922 big lists so truncate them to a reasonable size. */
5923 if (!reload_completed
5924 && ready.n_ready - ready.n_debug > MAX_SCHED_READY_INSNS)
5926 ready_sort (&ready);
5928 /* Find first free-standing insn past MAX_SCHED_READY_INSNS.
5929 If there are debug insns, we know they're first. */
5930 for (i = MAX_SCHED_READY_INSNS + ready.n_debug; i < ready.n_ready; i++)
5931 if (!SCHED_GROUP_P (ready_element (&ready, i)))
5932 break;
5934 if (sched_verbose >= 2)
5936 fprintf (sched_dump,
5937 ";;\t\tReady list on entry: %d insns\n", ready.n_ready);
5938 fprintf (sched_dump,
5939 ";;\t\t before reload => truncated to %d insns\n", i);
5942 /* Delay all insns past it for 1 cycle. If debug counter is
5943 activated make an exception for the insn right after
5944 nonscheduled_insns_begin. */
5946 rtx skip_insn;
5948 if (dbg_cnt (sched_insn) == false)
5949 skip_insn = next_nonnote_insn (nonscheduled_insns_begin);
5950 else
5951 skip_insn = NULL_RTX;
5953 while (i < ready.n_ready)
5955 rtx insn;
5957 insn = ready_remove (&ready, i);
5959 if (insn != skip_insn)
5960 queue_insn (insn, 1, "list truncated");
5962 if (skip_insn)
5963 ready_add (&ready, skip_insn, true);
5967 /* Now we can restore basic block notes and maintain precise cfg. */
5968 restore_bb_notes (*target_bb);
5970 last_clock_var = -1;
5972 advance = 0;
5974 gcc_assert (VEC_length (rtx, scheduled_insns) == 0);
5975 sort_p = TRUE;
5976 must_backtrack = false;
5977 modulo_insns_scheduled = 0;
5979 ls.modulo_epilogue = false;
5981 /* Loop until all the insns in BB are scheduled. */
5982 while ((*current_sched_info->schedule_more_p) ())
5984 perform_replacements_new_cycle ();
5987 start_clock_var = clock_var;
5989 clock_var++;
5991 advance_one_cycle ();
5993 /* Add to the ready list all pending insns that can be issued now.
5994 If there are no ready insns, increment clock until one
5995 is ready and add all pending insns at that point to the ready
5996 list. */
5997 queue_to_ready (&ready);
5999 gcc_assert (ready.n_ready);
6001 if (sched_verbose >= 2)
6003 fprintf (sched_dump, ";;\t\tReady list after queue_to_ready: ");
6004 debug_ready_list (&ready);
6006 advance -= clock_var - start_clock_var;
6008 while (advance > 0);
6010 if (ls.modulo_epilogue)
6012 int stage = clock_var / modulo_ii;
6013 if (stage > modulo_last_stage * 2 + 2)
6015 if (sched_verbose >= 2)
6016 fprintf (sched_dump,
6017 ";;\t\tmodulo scheduled succeeded at II %d\n",
6018 modulo_ii);
6019 success = true;
6020 goto end_schedule;
6023 else if (modulo_ii > 0)
6025 int stage = clock_var / modulo_ii;
6026 if (stage > modulo_max_stages)
6028 if (sched_verbose >= 2)
6029 fprintf (sched_dump,
6030 ";;\t\tfailing schedule due to excessive stages\n");
6031 goto end_schedule;
6033 if (modulo_n_insns == modulo_insns_scheduled
6034 && stage > modulo_last_stage)
6036 if (sched_verbose >= 2)
6037 fprintf (sched_dump,
6038 ";;\t\tfound kernel after %d stages, II %d\n",
6039 stage, modulo_ii);
6040 ls.modulo_epilogue = true;
6044 prune_ready_list (temp_state, true, false, ls.modulo_epilogue);
6045 if (ready.n_ready == 0)
6046 continue;
6047 if (must_backtrack)
6048 goto do_backtrack;
6050 ls.first_cycle_insn_p = true;
6051 ls.shadows_only_p = false;
6052 cycle_issued_insns = 0;
6053 ls.can_issue_more = issue_rate;
6054 for (;;)
6056 rtx insn;
6057 int cost;
6058 bool asm_p;
6060 if (sort_p && ready.n_ready > 0)
6062 /* Sort the ready list based on priority. This must be
6063 done every iteration through the loop, as schedule_insn
6064 may have readied additional insns that will not be
6065 sorted correctly. */
6066 ready_sort (&ready);
6068 if (sched_verbose >= 2)
6070 fprintf (sched_dump, ";;\t\tReady list after ready_sort: ");
6071 debug_ready_list (&ready);
6075 /* We don't want md sched reorder to even see debug isns, so put
6076 them out right away. */
6077 if (ready.n_ready && DEBUG_INSN_P (ready_element (&ready, 0))
6078 && (*current_sched_info->schedule_more_p) ())
6080 while (ready.n_ready && DEBUG_INSN_P (ready_element (&ready, 0)))
6082 rtx insn = ready_remove_first (&ready);
6083 gcc_assert (DEBUG_INSN_P (insn));
6084 (*current_sched_info->begin_schedule_ready) (insn);
6085 VEC_safe_push (rtx, heap, scheduled_insns, insn);
6086 last_scheduled_insn = insn;
6087 advance = schedule_insn (insn);
6088 gcc_assert (advance == 0);
6089 if (ready.n_ready > 0)
6090 ready_sort (&ready);
6094 if (ls.first_cycle_insn_p && !ready.n_ready)
6095 break;
6097 resume_after_backtrack:
6098 /* Allow the target to reorder the list, typically for
6099 better instruction bundling. */
6100 if (sort_p
6101 && (ready.n_ready == 0
6102 || !SCHED_GROUP_P (ready_element (&ready, 0))))
6104 if (ls.first_cycle_insn_p && targetm.sched.reorder)
6105 ls.can_issue_more
6106 = targetm.sched.reorder (sched_dump, sched_verbose,
6107 ready_lastpos (&ready),
6108 &ready.n_ready, clock_var);
6109 else if (!ls.first_cycle_insn_p && targetm.sched.reorder2)
6110 ls.can_issue_more
6111 = targetm.sched.reorder2 (sched_dump, sched_verbose,
6112 ready.n_ready
6113 ? ready_lastpos (&ready) : NULL,
6114 &ready.n_ready, clock_var);
6117 restart_choose_ready:
6118 if (sched_verbose >= 2)
6120 fprintf (sched_dump, ";;\tReady list (t = %3d): ",
6121 clock_var);
6122 debug_ready_list (&ready);
6123 if (sched_pressure == SCHED_PRESSURE_WEIGHTED)
6124 print_curr_reg_pressure ();
6127 if (ready.n_ready == 0
6128 && ls.can_issue_more
6129 && reload_completed)
6131 /* Allow scheduling insns directly from the queue in case
6132 there's nothing better to do (ready list is empty) but
6133 there are still vacant dispatch slots in the current cycle. */
6134 if (sched_verbose >= 6)
6135 fprintf (sched_dump,";;\t\tSecond chance\n");
6136 memcpy (temp_state, curr_state, dfa_state_size);
6137 if (early_queue_to_ready (temp_state, &ready))
6138 ready_sort (&ready);
6141 if (ready.n_ready == 0
6142 || !ls.can_issue_more
6143 || state_dead_lock_p (curr_state)
6144 || !(*current_sched_info->schedule_more_p) ())
6145 break;
6147 /* Select and remove the insn from the ready list. */
6148 if (sort_p)
6150 int res;
6152 insn = NULL_RTX;
6153 res = choose_ready (&ready, ls.first_cycle_insn_p, &insn);
6155 if (res < 0)
6156 /* Finish cycle. */
6157 break;
6158 if (res > 0)
6159 goto restart_choose_ready;
6161 gcc_assert (insn != NULL_RTX);
6163 else
6164 insn = ready_remove_first (&ready);
6166 if (sched_pressure != SCHED_PRESSURE_NONE
6167 && INSN_TICK (insn) > clock_var)
6169 ready_add (&ready, insn, true);
6170 advance = 1;
6171 break;
6174 if (targetm.sched.dfa_new_cycle
6175 && targetm.sched.dfa_new_cycle (sched_dump, sched_verbose,
6176 insn, last_clock_var,
6177 clock_var, &sort_p))
6178 /* SORT_P is used by the target to override sorting
6179 of the ready list. This is needed when the target
6180 has modified its internal structures expecting that
6181 the insn will be issued next. As we need the insn
6182 to have the highest priority (so it will be returned by
6183 the ready_remove_first call above), we invoke
6184 ready_add (&ready, insn, true).
6185 But, still, there is one issue: INSN can be later
6186 discarded by scheduler's front end through
6187 current_sched_info->can_schedule_ready_p, hence, won't
6188 be issued next. */
6190 ready_add (&ready, insn, true);
6191 break;
6194 sort_p = TRUE;
6196 if (current_sched_info->can_schedule_ready_p
6197 && ! (*current_sched_info->can_schedule_ready_p) (insn))
6198 /* We normally get here only if we don't want to move
6199 insn from the split block. */
6201 TODO_SPEC (insn) = DEP_POSTPONED;
6202 goto restart_choose_ready;
6205 if (delay_htab)
6207 /* If this insn is the first part of a delay-slot pair, record a
6208 backtrack point. */
6209 struct delay_pair *delay_entry;
6210 delay_entry
6211 = (struct delay_pair *)htab_find_with_hash (delay_htab, insn,
6212 htab_hash_pointer (insn));
6213 if (delay_entry)
6215 save_backtrack_point (delay_entry, ls);
6216 if (sched_verbose >= 2)
6217 fprintf (sched_dump, ";;\t\tsaving backtrack point\n");
6221 /* DECISION is made. */
6223 if (modulo_ii > 0 && INSN_UID (insn) < modulo_iter0_max_uid)
6225 modulo_insns_scheduled++;
6226 modulo_last_stage = clock_var / modulo_ii;
6228 if (TODO_SPEC (insn) & SPECULATIVE)
6229 generate_recovery_code (insn);
6231 if (targetm.sched.dispatch (NULL_RTX, IS_DISPATCH_ON))
6232 targetm.sched.dispatch_do (insn, ADD_TO_DISPATCH_WINDOW);
6234 /* Update counters, etc in the scheduler's front end. */
6235 (*current_sched_info->begin_schedule_ready) (insn);
6236 VEC_safe_push (rtx, heap, scheduled_insns, insn);
6237 gcc_assert (NONDEBUG_INSN_P (insn));
6238 last_nondebug_scheduled_insn = last_scheduled_insn = insn;
6240 if (recog_memoized (insn) >= 0)
6242 memcpy (temp_state, curr_state, dfa_state_size);
6243 cost = state_transition (curr_state, insn);
6244 if (sched_pressure != SCHED_PRESSURE_WEIGHTED)
6245 gcc_assert (cost < 0);
6246 if (memcmp (temp_state, curr_state, dfa_state_size) != 0)
6247 cycle_issued_insns++;
6248 asm_p = false;
6250 else
6251 asm_p = (GET_CODE (PATTERN (insn)) == ASM_INPUT
6252 || asm_noperands (PATTERN (insn)) >= 0);
6254 if (targetm.sched.variable_issue)
6255 ls.can_issue_more =
6256 targetm.sched.variable_issue (sched_dump, sched_verbose,
6257 insn, ls.can_issue_more);
6258 /* A naked CLOBBER or USE generates no instruction, so do
6259 not count them against the issue rate. */
6260 else if (GET_CODE (PATTERN (insn)) != USE
6261 && GET_CODE (PATTERN (insn)) != CLOBBER)
6262 ls.can_issue_more--;
6263 advance = schedule_insn (insn);
6265 if (SHADOW_P (insn))
6266 ls.shadows_only_p = true;
6268 /* After issuing an asm insn we should start a new cycle. */
6269 if (advance == 0 && asm_p)
6270 advance = 1;
6272 if (must_backtrack)
6273 break;
6275 if (advance != 0)
6276 break;
6278 ls.first_cycle_insn_p = false;
6279 if (ready.n_ready > 0)
6280 prune_ready_list (temp_state, false, ls.shadows_only_p,
6281 ls.modulo_epilogue);
6284 do_backtrack:
6285 if (!must_backtrack)
6286 for (i = 0; i < ready.n_ready; i++)
6288 rtx insn = ready_element (&ready, i);
6289 if (INSN_EXACT_TICK (insn) == clock_var)
6291 must_backtrack = true;
6292 clock_var++;
6293 break;
6296 if (must_backtrack && modulo_ii > 0)
6298 if (modulo_backtracks_left == 0)
6299 goto end_schedule;
6300 modulo_backtracks_left--;
6302 while (must_backtrack)
6304 struct haifa_saved_data *failed;
6305 rtx failed_insn;
6307 must_backtrack = false;
6308 failed = verify_shadows ();
6309 gcc_assert (failed);
6311 failed_insn = failed->delay_pair->i1;
6312 /* Clear these queues. */
6313 perform_replacements_new_cycle ();
6314 toggle_cancelled_flags (false);
6315 unschedule_insns_until (failed_insn);
6316 while (failed != backtrack_queue)
6317 free_topmost_backtrack_point (true);
6318 restore_last_backtrack_point (&ls);
6319 if (sched_verbose >= 2)
6320 fprintf (sched_dump, ";;\t\trewind to cycle %d\n", clock_var);
6321 /* Delay by at least a cycle. This could cause additional
6322 backtracking. */
6323 queue_insn (failed_insn, 1, "backtracked");
6324 advance = 0;
6325 if (must_backtrack)
6326 continue;
6327 if (ready.n_ready > 0)
6328 goto resume_after_backtrack;
6329 else
6331 if (clock_var == 0 && ls.first_cycle_insn_p)
6332 goto end_schedule;
6333 advance = 1;
6334 break;
6338 if (ls.modulo_epilogue)
6339 success = true;
6340 end_schedule:
6341 advance_one_cycle ();
6342 perform_replacements_new_cycle ();
6343 if (modulo_ii > 0)
6345 /* Once again, debug insn suckiness: they can be on the ready list
6346 even if they have unresolved dependencies. To make our view
6347 of the world consistent, remove such "ready" insns. */
6348 restart_debug_insn_loop:
6349 for (i = ready.n_ready - 1; i >= 0; i--)
6351 rtx x;
6353 x = ready_element (&ready, i);
6354 if (DEPS_LIST_FIRST (INSN_HARD_BACK_DEPS (x)) != NULL
6355 || DEPS_LIST_FIRST (INSN_SPEC_BACK_DEPS (x)) != NULL)
6357 ready_remove (&ready, i);
6358 goto restart_debug_insn_loop;
6361 for (i = ready.n_ready - 1; i >= 0; i--)
6363 rtx x;
6365 x = ready_element (&ready, i);
6366 resolve_dependencies (x);
6368 for (i = 0; i <= max_insn_queue_index; i++)
6370 rtx link;
6371 while ((link = insn_queue[i]) != NULL)
6373 rtx x = XEXP (link, 0);
6374 insn_queue[i] = XEXP (link, 1);
6375 QUEUE_INDEX (x) = QUEUE_NOWHERE;
6376 free_INSN_LIST_node (link);
6377 resolve_dependencies (x);
6382 if (!success)
6383 undo_all_replacements ();
6385 /* Debug info. */
6386 if (sched_verbose)
6388 fprintf (sched_dump, ";;\tReady list (final): ");
6389 debug_ready_list (&ready);
6392 if (modulo_ii == 0 && current_sched_info->queue_must_finish_empty)
6393 /* Sanity check -- queue must be empty now. Meaningless if region has
6394 multiple bbs. */
6395 gcc_assert (!q_size && !ready.n_ready && !ready.n_debug);
6396 else if (modulo_ii == 0)
6398 /* We must maintain QUEUE_INDEX between blocks in region. */
6399 for (i = ready.n_ready - 1; i >= 0; i--)
6401 rtx x;
6403 x = ready_element (&ready, i);
6404 QUEUE_INDEX (x) = QUEUE_NOWHERE;
6405 TODO_SPEC (x) = HARD_DEP;
6408 if (q_size)
6409 for (i = 0; i <= max_insn_queue_index; i++)
6411 rtx link;
6412 for (link = insn_queue[i]; link; link = XEXP (link, 1))
6414 rtx x;
6416 x = XEXP (link, 0);
6417 QUEUE_INDEX (x) = QUEUE_NOWHERE;
6418 TODO_SPEC (x) = HARD_DEP;
6420 free_INSN_LIST_list (&insn_queue[i]);
6424 if (sched_pressure == SCHED_PRESSURE_MODEL)
6425 model_end_schedule ();
6427 if (success)
6429 commit_schedule (prev_head, tail, target_bb);
6430 if (sched_verbose)
6431 fprintf (sched_dump, ";; total time = %d\n", clock_var);
6433 else
6434 last_scheduled_insn = tail;
6436 VEC_truncate (rtx, scheduled_insns, 0);
6438 if (!current_sched_info->queue_must_finish_empty
6439 || haifa_recovery_bb_recently_added_p)
6441 /* INSN_TICK (minimum clock tick at which the insn becomes
6442 ready) may be not correct for the insn in the subsequent
6443 blocks of the region. We should use a correct value of
6444 `clock_var' or modify INSN_TICK. It is better to keep
6445 clock_var value equal to 0 at the start of a basic block.
6446 Therefore we modify INSN_TICK here. */
6447 fix_inter_tick (NEXT_INSN (prev_head), last_scheduled_insn);
6450 if (targetm.sched.finish)
6452 targetm.sched.finish (sched_dump, sched_verbose);
6453 /* Target might have added some instructions to the scheduled block
6454 in its md_finish () hook. These new insns don't have any data
6455 initialized and to identify them we extend h_i_d so that they'll
6456 get zero luids. */
6457 sched_extend_luids ();
6460 if (sched_verbose)
6461 fprintf (sched_dump, ";; new head = %d\n;; new tail = %d\n\n",
6462 INSN_UID (head), INSN_UID (tail));
6464 /* Update head/tail boundaries. */
6465 head = NEXT_INSN (prev_head);
6466 tail = last_scheduled_insn;
6468 head = restore_other_notes (head, NULL);
6470 current_sched_info->head = head;
6471 current_sched_info->tail = tail;
6473 free_backtrack_queue ();
6475 return success;
6478 /* Set_priorities: compute priority of each insn in the block. */
6481 set_priorities (rtx head, rtx tail)
6483 rtx insn;
6484 int n_insn;
6485 int sched_max_insns_priority =
6486 current_sched_info->sched_max_insns_priority;
6487 rtx prev_head;
6489 if (head == tail && ! INSN_P (head))
6490 gcc_unreachable ();
6492 n_insn = 0;
6494 prev_head = PREV_INSN (head);
6495 for (insn = tail; insn != prev_head; insn = PREV_INSN (insn))
6497 if (!INSN_P (insn))
6498 continue;
6500 n_insn++;
6501 (void) priority (insn);
6503 gcc_assert (INSN_PRIORITY_KNOWN (insn));
6505 sched_max_insns_priority = MAX (sched_max_insns_priority,
6506 INSN_PRIORITY (insn));
6509 current_sched_info->sched_max_insns_priority = sched_max_insns_priority;
6511 return n_insn;
6514 /* Set dump and sched_verbose for the desired debugging output. If no
6515 dump-file was specified, but -fsched-verbose=N (any N), print to stderr.
6516 For -fsched-verbose=N, N>=10, print everything to stderr. */
6517 void
6518 setup_sched_dump (void)
6520 sched_verbose = sched_verbose_param;
6521 if (sched_verbose_param == 0 && dump_file)
6522 sched_verbose = 1;
6523 sched_dump = ((sched_verbose_param >= 10 || !dump_file)
6524 ? stderr : dump_file);
6527 /* Initialize some global state for the scheduler. This function works
6528 with the common data shared between all the schedulers. It is called
6529 from the scheduler specific initialization routine. */
6531 void
6532 sched_init (void)
6534 /* Disable speculative loads in their presence if cc0 defined. */
6535 #ifdef HAVE_cc0
6536 flag_schedule_speculative_load = 0;
6537 #endif
6539 if (targetm.sched.dispatch (NULL_RTX, IS_DISPATCH_ON))
6540 targetm.sched.dispatch_do (NULL_RTX, DISPATCH_INIT);
6542 if (flag_sched_pressure
6543 && !reload_completed
6544 && common_sched_info->sched_pass_id == SCHED_RGN_PASS)
6545 sched_pressure = ((enum sched_pressure_algorithm)
6546 PARAM_VALUE (PARAM_SCHED_PRESSURE_ALGORITHM));
6547 else
6548 sched_pressure = SCHED_PRESSURE_NONE;
6550 if (sched_pressure != SCHED_PRESSURE_NONE)
6551 ira_setup_eliminable_regset (false);
6553 /* Initialize SPEC_INFO. */
6554 if (targetm.sched.set_sched_flags)
6556 spec_info = &spec_info_var;
6557 targetm.sched.set_sched_flags (spec_info);
6559 if (spec_info->mask != 0)
6561 spec_info->data_weakness_cutoff =
6562 (PARAM_VALUE (PARAM_SCHED_SPEC_PROB_CUTOFF) * MAX_DEP_WEAK) / 100;
6563 spec_info->control_weakness_cutoff =
6564 (PARAM_VALUE (PARAM_SCHED_SPEC_PROB_CUTOFF)
6565 * REG_BR_PROB_BASE) / 100;
6567 else
6568 /* So we won't read anything accidentally. */
6569 spec_info = NULL;
6572 else
6573 /* So we won't read anything accidentally. */
6574 spec_info = 0;
6576 /* Initialize issue_rate. */
6577 if (targetm.sched.issue_rate)
6578 issue_rate = targetm.sched.issue_rate ();
6579 else
6580 issue_rate = 1;
6582 if (cached_issue_rate != issue_rate)
6584 cached_issue_rate = issue_rate;
6585 /* To invalidate max_lookahead_tries: */
6586 cached_first_cycle_multipass_dfa_lookahead = 0;
6589 if (targetm.sched.first_cycle_multipass_dfa_lookahead)
6590 dfa_lookahead = targetm.sched.first_cycle_multipass_dfa_lookahead ();
6591 else
6592 dfa_lookahead = 0;
6594 if (targetm.sched.init_dfa_pre_cycle_insn)
6595 targetm.sched.init_dfa_pre_cycle_insn ();
6597 if (targetm.sched.init_dfa_post_cycle_insn)
6598 targetm.sched.init_dfa_post_cycle_insn ();
6600 dfa_start ();
6601 dfa_state_size = state_size ();
6603 init_alias_analysis ();
6605 if (!sched_no_dce)
6606 df_set_flags (DF_LR_RUN_DCE);
6607 df_note_add_problem ();
6609 /* More problems needed for interloop dep calculation in SMS. */
6610 if (common_sched_info->sched_pass_id == SCHED_SMS_PASS)
6612 df_rd_add_problem ();
6613 df_chain_add_problem (DF_DU_CHAIN + DF_UD_CHAIN);
6616 df_analyze ();
6618 /* Do not run DCE after reload, as this can kill nops inserted
6619 by bundling. */
6620 if (reload_completed)
6621 df_clear_flags (DF_LR_RUN_DCE);
6623 regstat_compute_calls_crossed ();
6625 if (targetm.sched.init_global)
6626 targetm.sched.init_global (sched_dump, sched_verbose, get_max_uid () + 1);
6628 if (sched_pressure != SCHED_PRESSURE_NONE)
6630 int i, max_regno = max_reg_num ();
6632 if (sched_dump != NULL)
6633 /* We need info about pseudos for rtl dumps about pseudo
6634 classes and costs. */
6635 regstat_init_n_sets_and_refs ();
6636 ira_set_pseudo_classes (true, sched_verbose ? sched_dump : NULL);
6637 sched_regno_pressure_class
6638 = (enum reg_class *) xmalloc (max_regno * sizeof (enum reg_class));
6639 for (i = 0; i < max_regno; i++)
6640 sched_regno_pressure_class[i]
6641 = (i < FIRST_PSEUDO_REGISTER
6642 ? ira_pressure_class_translate[REGNO_REG_CLASS (i)]
6643 : ira_pressure_class_translate[reg_allocno_class (i)]);
6644 curr_reg_live = BITMAP_ALLOC (NULL);
6645 if (sched_pressure == SCHED_PRESSURE_WEIGHTED)
6647 saved_reg_live = BITMAP_ALLOC (NULL);
6648 region_ref_regs = BITMAP_ALLOC (NULL);
6652 curr_state = xmalloc (dfa_state_size);
6655 static void haifa_init_only_bb (basic_block, basic_block);
6657 /* Initialize data structures specific to the Haifa scheduler. */
6658 void
6659 haifa_sched_init (void)
6661 setup_sched_dump ();
6662 sched_init ();
6664 scheduled_insns = VEC_alloc (rtx, heap, 0);
6666 if (spec_info != NULL)
6668 sched_deps_info->use_deps_list = 1;
6669 sched_deps_info->generate_spec_deps = 1;
6672 /* Initialize luids, dependency caches, target and h_i_d for the
6673 whole function. */
6675 bb_vec_t bbs = VEC_alloc (basic_block, heap, n_basic_blocks);
6676 basic_block bb;
6678 sched_init_bbs ();
6680 FOR_EACH_BB (bb)
6681 VEC_quick_push (basic_block, bbs, bb);
6682 sched_init_luids (bbs);
6683 sched_deps_init (true);
6684 sched_extend_target ();
6685 haifa_init_h_i_d (bbs);
6687 VEC_free (basic_block, heap, bbs);
6690 sched_init_only_bb = haifa_init_only_bb;
6691 sched_split_block = sched_split_block_1;
6692 sched_create_empty_bb = sched_create_empty_bb_1;
6693 haifa_recovery_bb_ever_added_p = false;
6695 nr_begin_data = nr_begin_control = nr_be_in_data = nr_be_in_control = 0;
6696 before_recovery = 0;
6697 after_recovery = 0;
6699 modulo_ii = 0;
6702 /* Finish work with the data specific to the Haifa scheduler. */
6703 void
6704 haifa_sched_finish (void)
6706 sched_create_empty_bb = NULL;
6707 sched_split_block = NULL;
6708 sched_init_only_bb = NULL;
6710 if (spec_info && spec_info->dump)
6712 char c = reload_completed ? 'a' : 'b';
6714 fprintf (spec_info->dump,
6715 ";; %s:\n", current_function_name ());
6717 fprintf (spec_info->dump,
6718 ";; Procedure %cr-begin-data-spec motions == %d\n",
6719 c, nr_begin_data);
6720 fprintf (spec_info->dump,
6721 ";; Procedure %cr-be-in-data-spec motions == %d\n",
6722 c, nr_be_in_data);
6723 fprintf (spec_info->dump,
6724 ";; Procedure %cr-begin-control-spec motions == %d\n",
6725 c, nr_begin_control);
6726 fprintf (spec_info->dump,
6727 ";; Procedure %cr-be-in-control-spec motions == %d\n",
6728 c, nr_be_in_control);
6731 VEC_free (rtx, heap, scheduled_insns);
6733 /* Finalize h_i_d, dependency caches, and luids for the whole
6734 function. Target will be finalized in md_global_finish (). */
6735 sched_deps_finish ();
6736 sched_finish_luids ();
6737 current_sched_info = NULL;
6738 sched_finish ();
6741 /* Free global data used during insn scheduling. This function works with
6742 the common data shared between the schedulers. */
6744 void
6745 sched_finish (void)
6747 haifa_finish_h_i_d ();
6748 if (sched_pressure != SCHED_PRESSURE_NONE)
6750 if (regstat_n_sets_and_refs != NULL)
6751 regstat_free_n_sets_and_refs ();
6752 if (sched_pressure == SCHED_PRESSURE_WEIGHTED)
6754 BITMAP_FREE (region_ref_regs);
6755 BITMAP_FREE (saved_reg_live);
6757 BITMAP_FREE (curr_reg_live);
6758 free (sched_regno_pressure_class);
6760 free (curr_state);
6762 if (targetm.sched.finish_global)
6763 targetm.sched.finish_global (sched_dump, sched_verbose);
6765 end_alias_analysis ();
6767 regstat_free_calls_crossed ();
6769 dfa_finish ();
6772 /* Free all delay_pair structures that were recorded. */
6773 void
6774 free_delay_pairs (void)
6776 if (delay_htab)
6778 htab_empty (delay_htab);
6779 htab_empty (delay_htab_i2);
6783 /* Fix INSN_TICKs of the instructions in the current block as well as
6784 INSN_TICKs of their dependents.
6785 HEAD and TAIL are the begin and the end of the current scheduled block. */
6786 static void
6787 fix_inter_tick (rtx head, rtx tail)
6789 /* Set of instructions with corrected INSN_TICK. */
6790 bitmap_head processed;
6791 /* ??? It is doubtful if we should assume that cycle advance happens on
6792 basic block boundaries. Basically insns that are unconditionally ready
6793 on the start of the block are more preferable then those which have
6794 a one cycle dependency over insn from the previous block. */
6795 int next_clock = clock_var + 1;
6797 bitmap_initialize (&processed, 0);
6799 /* Iterates over scheduled instructions and fix their INSN_TICKs and
6800 INSN_TICKs of dependent instructions, so that INSN_TICKs are consistent
6801 across different blocks. */
6802 for (tail = NEXT_INSN (tail); head != tail; head = NEXT_INSN (head))
6804 if (INSN_P (head))
6806 int tick;
6807 sd_iterator_def sd_it;
6808 dep_t dep;
6810 tick = INSN_TICK (head);
6811 gcc_assert (tick >= MIN_TICK);
6813 /* Fix INSN_TICK of instruction from just scheduled block. */
6814 if (bitmap_set_bit (&processed, INSN_LUID (head)))
6816 tick -= next_clock;
6818 if (tick < MIN_TICK)
6819 tick = MIN_TICK;
6821 INSN_TICK (head) = tick;
6824 FOR_EACH_DEP (head, SD_LIST_RES_FORW, sd_it, dep)
6826 rtx next;
6828 next = DEP_CON (dep);
6829 tick = INSN_TICK (next);
6831 if (tick != INVALID_TICK
6832 /* If NEXT has its INSN_TICK calculated, fix it.
6833 If not - it will be properly calculated from
6834 scratch later in fix_tick_ready. */
6835 && bitmap_set_bit (&processed, INSN_LUID (next)))
6837 tick -= next_clock;
6839 if (tick < MIN_TICK)
6840 tick = MIN_TICK;
6842 if (tick > INTER_TICK (next))
6843 INTER_TICK (next) = tick;
6844 else
6845 tick = INTER_TICK (next);
6847 INSN_TICK (next) = tick;
6852 bitmap_clear (&processed);
6855 /* Check if NEXT is ready to be added to the ready or queue list.
6856 If "yes", add it to the proper list.
6857 Returns:
6858 -1 - is not ready yet,
6859 0 - added to the ready list,
6860 0 < N - queued for N cycles. */
6862 try_ready (rtx next)
6864 ds_t old_ts, new_ts;
6866 old_ts = TODO_SPEC (next);
6868 gcc_assert (!(old_ts & ~(SPECULATIVE | HARD_DEP | DEP_CONTROL | DEP_POSTPONED))
6869 && (old_ts == HARD_DEP
6870 || old_ts == DEP_POSTPONED
6871 || (old_ts & SPECULATIVE)
6872 || old_ts == DEP_CONTROL));
6874 new_ts = recompute_todo_spec (next, false);
6876 if (new_ts & (HARD_DEP | DEP_POSTPONED))
6877 gcc_assert (new_ts == old_ts
6878 && QUEUE_INDEX (next) == QUEUE_NOWHERE);
6879 else if (current_sched_info->new_ready)
6880 new_ts = current_sched_info->new_ready (next, new_ts);
6882 /* * if !(old_ts & SPECULATIVE) (e.g. HARD_DEP or 0), then insn might
6883 have its original pattern or changed (speculative) one. This is due
6884 to changing ebb in region scheduling.
6885 * But if (old_ts & SPECULATIVE), then we are pretty sure that insn
6886 has speculative pattern.
6888 We can't assert (!(new_ts & HARD_DEP) || new_ts == old_ts) here because
6889 control-speculative NEXT could have been discarded by sched-rgn.c
6890 (the same case as when discarded by can_schedule_ready_p ()). */
6892 if ((new_ts & SPECULATIVE)
6893 /* If (old_ts == new_ts), then (old_ts & SPECULATIVE) and we don't
6894 need to change anything. */
6895 && new_ts != old_ts)
6897 int res;
6898 rtx new_pat;
6900 gcc_assert ((new_ts & SPECULATIVE) && !(new_ts & ~SPECULATIVE));
6902 res = haifa_speculate_insn (next, new_ts, &new_pat);
6904 switch (res)
6906 case -1:
6907 /* It would be nice to change DEP_STATUS of all dependences,
6908 which have ((DEP_STATUS & SPECULATIVE) == new_ts) to HARD_DEP,
6909 so we won't reanalyze anything. */
6910 new_ts = HARD_DEP;
6911 break;
6913 case 0:
6914 /* We follow the rule, that every speculative insn
6915 has non-null ORIG_PAT. */
6916 if (!ORIG_PAT (next))
6917 ORIG_PAT (next) = PATTERN (next);
6918 break;
6920 case 1:
6921 if (!ORIG_PAT (next))
6922 /* If we gonna to overwrite the original pattern of insn,
6923 save it. */
6924 ORIG_PAT (next) = PATTERN (next);
6926 res = haifa_change_pattern (next, new_pat);
6927 gcc_assert (res);
6928 break;
6930 default:
6931 gcc_unreachable ();
6935 /* We need to restore pattern only if (new_ts == 0), because otherwise it is
6936 either correct (new_ts & SPECULATIVE),
6937 or we simply don't care (new_ts & HARD_DEP). */
6939 gcc_assert (!ORIG_PAT (next)
6940 || !IS_SPECULATION_BRANCHY_CHECK_P (next));
6942 TODO_SPEC (next) = new_ts;
6944 if (new_ts & (HARD_DEP | DEP_POSTPONED))
6946 /* We can't assert (QUEUE_INDEX (next) == QUEUE_NOWHERE) here because
6947 control-speculative NEXT could have been discarded by sched-rgn.c
6948 (the same case as when discarded by can_schedule_ready_p ()). */
6949 /*gcc_assert (QUEUE_INDEX (next) == QUEUE_NOWHERE);*/
6951 change_queue_index (next, QUEUE_NOWHERE);
6953 return -1;
6955 else if (!(new_ts & BEGIN_SPEC)
6956 && ORIG_PAT (next) && PREDICATED_PAT (next) == NULL_RTX
6957 && !IS_SPECULATION_CHECK_P (next))
6958 /* We should change pattern of every previously speculative
6959 instruction - and we determine if NEXT was speculative by using
6960 ORIG_PAT field. Except one case - speculation checks have ORIG_PAT
6961 pat too, so skip them. */
6963 bool success = haifa_change_pattern (next, ORIG_PAT (next));
6964 gcc_assert (success);
6965 ORIG_PAT (next) = 0;
6968 if (sched_verbose >= 2)
6970 fprintf (sched_dump, ";;\t\tdependencies resolved: insn %s",
6971 (*current_sched_info->print_insn) (next, 0));
6973 if (spec_info && spec_info->dump)
6975 if (new_ts & BEGIN_DATA)
6976 fprintf (spec_info->dump, "; data-spec;");
6977 if (new_ts & BEGIN_CONTROL)
6978 fprintf (spec_info->dump, "; control-spec;");
6979 if (new_ts & BE_IN_CONTROL)
6980 fprintf (spec_info->dump, "; in-control-spec;");
6982 if (TODO_SPEC (next) & DEP_CONTROL)
6983 fprintf (sched_dump, " predicated");
6984 fprintf (sched_dump, "\n");
6987 adjust_priority (next);
6989 return fix_tick_ready (next);
6992 /* Calculate INSN_TICK of NEXT and add it to either ready or queue list. */
6993 static int
6994 fix_tick_ready (rtx next)
6996 int tick, delay;
6998 if (!DEBUG_INSN_P (next) && !sd_lists_empty_p (next, SD_LIST_RES_BACK))
7000 int full_p;
7001 sd_iterator_def sd_it;
7002 dep_t dep;
7004 tick = INSN_TICK (next);
7005 /* if tick is not equal to INVALID_TICK, then update
7006 INSN_TICK of NEXT with the most recent resolved dependence
7007 cost. Otherwise, recalculate from scratch. */
7008 full_p = (tick == INVALID_TICK);
7010 FOR_EACH_DEP (next, SD_LIST_RES_BACK, sd_it, dep)
7012 rtx pro = DEP_PRO (dep);
7013 int tick1;
7015 gcc_assert (INSN_TICK (pro) >= MIN_TICK);
7017 tick1 = INSN_TICK (pro) + dep_cost (dep);
7018 if (tick1 > tick)
7019 tick = tick1;
7021 if (!full_p)
7022 break;
7025 else
7026 tick = -1;
7028 INSN_TICK (next) = tick;
7030 delay = tick - clock_var;
7031 if (delay <= 0 || sched_pressure != SCHED_PRESSURE_NONE)
7032 delay = QUEUE_READY;
7034 change_queue_index (next, delay);
7036 return delay;
7039 /* Move NEXT to the proper queue list with (DELAY >= 1),
7040 or add it to the ready list (DELAY == QUEUE_READY),
7041 or remove it from ready and queue lists at all (DELAY == QUEUE_NOWHERE). */
7042 static void
7043 change_queue_index (rtx next, int delay)
7045 int i = QUEUE_INDEX (next);
7047 gcc_assert (QUEUE_NOWHERE <= delay && delay <= max_insn_queue_index
7048 && delay != 0);
7049 gcc_assert (i != QUEUE_SCHEDULED);
7051 if ((delay > 0 && NEXT_Q_AFTER (q_ptr, delay) == i)
7052 || (delay < 0 && delay == i))
7053 /* We have nothing to do. */
7054 return;
7056 /* Remove NEXT from wherever it is now. */
7057 if (i == QUEUE_READY)
7058 ready_remove_insn (next);
7059 else if (i >= 0)
7060 queue_remove (next);
7062 /* Add it to the proper place. */
7063 if (delay == QUEUE_READY)
7064 ready_add (readyp, next, false);
7065 else if (delay >= 1)
7066 queue_insn (next, delay, "change queue index");
7068 if (sched_verbose >= 2)
7070 fprintf (sched_dump, ";;\t\ttick updated: insn %s",
7071 (*current_sched_info->print_insn) (next, 0));
7073 if (delay == QUEUE_READY)
7074 fprintf (sched_dump, " into ready\n");
7075 else if (delay >= 1)
7076 fprintf (sched_dump, " into queue with cost=%d\n", delay);
7077 else
7078 fprintf (sched_dump, " removed from ready or queue lists\n");
7082 static int sched_ready_n_insns = -1;
7084 /* Initialize per region data structures. */
7085 void
7086 sched_extend_ready_list (int new_sched_ready_n_insns)
7088 int i;
7090 if (sched_ready_n_insns == -1)
7091 /* At the first call we need to initialize one more choice_stack
7092 entry. */
7094 i = 0;
7095 sched_ready_n_insns = 0;
7096 VEC_reserve (rtx, heap, scheduled_insns, new_sched_ready_n_insns);
7098 else
7099 i = sched_ready_n_insns + 1;
7101 ready.veclen = new_sched_ready_n_insns + issue_rate;
7102 ready.vec = XRESIZEVEC (rtx, ready.vec, ready.veclen);
7104 gcc_assert (new_sched_ready_n_insns >= sched_ready_n_insns);
7106 ready_try = (char *) xrecalloc (ready_try, new_sched_ready_n_insns,
7107 sched_ready_n_insns, sizeof (*ready_try));
7109 /* We allocate +1 element to save initial state in the choice_stack[0]
7110 entry. */
7111 choice_stack = XRESIZEVEC (struct choice_entry, choice_stack,
7112 new_sched_ready_n_insns + 1);
7114 for (; i <= new_sched_ready_n_insns; i++)
7116 choice_stack[i].state = xmalloc (dfa_state_size);
7118 if (targetm.sched.first_cycle_multipass_init)
7119 targetm.sched.first_cycle_multipass_init (&(choice_stack[i]
7120 .target_data));
7123 sched_ready_n_insns = new_sched_ready_n_insns;
7126 /* Free per region data structures. */
7127 void
7128 sched_finish_ready_list (void)
7130 int i;
7132 free (ready.vec);
7133 ready.vec = NULL;
7134 ready.veclen = 0;
7136 free (ready_try);
7137 ready_try = NULL;
7139 for (i = 0; i <= sched_ready_n_insns; i++)
7141 if (targetm.sched.first_cycle_multipass_fini)
7142 targetm.sched.first_cycle_multipass_fini (&(choice_stack[i]
7143 .target_data));
7145 free (choice_stack [i].state);
7147 free (choice_stack);
7148 choice_stack = NULL;
7150 sched_ready_n_insns = -1;
7153 static int
7154 haifa_luid_for_non_insn (rtx x)
7156 gcc_assert (NOTE_P (x) || LABEL_P (x));
7158 return 0;
7161 /* Generates recovery code for INSN. */
7162 static void
7163 generate_recovery_code (rtx insn)
7165 if (TODO_SPEC (insn) & BEGIN_SPEC)
7166 begin_speculative_block (insn);
7168 /* Here we have insn with no dependencies to
7169 instructions other then CHECK_SPEC ones. */
7171 if (TODO_SPEC (insn) & BE_IN_SPEC)
7172 add_to_speculative_block (insn);
7175 /* Helper function.
7176 Tries to add speculative dependencies of type FS between instructions
7177 in deps_list L and TWIN. */
7178 static void
7179 process_insn_forw_deps_be_in_spec (rtx insn, rtx twin, ds_t fs)
7181 sd_iterator_def sd_it;
7182 dep_t dep;
7184 FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
7186 ds_t ds;
7187 rtx consumer;
7189 consumer = DEP_CON (dep);
7191 ds = DEP_STATUS (dep);
7193 if (/* If we want to create speculative dep. */
7195 /* And we can do that because this is a true dep. */
7196 && (ds & DEP_TYPES) == DEP_TRUE)
7198 gcc_assert (!(ds & BE_IN_SPEC));
7200 if (/* If this dep can be overcome with 'begin speculation'. */
7201 ds & BEGIN_SPEC)
7202 /* Then we have a choice: keep the dep 'begin speculative'
7203 or transform it into 'be in speculative'. */
7205 if (/* In try_ready we assert that if insn once became ready
7206 it can be removed from the ready (or queue) list only
7207 due to backend decision. Hence we can't let the
7208 probability of the speculative dep to decrease. */
7209 ds_weak (ds) <= ds_weak (fs))
7211 ds_t new_ds;
7213 new_ds = (ds & ~BEGIN_SPEC) | fs;
7215 if (/* consumer can 'be in speculative'. */
7216 sched_insn_is_legitimate_for_speculation_p (consumer,
7217 new_ds))
7218 /* Transform it to be in speculative. */
7219 ds = new_ds;
7222 else
7223 /* Mark the dep as 'be in speculative'. */
7224 ds |= fs;
7228 dep_def _new_dep, *new_dep = &_new_dep;
7230 init_dep_1 (new_dep, twin, consumer, DEP_TYPE (dep), ds);
7231 sd_add_dep (new_dep, false);
7236 /* Generates recovery code for BEGIN speculative INSN. */
7237 static void
7238 begin_speculative_block (rtx insn)
7240 if (TODO_SPEC (insn) & BEGIN_DATA)
7241 nr_begin_data++;
7242 if (TODO_SPEC (insn) & BEGIN_CONTROL)
7243 nr_begin_control++;
7245 create_check_block_twin (insn, false);
7247 TODO_SPEC (insn) &= ~BEGIN_SPEC;
7250 static void haifa_init_insn (rtx);
7252 /* Generates recovery code for BE_IN speculative INSN. */
7253 static void
7254 add_to_speculative_block (rtx insn)
7256 ds_t ts;
7257 sd_iterator_def sd_it;
7258 dep_t dep;
7259 rtx twins = NULL;
7260 rtx_vec_t priorities_roots;
7262 ts = TODO_SPEC (insn);
7263 gcc_assert (!(ts & ~BE_IN_SPEC));
7265 if (ts & BE_IN_DATA)
7266 nr_be_in_data++;
7267 if (ts & BE_IN_CONTROL)
7268 nr_be_in_control++;
7270 TODO_SPEC (insn) &= ~BE_IN_SPEC;
7271 gcc_assert (!TODO_SPEC (insn));
7273 DONE_SPEC (insn) |= ts;
7275 /* First we convert all simple checks to branchy. */
7276 for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
7277 sd_iterator_cond (&sd_it, &dep);)
7279 rtx check = DEP_PRO (dep);
7281 if (IS_SPECULATION_SIMPLE_CHECK_P (check))
7283 create_check_block_twin (check, true);
7285 /* Restart search. */
7286 sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
7288 else
7289 /* Continue search. */
7290 sd_iterator_next (&sd_it);
7293 priorities_roots = NULL;
7294 clear_priorities (insn, &priorities_roots);
7296 while (1)
7298 rtx check, twin;
7299 basic_block rec;
7301 /* Get the first backward dependency of INSN. */
7302 sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
7303 if (!sd_iterator_cond (&sd_it, &dep))
7304 /* INSN has no backward dependencies left. */
7305 break;
7307 gcc_assert ((DEP_STATUS (dep) & BEGIN_SPEC) == 0
7308 && (DEP_STATUS (dep) & BE_IN_SPEC) != 0
7309 && (DEP_STATUS (dep) & DEP_TYPES) == DEP_TRUE);
7311 check = DEP_PRO (dep);
7313 gcc_assert (!IS_SPECULATION_CHECK_P (check) && !ORIG_PAT (check)
7314 && QUEUE_INDEX (check) == QUEUE_NOWHERE);
7316 rec = BLOCK_FOR_INSN (check);
7318 twin = emit_insn_before (copy_insn (PATTERN (insn)), BB_END (rec));
7319 haifa_init_insn (twin);
7321 sd_copy_back_deps (twin, insn, true);
7323 if (sched_verbose && spec_info->dump)
7324 /* INSN_BB (insn) isn't determined for twin insns yet.
7325 So we can't use current_sched_info->print_insn. */
7326 fprintf (spec_info->dump, ";;\t\tGenerated twin insn : %d/rec%d\n",
7327 INSN_UID (twin), rec->index);
7329 twins = alloc_INSN_LIST (twin, twins);
7331 /* Add dependences between TWIN and all appropriate
7332 instructions from REC. */
7333 FOR_EACH_DEP (insn, SD_LIST_SPEC_BACK, sd_it, dep)
7335 rtx pro = DEP_PRO (dep);
7337 gcc_assert (DEP_TYPE (dep) == REG_DEP_TRUE);
7339 /* INSN might have dependencies from the instructions from
7340 several recovery blocks. At this iteration we process those
7341 producers that reside in REC. */
7342 if (BLOCK_FOR_INSN (pro) == rec)
7344 dep_def _new_dep, *new_dep = &_new_dep;
7346 init_dep (new_dep, pro, twin, REG_DEP_TRUE);
7347 sd_add_dep (new_dep, false);
7351 process_insn_forw_deps_be_in_spec (insn, twin, ts);
7353 /* Remove all dependencies between INSN and insns in REC. */
7354 for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
7355 sd_iterator_cond (&sd_it, &dep);)
7357 rtx pro = DEP_PRO (dep);
7359 if (BLOCK_FOR_INSN (pro) == rec)
7360 sd_delete_dep (sd_it);
7361 else
7362 sd_iterator_next (&sd_it);
7366 /* We couldn't have added the dependencies between INSN and TWINS earlier
7367 because that would make TWINS appear in the INSN_BACK_DEPS (INSN). */
7368 while (twins)
7370 rtx twin;
7372 twin = XEXP (twins, 0);
7375 dep_def _new_dep, *new_dep = &_new_dep;
7377 init_dep (new_dep, insn, twin, REG_DEP_OUTPUT);
7378 sd_add_dep (new_dep, false);
7381 twin = XEXP (twins, 1);
7382 free_INSN_LIST_node (twins);
7383 twins = twin;
7386 calc_priorities (priorities_roots);
7387 VEC_free (rtx, heap, priorities_roots);
7390 /* Extends and fills with zeros (only the new part) array pointed to by P. */
7391 void *
7392 xrecalloc (void *p, size_t new_nmemb, size_t old_nmemb, size_t size)
7394 gcc_assert (new_nmemb >= old_nmemb);
7395 p = XRESIZEVAR (void, p, new_nmemb * size);
7396 memset (((char *) p) + old_nmemb * size, 0, (new_nmemb - old_nmemb) * size);
7397 return p;
7400 /* Helper function.
7401 Find fallthru edge from PRED. */
7402 edge
7403 find_fallthru_edge_from (basic_block pred)
7405 edge e;
7406 basic_block succ;
7408 succ = pred->next_bb;
7409 gcc_assert (succ->prev_bb == pred);
7411 if (EDGE_COUNT (pred->succs) <= EDGE_COUNT (succ->preds))
7413 e = find_fallthru_edge (pred->succs);
7415 if (e)
7417 gcc_assert (e->dest == succ);
7418 return e;
7421 else
7423 e = find_fallthru_edge (succ->preds);
7425 if (e)
7427 gcc_assert (e->src == pred);
7428 return e;
7432 return NULL;
7435 /* Extend per basic block data structures. */
7436 static void
7437 sched_extend_bb (void)
7439 rtx insn;
7441 /* The following is done to keep current_sched_info->next_tail non null. */
7442 insn = BB_END (EXIT_BLOCK_PTR->prev_bb);
7443 if (NEXT_INSN (insn) == 0
7444 || (!NOTE_P (insn)
7445 && !LABEL_P (insn)
7446 /* Don't emit a NOTE if it would end up before a BARRIER. */
7447 && !BARRIER_P (NEXT_INSN (insn))))
7449 rtx note = emit_note_after (NOTE_INSN_DELETED, insn);
7450 /* Make insn appear outside BB. */
7451 set_block_for_insn (note, NULL);
7452 BB_END (EXIT_BLOCK_PTR->prev_bb) = insn;
7456 /* Init per basic block data structures. */
7457 void
7458 sched_init_bbs (void)
7460 sched_extend_bb ();
7463 /* Initialize BEFORE_RECOVERY variable. */
7464 static void
7465 init_before_recovery (basic_block *before_recovery_ptr)
7467 basic_block last;
7468 edge e;
7470 last = EXIT_BLOCK_PTR->prev_bb;
7471 e = find_fallthru_edge_from (last);
7473 if (e)
7475 /* We create two basic blocks:
7476 1. Single instruction block is inserted right after E->SRC
7477 and has jump to
7478 2. Empty block right before EXIT_BLOCK.
7479 Between these two blocks recovery blocks will be emitted. */
7481 basic_block single, empty;
7482 rtx x, label;
7484 /* If the fallthrough edge to exit we've found is from the block we've
7485 created before, don't do anything more. */
7486 if (last == after_recovery)
7487 return;
7489 adding_bb_to_current_region_p = false;
7491 single = sched_create_empty_bb (last);
7492 empty = sched_create_empty_bb (single);
7494 /* Add new blocks to the root loop. */
7495 if (current_loops != NULL)
7497 add_bb_to_loop (single, VEC_index (loop_p, current_loops->larray, 0));
7498 add_bb_to_loop (empty, VEC_index (loop_p, current_loops->larray, 0));
7501 single->count = last->count;
7502 empty->count = last->count;
7503 single->frequency = last->frequency;
7504 empty->frequency = last->frequency;
7505 BB_COPY_PARTITION (single, last);
7506 BB_COPY_PARTITION (empty, last);
7508 redirect_edge_succ (e, single);
7509 make_single_succ_edge (single, empty, 0);
7510 make_single_succ_edge (empty, EXIT_BLOCK_PTR, EDGE_FALLTHRU);
7512 label = block_label (empty);
7513 x = emit_jump_insn_after (gen_jump (label), BB_END (single));
7514 JUMP_LABEL (x) = label;
7515 LABEL_NUSES (label)++;
7516 haifa_init_insn (x);
7518 emit_barrier_after (x);
7520 sched_init_only_bb (empty, NULL);
7521 sched_init_only_bb (single, NULL);
7522 sched_extend_bb ();
7524 adding_bb_to_current_region_p = true;
7525 before_recovery = single;
7526 after_recovery = empty;
7528 if (before_recovery_ptr)
7529 *before_recovery_ptr = before_recovery;
7531 if (sched_verbose >= 2 && spec_info->dump)
7532 fprintf (spec_info->dump,
7533 ";;\t\tFixed fallthru to EXIT : %d->>%d->%d->>EXIT\n",
7534 last->index, single->index, empty->index);
7536 else
7537 before_recovery = last;
7540 /* Returns new recovery block. */
7541 basic_block
7542 sched_create_recovery_block (basic_block *before_recovery_ptr)
7544 rtx label;
7545 rtx barrier;
7546 basic_block rec;
7548 haifa_recovery_bb_recently_added_p = true;
7549 haifa_recovery_bb_ever_added_p = true;
7551 init_before_recovery (before_recovery_ptr);
7553 barrier = get_last_bb_insn (before_recovery);
7554 gcc_assert (BARRIER_P (barrier));
7556 label = emit_label_after (gen_label_rtx (), barrier);
7558 rec = create_basic_block (label, label, before_recovery);
7560 /* A recovery block always ends with an unconditional jump. */
7561 emit_barrier_after (BB_END (rec));
7563 if (BB_PARTITION (before_recovery) != BB_UNPARTITIONED)
7564 BB_SET_PARTITION (rec, BB_COLD_PARTITION);
7566 if (sched_verbose && spec_info->dump)
7567 fprintf (spec_info->dump, ";;\t\tGenerated recovery block rec%d\n",
7568 rec->index);
7570 return rec;
7573 /* Create edges: FIRST_BB -> REC; FIRST_BB -> SECOND_BB; REC -> SECOND_BB
7574 and emit necessary jumps. */
7575 void
7576 sched_create_recovery_edges (basic_block first_bb, basic_block rec,
7577 basic_block second_bb)
7579 rtx label;
7580 rtx jump;
7581 int edge_flags;
7583 /* This is fixing of incoming edge. */
7584 /* ??? Which other flags should be specified? */
7585 if (BB_PARTITION (first_bb) != BB_PARTITION (rec))
7586 /* Partition type is the same, if it is "unpartitioned". */
7587 edge_flags = EDGE_CROSSING;
7588 else
7589 edge_flags = 0;
7591 make_edge (first_bb, rec, edge_flags);
7592 label = block_label (second_bb);
7593 jump = emit_jump_insn_after (gen_jump (label), BB_END (rec));
7594 JUMP_LABEL (jump) = label;
7595 LABEL_NUSES (label)++;
7597 if (BB_PARTITION (second_bb) != BB_PARTITION (rec))
7598 /* Partition type is the same, if it is "unpartitioned". */
7600 /* Rewritten from cfgrtl.c. */
7601 if (flag_reorder_blocks_and_partition
7602 && targetm_common.have_named_sections)
7604 /* We don't need the same note for the check because
7605 any_condjump_p (check) == true. */
7606 add_reg_note (jump, REG_CROSSING_JUMP, NULL_RTX);
7608 edge_flags = EDGE_CROSSING;
7610 else
7611 edge_flags = 0;
7613 make_single_succ_edge (rec, second_bb, edge_flags);
7614 if (dom_info_available_p (CDI_DOMINATORS))
7615 set_immediate_dominator (CDI_DOMINATORS, rec, first_bb);
7618 /* This function creates recovery code for INSN. If MUTATE_P is nonzero,
7619 INSN is a simple check, that should be converted to branchy one. */
7620 static void
7621 create_check_block_twin (rtx insn, bool mutate_p)
7623 basic_block rec;
7624 rtx label, check, twin;
7625 ds_t fs;
7626 sd_iterator_def sd_it;
7627 dep_t dep;
7628 dep_def _new_dep, *new_dep = &_new_dep;
7629 ds_t todo_spec;
7631 gcc_assert (ORIG_PAT (insn) != NULL_RTX);
7633 if (!mutate_p)
7634 todo_spec = TODO_SPEC (insn);
7635 else
7637 gcc_assert (IS_SPECULATION_SIMPLE_CHECK_P (insn)
7638 && (TODO_SPEC (insn) & SPECULATIVE) == 0);
7640 todo_spec = CHECK_SPEC (insn);
7643 todo_spec &= SPECULATIVE;
7645 /* Create recovery block. */
7646 if (mutate_p || targetm.sched.needs_block_p (todo_spec))
7648 rec = sched_create_recovery_block (NULL);
7649 label = BB_HEAD (rec);
7651 else
7653 rec = EXIT_BLOCK_PTR;
7654 label = NULL_RTX;
7657 /* Emit CHECK. */
7658 check = targetm.sched.gen_spec_check (insn, label, todo_spec);
7660 if (rec != EXIT_BLOCK_PTR)
7662 /* To have mem_reg alive at the beginning of second_bb,
7663 we emit check BEFORE insn, so insn after splitting
7664 insn will be at the beginning of second_bb, which will
7665 provide us with the correct life information. */
7666 check = emit_jump_insn_before (check, insn);
7667 JUMP_LABEL (check) = label;
7668 LABEL_NUSES (label)++;
7670 else
7671 check = emit_insn_before (check, insn);
7673 /* Extend data structures. */
7674 haifa_init_insn (check);
7676 /* CHECK is being added to current region. Extend ready list. */
7677 gcc_assert (sched_ready_n_insns != -1);
7678 sched_extend_ready_list (sched_ready_n_insns + 1);
7680 if (current_sched_info->add_remove_insn)
7681 current_sched_info->add_remove_insn (insn, 0);
7683 RECOVERY_BLOCK (check) = rec;
7685 if (sched_verbose && spec_info->dump)
7686 fprintf (spec_info->dump, ";;\t\tGenerated check insn : %s\n",
7687 (*current_sched_info->print_insn) (check, 0));
7689 gcc_assert (ORIG_PAT (insn));
7691 /* Initialize TWIN (twin is a duplicate of original instruction
7692 in the recovery block). */
7693 if (rec != EXIT_BLOCK_PTR)
7695 sd_iterator_def sd_it;
7696 dep_t dep;
7698 FOR_EACH_DEP (insn, SD_LIST_RES_BACK, sd_it, dep)
7699 if ((DEP_STATUS (dep) & DEP_OUTPUT) != 0)
7701 struct _dep _dep2, *dep2 = &_dep2;
7703 init_dep (dep2, DEP_PRO (dep), check, REG_DEP_TRUE);
7705 sd_add_dep (dep2, true);
7708 twin = emit_insn_after (ORIG_PAT (insn), BB_END (rec));
7709 haifa_init_insn (twin);
7711 if (sched_verbose && spec_info->dump)
7712 /* INSN_BB (insn) isn't determined for twin insns yet.
7713 So we can't use current_sched_info->print_insn. */
7714 fprintf (spec_info->dump, ";;\t\tGenerated twin insn : %d/rec%d\n",
7715 INSN_UID (twin), rec->index);
7717 else
7719 ORIG_PAT (check) = ORIG_PAT (insn);
7720 HAS_INTERNAL_DEP (check) = 1;
7721 twin = check;
7722 /* ??? We probably should change all OUTPUT dependencies to
7723 (TRUE | OUTPUT). */
7726 /* Copy all resolved back dependencies of INSN to TWIN. This will
7727 provide correct value for INSN_TICK (TWIN). */
7728 sd_copy_back_deps (twin, insn, true);
7730 if (rec != EXIT_BLOCK_PTR)
7731 /* In case of branchy check, fix CFG. */
7733 basic_block first_bb, second_bb;
7734 rtx jump;
7736 first_bb = BLOCK_FOR_INSN (check);
7737 second_bb = sched_split_block (first_bb, check);
7739 sched_create_recovery_edges (first_bb, rec, second_bb);
7741 sched_init_only_bb (second_bb, first_bb);
7742 sched_init_only_bb (rec, EXIT_BLOCK_PTR);
7744 jump = BB_END (rec);
7745 haifa_init_insn (jump);
7748 /* Move backward dependences from INSN to CHECK and
7749 move forward dependences from INSN to TWIN. */
7751 /* First, create dependencies between INSN's producers and CHECK & TWIN. */
7752 FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
7754 rtx pro = DEP_PRO (dep);
7755 ds_t ds;
7757 /* If BEGIN_DATA: [insn ~~TRUE~~> producer]:
7758 check --TRUE--> producer ??? or ANTI ???
7759 twin --TRUE--> producer
7760 twin --ANTI--> check
7762 If BEGIN_CONTROL: [insn ~~ANTI~~> producer]:
7763 check --ANTI--> producer
7764 twin --ANTI--> producer
7765 twin --ANTI--> check
7767 If BE_IN_SPEC: [insn ~~TRUE~~> producer]:
7768 check ~~TRUE~~> producer
7769 twin ~~TRUE~~> producer
7770 twin --ANTI--> check */
7772 ds = DEP_STATUS (dep);
7774 if (ds & BEGIN_SPEC)
7776 gcc_assert (!mutate_p);
7777 ds &= ~BEGIN_SPEC;
7780 init_dep_1 (new_dep, pro, check, DEP_TYPE (dep), ds);
7781 sd_add_dep (new_dep, false);
7783 if (rec != EXIT_BLOCK_PTR)
7785 DEP_CON (new_dep) = twin;
7786 sd_add_dep (new_dep, false);
7790 /* Second, remove backward dependencies of INSN. */
7791 for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
7792 sd_iterator_cond (&sd_it, &dep);)
7794 if ((DEP_STATUS (dep) & BEGIN_SPEC)
7795 || mutate_p)
7796 /* We can delete this dep because we overcome it with
7797 BEGIN_SPECULATION. */
7798 sd_delete_dep (sd_it);
7799 else
7800 sd_iterator_next (&sd_it);
7803 /* Future Speculations. Determine what BE_IN speculations will be like. */
7804 fs = 0;
7806 /* Fields (DONE_SPEC (x) & BEGIN_SPEC) and CHECK_SPEC (x) are set only
7807 here. */
7809 gcc_assert (!DONE_SPEC (insn));
7811 if (!mutate_p)
7813 ds_t ts = TODO_SPEC (insn);
7815 DONE_SPEC (insn) = ts & BEGIN_SPEC;
7816 CHECK_SPEC (check) = ts & BEGIN_SPEC;
7818 /* Luckiness of future speculations solely depends upon initial
7819 BEGIN speculation. */
7820 if (ts & BEGIN_DATA)
7821 fs = set_dep_weak (fs, BE_IN_DATA, get_dep_weak (ts, BEGIN_DATA));
7822 if (ts & BEGIN_CONTROL)
7823 fs = set_dep_weak (fs, BE_IN_CONTROL,
7824 get_dep_weak (ts, BEGIN_CONTROL));
7826 else
7827 CHECK_SPEC (check) = CHECK_SPEC (insn);
7829 /* Future speculations: call the helper. */
7830 process_insn_forw_deps_be_in_spec (insn, twin, fs);
7832 if (rec != EXIT_BLOCK_PTR)
7834 /* Which types of dependencies should we use here is,
7835 generally, machine-dependent question... But, for now,
7836 it is not. */
7838 if (!mutate_p)
7840 init_dep (new_dep, insn, check, REG_DEP_TRUE);
7841 sd_add_dep (new_dep, false);
7843 init_dep (new_dep, insn, twin, REG_DEP_OUTPUT);
7844 sd_add_dep (new_dep, false);
7846 else
7848 if (spec_info->dump)
7849 fprintf (spec_info->dump, ";;\t\tRemoved simple check : %s\n",
7850 (*current_sched_info->print_insn) (insn, 0));
7852 /* Remove all dependencies of the INSN. */
7854 sd_it = sd_iterator_start (insn, (SD_LIST_FORW
7855 | SD_LIST_BACK
7856 | SD_LIST_RES_BACK));
7857 while (sd_iterator_cond (&sd_it, &dep))
7858 sd_delete_dep (sd_it);
7861 /* If former check (INSN) already was moved to the ready (or queue)
7862 list, add new check (CHECK) there too. */
7863 if (QUEUE_INDEX (insn) != QUEUE_NOWHERE)
7864 try_ready (check);
7866 /* Remove old check from instruction stream and free its
7867 data. */
7868 sched_remove_insn (insn);
7871 init_dep (new_dep, check, twin, REG_DEP_ANTI);
7872 sd_add_dep (new_dep, false);
7874 else
7876 init_dep_1 (new_dep, insn, check, REG_DEP_TRUE, DEP_TRUE | DEP_OUTPUT);
7877 sd_add_dep (new_dep, false);
7880 if (!mutate_p)
7881 /* Fix priorities. If MUTATE_P is nonzero, this is not necessary,
7882 because it'll be done later in add_to_speculative_block. */
7884 rtx_vec_t priorities_roots = NULL;
7886 clear_priorities (twin, &priorities_roots);
7887 calc_priorities (priorities_roots);
7888 VEC_free (rtx, heap, priorities_roots);
7892 /* Removes dependency between instructions in the recovery block REC
7893 and usual region instructions. It keeps inner dependences so it
7894 won't be necessary to recompute them. */
7895 static void
7896 fix_recovery_deps (basic_block rec)
7898 rtx note, insn, jump, ready_list = 0;
7899 bitmap_head in_ready;
7900 rtx link;
7902 bitmap_initialize (&in_ready, 0);
7904 /* NOTE - a basic block note. */
7905 note = NEXT_INSN (BB_HEAD (rec));
7906 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
7907 insn = BB_END (rec);
7908 gcc_assert (JUMP_P (insn));
7909 insn = PREV_INSN (insn);
7913 sd_iterator_def sd_it;
7914 dep_t dep;
7916 for (sd_it = sd_iterator_start (insn, SD_LIST_FORW);
7917 sd_iterator_cond (&sd_it, &dep);)
7919 rtx consumer = DEP_CON (dep);
7921 if (BLOCK_FOR_INSN (consumer) != rec)
7923 sd_delete_dep (sd_it);
7925 if (bitmap_set_bit (&in_ready, INSN_LUID (consumer)))
7926 ready_list = alloc_INSN_LIST (consumer, ready_list);
7928 else
7930 gcc_assert ((DEP_STATUS (dep) & DEP_TYPES) == DEP_TRUE);
7932 sd_iterator_next (&sd_it);
7936 insn = PREV_INSN (insn);
7938 while (insn != note);
7940 bitmap_clear (&in_ready);
7942 /* Try to add instructions to the ready or queue list. */
7943 for (link = ready_list; link; link = XEXP (link, 1))
7944 try_ready (XEXP (link, 0));
7945 free_INSN_LIST_list (&ready_list);
7947 /* Fixing jump's dependences. */
7948 insn = BB_HEAD (rec);
7949 jump = BB_END (rec);
7951 gcc_assert (LABEL_P (insn));
7952 insn = NEXT_INSN (insn);
7954 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn));
7955 add_jump_dependencies (insn, jump);
7958 /* Change pattern of INSN to NEW_PAT. Invalidate cached haifa
7959 instruction data. */
7960 static bool
7961 haifa_change_pattern (rtx insn, rtx new_pat)
7963 int t;
7965 t = validate_change (insn, &PATTERN (insn), new_pat, 0);
7966 if (!t)
7967 return false;
7969 update_insn_after_change (insn);
7970 return true;
7973 /* -1 - can't speculate,
7974 0 - for speculation with REQUEST mode it is OK to use
7975 current instruction pattern,
7976 1 - need to change pattern for *NEW_PAT to be speculative. */
7978 sched_speculate_insn (rtx insn, ds_t request, rtx *new_pat)
7980 gcc_assert (current_sched_info->flags & DO_SPECULATION
7981 && (request & SPECULATIVE)
7982 && sched_insn_is_legitimate_for_speculation_p (insn, request));
7984 if ((request & spec_info->mask) != request)
7985 return -1;
7987 if (request & BE_IN_SPEC
7988 && !(request & BEGIN_SPEC))
7989 return 0;
7991 return targetm.sched.speculate_insn (insn, request, new_pat);
7994 static int
7995 haifa_speculate_insn (rtx insn, ds_t request, rtx *new_pat)
7997 gcc_assert (sched_deps_info->generate_spec_deps
7998 && !IS_SPECULATION_CHECK_P (insn));
8000 if (HAS_INTERNAL_DEP (insn)
8001 || SCHED_GROUP_P (insn))
8002 return -1;
8004 return sched_speculate_insn (insn, request, new_pat);
8007 /* Print some information about block BB, which starts with HEAD and
8008 ends with TAIL, before scheduling it.
8009 I is zero, if scheduler is about to start with the fresh ebb. */
8010 static void
8011 dump_new_block_header (int i, basic_block bb, rtx head, rtx tail)
8013 if (!i)
8014 fprintf (sched_dump,
8015 ";; ======================================================\n");
8016 else
8017 fprintf (sched_dump,
8018 ";; =====================ADVANCING TO=====================\n");
8019 fprintf (sched_dump,
8020 ";; -- basic block %d from %d to %d -- %s reload\n",
8021 bb->index, INSN_UID (head), INSN_UID (tail),
8022 (reload_completed ? "after" : "before"));
8023 fprintf (sched_dump,
8024 ";; ======================================================\n");
8025 fprintf (sched_dump, "\n");
8028 /* Unlink basic block notes and labels and saves them, so they
8029 can be easily restored. We unlink basic block notes in EBB to
8030 provide back-compatibility with the previous code, as target backends
8031 assume, that there'll be only instructions between
8032 current_sched_info->{head and tail}. We restore these notes as soon
8033 as we can.
8034 FIRST (LAST) is the first (last) basic block in the ebb.
8035 NB: In usual case (FIRST == LAST) nothing is really done. */
8036 void
8037 unlink_bb_notes (basic_block first, basic_block last)
8039 /* We DON'T unlink basic block notes of the first block in the ebb. */
8040 if (first == last)
8041 return;
8043 bb_header = XNEWVEC (rtx, last_basic_block);
8045 /* Make a sentinel. */
8046 if (last->next_bb != EXIT_BLOCK_PTR)
8047 bb_header[last->next_bb->index] = 0;
8049 first = first->next_bb;
8052 rtx prev, label, note, next;
8054 label = BB_HEAD (last);
8055 if (LABEL_P (label))
8056 note = NEXT_INSN (label);
8057 else
8058 note = label;
8059 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
8061 prev = PREV_INSN (label);
8062 next = NEXT_INSN (note);
8063 gcc_assert (prev && next);
8065 NEXT_INSN (prev) = next;
8066 PREV_INSN (next) = prev;
8068 bb_header[last->index] = label;
8070 if (last == first)
8071 break;
8073 last = last->prev_bb;
8075 while (1);
8078 /* Restore basic block notes.
8079 FIRST is the first basic block in the ebb. */
8080 static void
8081 restore_bb_notes (basic_block first)
8083 if (!bb_header)
8084 return;
8086 /* We DON'T unlink basic block notes of the first block in the ebb. */
8087 first = first->next_bb;
8088 /* Remember: FIRST is actually a second basic block in the ebb. */
8090 while (first != EXIT_BLOCK_PTR
8091 && bb_header[first->index])
8093 rtx prev, label, note, next;
8095 label = bb_header[first->index];
8096 prev = PREV_INSN (label);
8097 next = NEXT_INSN (prev);
8099 if (LABEL_P (label))
8100 note = NEXT_INSN (label);
8101 else
8102 note = label;
8103 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
8105 bb_header[first->index] = 0;
8107 NEXT_INSN (prev) = label;
8108 NEXT_INSN (note) = next;
8109 PREV_INSN (next) = note;
8111 first = first->next_bb;
8114 free (bb_header);
8115 bb_header = 0;
8118 /* Helper function.
8119 Fix CFG after both in- and inter-block movement of
8120 control_flow_insn_p JUMP. */
8121 static void
8122 fix_jump_move (rtx jump)
8124 basic_block bb, jump_bb, jump_bb_next;
8126 bb = BLOCK_FOR_INSN (PREV_INSN (jump));
8127 jump_bb = BLOCK_FOR_INSN (jump);
8128 jump_bb_next = jump_bb->next_bb;
8130 gcc_assert (common_sched_info->sched_pass_id == SCHED_EBB_PASS
8131 || IS_SPECULATION_BRANCHY_CHECK_P (jump));
8133 if (!NOTE_INSN_BASIC_BLOCK_P (BB_END (jump_bb_next)))
8134 /* if jump_bb_next is not empty. */
8135 BB_END (jump_bb) = BB_END (jump_bb_next);
8137 if (BB_END (bb) != PREV_INSN (jump))
8138 /* Then there are instruction after jump that should be placed
8139 to jump_bb_next. */
8140 BB_END (jump_bb_next) = BB_END (bb);
8141 else
8142 /* Otherwise jump_bb_next is empty. */
8143 BB_END (jump_bb_next) = NEXT_INSN (BB_HEAD (jump_bb_next));
8145 /* To make assertion in move_insn happy. */
8146 BB_END (bb) = PREV_INSN (jump);
8148 update_bb_for_insn (jump_bb_next);
8151 /* Fix CFG after interblock movement of control_flow_insn_p JUMP. */
8152 static void
8153 move_block_after_check (rtx jump)
8155 basic_block bb, jump_bb, jump_bb_next;
8156 VEC(edge,gc) *t;
8158 bb = BLOCK_FOR_INSN (PREV_INSN (jump));
8159 jump_bb = BLOCK_FOR_INSN (jump);
8160 jump_bb_next = jump_bb->next_bb;
8162 update_bb_for_insn (jump_bb);
8164 gcc_assert (IS_SPECULATION_CHECK_P (jump)
8165 || IS_SPECULATION_CHECK_P (BB_END (jump_bb_next)));
8167 unlink_block (jump_bb_next);
8168 link_block (jump_bb_next, bb);
8170 t = bb->succs;
8171 bb->succs = 0;
8172 move_succs (&(jump_bb->succs), bb);
8173 move_succs (&(jump_bb_next->succs), jump_bb);
8174 move_succs (&t, jump_bb_next);
8176 df_mark_solutions_dirty ();
8178 common_sched_info->fix_recovery_cfg
8179 (bb->index, jump_bb->index, jump_bb_next->index);
8182 /* Helper function for move_block_after_check.
8183 This functions attaches edge vector pointed to by SUCCSP to
8184 block TO. */
8185 static void
8186 move_succs (VEC(edge,gc) **succsp, basic_block to)
8188 edge e;
8189 edge_iterator ei;
8191 gcc_assert (to->succs == 0);
8193 to->succs = *succsp;
8195 FOR_EACH_EDGE (e, ei, to->succs)
8196 e->src = to;
8198 *succsp = 0;
8201 /* Remove INSN from the instruction stream.
8202 INSN should have any dependencies. */
8203 static void
8204 sched_remove_insn (rtx insn)
8206 sd_finish_insn (insn);
8208 change_queue_index (insn, QUEUE_NOWHERE);
8209 current_sched_info->add_remove_insn (insn, 1);
8210 remove_insn (insn);
8213 /* Clear priorities of all instructions, that are forward dependent on INSN.
8214 Store in vector pointed to by ROOTS_PTR insns on which priority () should
8215 be invoked to initialize all cleared priorities. */
8216 static void
8217 clear_priorities (rtx insn, rtx_vec_t *roots_ptr)
8219 sd_iterator_def sd_it;
8220 dep_t dep;
8221 bool insn_is_root_p = true;
8223 gcc_assert (QUEUE_INDEX (insn) != QUEUE_SCHEDULED);
8225 FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
8227 rtx pro = DEP_PRO (dep);
8229 if (INSN_PRIORITY_STATUS (pro) >= 0
8230 && QUEUE_INDEX (insn) != QUEUE_SCHEDULED)
8232 /* If DEP doesn't contribute to priority then INSN itself should
8233 be added to priority roots. */
8234 if (contributes_to_priority_p (dep))
8235 insn_is_root_p = false;
8237 INSN_PRIORITY_STATUS (pro) = -1;
8238 clear_priorities (pro, roots_ptr);
8242 if (insn_is_root_p)
8243 VEC_safe_push (rtx, heap, *roots_ptr, insn);
8246 /* Recompute priorities of instructions, whose priorities might have been
8247 changed. ROOTS is a vector of instructions whose priority computation will
8248 trigger initialization of all cleared priorities. */
8249 static void
8250 calc_priorities (rtx_vec_t roots)
8252 int i;
8253 rtx insn;
8255 FOR_EACH_VEC_ELT (rtx, roots, i, insn)
8256 priority (insn);
8260 /* Add dependences between JUMP and other instructions in the recovery
8261 block. INSN is the first insn the recovery block. */
8262 static void
8263 add_jump_dependencies (rtx insn, rtx jump)
8267 insn = NEXT_INSN (insn);
8268 if (insn == jump)
8269 break;
8271 if (dep_list_size (insn, SD_LIST_FORW) == 0)
8273 dep_def _new_dep, *new_dep = &_new_dep;
8275 init_dep (new_dep, insn, jump, REG_DEP_ANTI);
8276 sd_add_dep (new_dep, false);
8279 while (1);
8281 gcc_assert (!sd_lists_empty_p (jump, SD_LIST_BACK));
8284 /* Extend data structures for logical insn UID. */
8285 void
8286 sched_extend_luids (void)
8288 int new_luids_max_uid = get_max_uid () + 1;
8290 VEC_safe_grow_cleared (int, heap, sched_luids, new_luids_max_uid);
8293 /* Initialize LUID for INSN. */
8294 void
8295 sched_init_insn_luid (rtx insn)
8297 int i = INSN_P (insn) ? 1 : common_sched_info->luid_for_non_insn (insn);
8298 int luid;
8300 if (i >= 0)
8302 luid = sched_max_luid;
8303 sched_max_luid += i;
8305 else
8306 luid = -1;
8308 SET_INSN_LUID (insn, luid);
8311 /* Initialize luids for BBS.
8312 The hook common_sched_info->luid_for_non_insn () is used to determine
8313 if notes, labels, etc. need luids. */
8314 void
8315 sched_init_luids (bb_vec_t bbs)
8317 int i;
8318 basic_block bb;
8320 sched_extend_luids ();
8321 FOR_EACH_VEC_ELT (basic_block, bbs, i, bb)
8323 rtx insn;
8325 FOR_BB_INSNS (bb, insn)
8326 sched_init_insn_luid (insn);
8330 /* Free LUIDs. */
8331 void
8332 sched_finish_luids (void)
8334 VEC_free (int, heap, sched_luids);
8335 sched_max_luid = 1;
8338 /* Return logical uid of INSN. Helpful while debugging. */
8340 insn_luid (rtx insn)
8342 return INSN_LUID (insn);
8345 /* Extend per insn data in the target. */
8346 void
8347 sched_extend_target (void)
8349 if (targetm.sched.h_i_d_extended)
8350 targetm.sched.h_i_d_extended ();
8353 /* Extend global scheduler structures (those, that live across calls to
8354 schedule_block) to include information about just emitted INSN. */
8355 static void
8356 extend_h_i_d (void)
8358 int reserve = (get_max_uid () + 1
8359 - VEC_length (haifa_insn_data_def, h_i_d));
8360 if (reserve > 0
8361 && ! VEC_space (haifa_insn_data_def, h_i_d, reserve))
8363 VEC_safe_grow_cleared (haifa_insn_data_def, heap, h_i_d,
8364 3 * get_max_uid () / 2);
8365 sched_extend_target ();
8369 /* Initialize h_i_d entry of the INSN with default values.
8370 Values, that are not explicitly initialized here, hold zero. */
8371 static void
8372 init_h_i_d (rtx insn)
8374 if (INSN_LUID (insn) > 0)
8376 INSN_COST (insn) = -1;
8377 QUEUE_INDEX (insn) = QUEUE_NOWHERE;
8378 INSN_TICK (insn) = INVALID_TICK;
8379 INSN_EXACT_TICK (insn) = INVALID_TICK;
8380 INTER_TICK (insn) = INVALID_TICK;
8381 TODO_SPEC (insn) = HARD_DEP;
8385 /* Initialize haifa_insn_data for BBS. */
8386 void
8387 haifa_init_h_i_d (bb_vec_t bbs)
8389 int i;
8390 basic_block bb;
8392 extend_h_i_d ();
8393 FOR_EACH_VEC_ELT (basic_block, bbs, i, bb)
8395 rtx insn;
8397 FOR_BB_INSNS (bb, insn)
8398 init_h_i_d (insn);
8402 /* Finalize haifa_insn_data. */
8403 void
8404 haifa_finish_h_i_d (void)
8406 int i;
8407 haifa_insn_data_t data;
8408 struct reg_use_data *use, *next;
8410 FOR_EACH_VEC_ELT (haifa_insn_data_def, h_i_d, i, data)
8412 free (data->max_reg_pressure);
8413 free (data->reg_pressure);
8414 for (use = data->reg_use_list; use != NULL; use = next)
8416 next = use->next_insn_use;
8417 free (use);
8420 VEC_free (haifa_insn_data_def, heap, h_i_d);
8423 /* Init data for the new insn INSN. */
8424 static void
8425 haifa_init_insn (rtx insn)
8427 gcc_assert (insn != NULL);
8429 sched_extend_luids ();
8430 sched_init_insn_luid (insn);
8431 sched_extend_target ();
8432 sched_deps_init (false);
8433 extend_h_i_d ();
8434 init_h_i_d (insn);
8436 if (adding_bb_to_current_region_p)
8438 sd_init_insn (insn);
8440 /* Extend dependency caches by one element. */
8441 extend_dependency_caches (1, false);
8443 if (sched_pressure != SCHED_PRESSURE_NONE)
8444 init_insn_reg_pressure_info (insn);
8447 /* Init data for the new basic block BB which comes after AFTER. */
8448 static void
8449 haifa_init_only_bb (basic_block bb, basic_block after)
8451 gcc_assert (bb != NULL);
8453 sched_init_bbs ();
8455 if (common_sched_info->add_block)
8456 /* This changes only data structures of the front-end. */
8457 common_sched_info->add_block (bb, after);
8460 /* A generic version of sched_split_block (). */
8461 basic_block
8462 sched_split_block_1 (basic_block first_bb, rtx after)
8464 edge e;
8466 e = split_block (first_bb, after);
8467 gcc_assert (e->src == first_bb);
8469 /* sched_split_block emits note if *check == BB_END. Probably it
8470 is better to rip that note off. */
8472 return e->dest;
8475 /* A generic version of sched_create_empty_bb (). */
8476 basic_block
8477 sched_create_empty_bb_1 (basic_block after)
8479 return create_empty_bb (after);
8482 /* Insert PAT as an INSN into the schedule and update the necessary data
8483 structures to account for it. */
8485 sched_emit_insn (rtx pat)
8487 rtx insn = emit_insn_before (pat, nonscheduled_insns_begin);
8488 haifa_init_insn (insn);
8490 if (current_sched_info->add_remove_insn)
8491 current_sched_info->add_remove_insn (insn, 0);
8493 (*current_sched_info->begin_schedule_ready) (insn);
8494 VEC_safe_push (rtx, heap, scheduled_insns, insn);
8496 last_scheduled_insn = insn;
8497 return insn;
8500 /* This function returns a candidate satisfying dispatch constraints from
8501 the ready list. */
8503 static rtx
8504 ready_remove_first_dispatch (struct ready_list *ready)
8506 int i;
8507 rtx insn = ready_element (ready, 0);
8509 if (ready->n_ready == 1
8510 || INSN_CODE (insn) < 0
8511 || !INSN_P (insn)
8512 || !active_insn_p (insn)
8513 || targetm.sched.dispatch (insn, FITS_DISPATCH_WINDOW))
8514 return ready_remove_first (ready);
8516 for (i = 1; i < ready->n_ready; i++)
8518 insn = ready_element (ready, i);
8520 if (INSN_CODE (insn) < 0
8521 || !INSN_P (insn)
8522 || !active_insn_p (insn))
8523 continue;
8525 if (targetm.sched.dispatch (insn, FITS_DISPATCH_WINDOW))
8527 /* Return ith element of ready. */
8528 insn = ready_remove (ready, i);
8529 return insn;
8533 if (targetm.sched.dispatch (NULL_RTX, DISPATCH_VIOLATION))
8534 return ready_remove_first (ready);
8536 for (i = 1; i < ready->n_ready; i++)
8538 insn = ready_element (ready, i);
8540 if (INSN_CODE (insn) < 0
8541 || !INSN_P (insn)
8542 || !active_insn_p (insn))
8543 continue;
8545 /* Return i-th element of ready. */
8546 if (targetm.sched.dispatch (insn, IS_CMP))
8547 return ready_remove (ready, i);
8550 return ready_remove_first (ready);
8553 /* Get number of ready insn in the ready list. */
8556 number_in_ready (void)
8558 return ready.n_ready;
8561 /* Get number of ready's in the ready list. */
8564 get_ready_element (int i)
8566 return ready_element (&ready, i);
8569 #endif /* INSN_SCHEDULING */