1/* Instruction scheduling pass.
2 Copyright (C) 1992-2017 Free Software Foundation, Inc.
3 Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
4 and currently maintained by, Jim Wilson (wilson@cygnus.com)
5
6This file is part of GCC.
7
8GCC is free software; you can redistribute it and/or modify it under
9the terms of the GNU General Public License as published by the Free
10Software Foundation; either version 3, or (at your option) any later
11version.
12
13GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14WARRANTY; without even the implied warranty of MERCHANTABILITY or
15FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16for more details.
17
18You should have received a copy of the GNU General Public License
19along with GCC; see the file COPYING3. If not see
20<http://www.gnu.org/licenses/>. */
21
22/* Instruction scheduling pass. This file, along with sched-deps.c,
23 contains the generic parts. The actual entry point for
24 the normal instruction scheduling pass is found in sched-rgn.c.
25
26 We compute insn priorities based on data dependencies. Flow
27 analysis only creates a fraction of the data-dependencies we must
28 observe: namely, only those dependencies which the combiner can be
29 expected to use. For this pass, we must therefore create the
30 remaining dependencies we need to observe: register dependencies,
31 memory dependencies, dependencies to keep function calls in order,
32 and the dependence between a conditional branch and the setting of
33 condition codes are all dealt with here.
34
35 The scheduler first traverses the data flow graph, starting with
36 the last instruction, and proceeding to the first, assigning values
37 to insn_priority as it goes. This sorts the instructions
38 topologically by data dependence.
39
40 Once priorities have been established, we order the insns using
41 list scheduling. This works as follows: starting with a list of
42 all the ready insns, and sorted according to priority number, we
43 schedule the insn from the end of the list by placing its
44 predecessors in the list according to their priority order. We
45 consider this insn scheduled by setting the pointer to the "end" of
46 the list to point to the previous insn. When an insn has no
47 predecessors, we either queue it until sufficient time has elapsed
48 or add it to the ready list. As the instructions are scheduled or
49 when stalls are introduced, the queue advances and dumps insns into
50 the ready list. When all insns down to the lowest priority have
51 been scheduled, the critical path of the basic block has been made
52 as short as possible. The remaining insns are then scheduled in
53 remaining slots.
54
55 The following list shows the order in which we want to break ties
56 among insns in the ready list:
57
58 1. choose insn with the longest path to end of bb, ties
59 broken by
60 2. choose insn with least contribution to register pressure,
61 ties broken by
62 3. prefer in-block upon interblock motion, ties broken by
63 4. prefer useful upon speculative motion, ties broken by
64 5. choose insn with largest control flow probability, ties
65 broken by
66 6. choose insn with the least dependences upon the previously
67 scheduled insn, or finally
68 7 choose the insn which has the most insns dependent on it.
69 8. choose insn with lowest UID.
70
71 Memory references complicate matters. Only if we can be certain
72 that memory references are not part of the data dependency graph
73 (via true, anti, or output dependence), can we move operations past
74 memory references. To first approximation, reads can be done
75 independently, while writes introduce dependencies. Better
76 approximations will yield fewer dependencies.
77
78 Before reload, an extended analysis of interblock data dependences
79 is required for interblock scheduling. This is performed in
80 compute_block_dependences ().
81
82 Dependencies set up by memory references are treated in exactly the
83 same way as other dependencies, by using insn backward dependences
84 INSN_BACK_DEPS. INSN_BACK_DEPS are translated into forward dependences
85 INSN_FORW_DEPS for the purpose of forward list scheduling.
86
87 Having optimized the critical path, we may have also unduly
88 extended the lifetimes of some registers. If an operation requires
89 that constants be loaded into registers, it is certainly desirable
90 to load those constants as early as necessary, but no earlier.
91 I.e., it will not do to load up a bunch of registers at the
92 beginning of a basic block only to use them at the end, if they
93 could be loaded later, since this may result in excessive register
94 utilization.
95
96 Note that since branches are never in basic blocks, but only end
97 basic blocks, this pass will not move branches. But that is ok,
98 since we can use GNU's delayed branch scheduling pass to take care
99 of this case.
100
101 Also note that no further optimizations based on algebraic
102 identities are performed, so this pass would be a good one to
103 perform instruction splitting, such as breaking up a multiply
104 instruction into shifts and adds where that is profitable.
105
106 Given the memory aliasing analysis that this pass should perform,
107 it should be possible to remove redundant stores to memory, and to
108 load values from registers instead of hitting memory.
109
110 Before reload, speculative insns are moved only if a 'proof' exists
111 that no exception will be caused by this, and if no live registers
112 exist that inhibit the motion (live registers constraints are not
113 represented by data dependence edges).
114
115 This pass must update information that subsequent passes expect to
116 be correct. Namely: reg_n_refs, reg_n_sets, reg_n_deaths,
117 reg_n_calls_crossed, and reg_live_length. Also, BB_HEAD, BB_END.
118
119 The information in the line number notes is carefully retained by
120 this pass. Notes that refer to the starting and ending of
121 exception regions are also carefully retained by this pass. All
122 other NOTE insns are grouped in their same relative order at the
123 beginning of basic blocks and regions that have been scheduled. */
124
125#include "config.h"
126#include "system.h"
127#include "coretypes.h"
128#include "backend.h"
129#include "target.h"
130#include "rtl.h"
131#include "cfghooks.h"
132#include "df.h"
133#include "memmodel.h"
134#include "tm_p.h"
135#include "insn-config.h"
136#include "regs.h"
137#include "ira.h"
138#include "recog.h"
139#include "insn-attr.h"
140#include "cfgrtl.h"
141#include "cfgbuild.h"
142#include "sched-int.h"
143#include "common/common-target.h"
144#include "params.h"
145#include "dbgcnt.h"
146#include "cfgloop.h"
147#include "dumpfile.h"
148#include "print-rtl.h"
149
150#ifdef INSN_SCHEDULING
151
152/* True if we do register pressure relief through live-range
153 shrinkage. */
154static bool live_range_shrinkage_p;
155
156/* Switch on live range shrinkage. */
157void
158initialize_live_range_shrinkage (void)
159{
160 live_range_shrinkage_p = true;
161}
162
163/* Switch off live range shrinkage. */
164void
165finish_live_range_shrinkage (void)
166{
167 live_range_shrinkage_p = false;
168}
169
170/* issue_rate is the number of insns that can be scheduled in the same
171 machine cycle. It can be defined in the config/mach/mach.h file,
172 otherwise we set it to 1. */
173
174int issue_rate;
175
176/* This can be set to true by a backend if the scheduler should not
177 enable a DCE pass. */
178bool sched_no_dce;
179
180/* The current initiation interval used when modulo scheduling. */
181static int modulo_ii;
182
183/* The maximum number of stages we are prepared to handle. */
184static int modulo_max_stages;
185
186/* The number of insns that exist in each iteration of the loop. We use this
187 to detect when we've scheduled all insns from the first iteration. */
188static int modulo_n_insns;
189
190/* The current count of insns in the first iteration of the loop that have
191 already been scheduled. */
192static int modulo_insns_scheduled;
193
194/* The maximum uid of insns from the first iteration of the loop. */
195static int modulo_iter0_max_uid;
196
197/* The number of times we should attempt to backtrack when modulo scheduling.
198 Decreased each time we have to backtrack. */
199static int modulo_backtracks_left;
200
201/* The stage in which the last insn from the original loop was
202 scheduled. */
203static int modulo_last_stage;
204
205/* sched-verbose controls the amount of debugging output the
206 scheduler prints. It is controlled by -fsched-verbose=N:
207 N=0: no debugging output.
208 N=1: default value.
209 N=2: bb's probabilities, detailed ready list info, unit/insn info.
210 N=3: rtl at abort point, control-flow, regions info.
211 N=5: dependences info. */
212int sched_verbose = 0;
213
214/* Debugging file. All printouts are sent to dump. */
215FILE *sched_dump = 0;
216
217/* This is a placeholder for the scheduler parameters common
218 to all schedulers. */
219struct common_sched_info_def *common_sched_info;
220
221#define INSN_TICK(INSN) (HID (INSN)->tick)
222#define INSN_EXACT_TICK(INSN) (HID (INSN)->exact_tick)
223#define INSN_TICK_ESTIMATE(INSN) (HID (INSN)->tick_estimate)
224#define INTER_TICK(INSN) (HID (INSN)->inter_tick)
225#define FEEDS_BACKTRACK_INSN(INSN) (HID (INSN)->feeds_backtrack_insn)
226#define SHADOW_P(INSN) (HID (INSN)->shadow_p)
227#define MUST_RECOMPUTE_SPEC_P(INSN) (HID (INSN)->must_recompute_spec)
228/* Cached cost of the instruction. Use insn_sched_cost to get cost of the
229 insn. -1 here means that the field is not initialized. */
230#define INSN_COST(INSN) (HID (INSN)->cost)
231
232/* If INSN_TICK of an instruction is equal to INVALID_TICK,
233 then it should be recalculated from scratch. */
234#define INVALID_TICK (-(max_insn_queue_index + 1))
235/* The minimal value of the INSN_TICK of an instruction. */
236#define MIN_TICK (-max_insn_queue_index)
237
238/* Original order of insns in the ready list.
239 Used to keep order of normal insns while separating DEBUG_INSNs. */
240#define INSN_RFS_DEBUG_ORIG_ORDER(INSN) (HID (INSN)->rfs_debug_orig_order)
241
242/* The deciding reason for INSN's place in the ready list. */
243#define INSN_LAST_RFS_WIN(INSN) (HID (INSN)->last_rfs_win)
244
245/* List of important notes we must keep around. This is a pointer to the
246 last element in the list. */
247rtx_insn *note_list;
248
249static struct spec_info_def spec_info_var;
250/* Description of the speculative part of the scheduling.
251 If NULL - no speculation. */
252spec_info_t spec_info = NULL;
253
254/* True, if recovery block was added during scheduling of current block.
255 Used to determine, if we need to fix INSN_TICKs. */
256static bool haifa_recovery_bb_recently_added_p;
257
258/* True, if recovery block was added during this scheduling pass.
259 Used to determine if we should have empty memory pools of dependencies
260 after finishing current region. */
261bool haifa_recovery_bb_ever_added_p;
262
263/* Counters of different types of speculative instructions. */
264static int nr_begin_data, nr_be_in_data, nr_begin_control, nr_be_in_control;
265
266/* Array used in {unlink, restore}_bb_notes. */
267static rtx_insn **bb_header = 0;
268
269/* Basic block after which recovery blocks will be created. */
270static basic_block before_recovery;
271
272/* Basic block just before the EXIT_BLOCK and after recovery, if we have
273 created it. */
274basic_block after_recovery;
275
276/* FALSE if we add bb to another region, so we don't need to initialize it. */
277bool adding_bb_to_current_region_p = true;
278
279/* Queues, etc. */
280
281/* An instruction is ready to be scheduled when all insns preceding it
282 have already been scheduled. It is important to ensure that all
283 insns which use its result will not be executed until its result
284 has been computed. An insn is maintained in one of four structures:
285
286 (P) the "Pending" set of insns which cannot be scheduled until
287 their dependencies have been satisfied.
288 (Q) the "Queued" set of insns that can be scheduled when sufficient
289 time has passed.
290 (R) the "Ready" list of unscheduled, uncommitted insns.
291 (S) the "Scheduled" list of insns.
292
293 Initially, all insns are either "Pending" or "Ready" depending on
294 whether their dependencies are satisfied.
295
296 Insns move from the "Ready" list to the "Scheduled" list as they
297 are committed to the schedule. As this occurs, the insns in the
298 "Pending" list have their dependencies satisfied and move to either
299 the "Ready" list or the "Queued" set depending on whether
300 sufficient time has passed to make them ready. As time passes,
301 insns move from the "Queued" set to the "Ready" list.
302
303 The "Pending" list (P) are the insns in the INSN_FORW_DEPS of the
304 unscheduled insns, i.e., those that are ready, queued, and pending.
305 The "Queued" set (Q) is implemented by the variable `insn_queue'.
306 The "Ready" list (R) is implemented by the variables `ready' and
307 `n_ready'.
308 The "Scheduled" list (S) is the new insn chain built by this pass.
309
310 The transition (R->S) is implemented in the scheduling loop in
311 `schedule_block' when the best insn to schedule is chosen.
312 The transitions (P->R and P->Q) are implemented in `schedule_insn' as
313 insns move from the ready list to the scheduled list.
314 The transition (Q->R) is implemented in 'queue_to_insn' as time
315 passes or stalls are introduced. */
316
317/* Implement a circular buffer to delay instructions until sufficient
318 time has passed. For the new pipeline description interface,
319 MAX_INSN_QUEUE_INDEX is a power of two minus one which is not less
320 than maximal time of instruction execution computed by genattr.c on
321 the base maximal time of functional unit reservations and getting a
322 result. This is the longest time an insn may be queued. */
323
324static rtx_insn_list **insn_queue;
325static int q_ptr = 0;
326static int q_size = 0;
327#define NEXT_Q(X) (((X)+1) & max_insn_queue_index)
328#define NEXT_Q_AFTER(X, C) (((X)+C) & max_insn_queue_index)
329
330#define QUEUE_SCHEDULED (-3)
331#define QUEUE_NOWHERE (-2)
332#define QUEUE_READY (-1)
333/* QUEUE_SCHEDULED - INSN is scheduled.
334 QUEUE_NOWHERE - INSN isn't scheduled yet and is neither in
335 queue or ready list.
336 QUEUE_READY - INSN is in ready list.
337 N >= 0 - INSN queued for X [where NEXT_Q_AFTER (q_ptr, X) == N] cycles. */
338
339#define QUEUE_INDEX(INSN) (HID (INSN)->queue_index)
340
341/* The following variable value refers for all current and future
342 reservations of the processor units. */
343state_t curr_state;
344
345/* The following variable value is size of memory representing all
346 current and future reservations of the processor units. */
347size_t dfa_state_size;
348
349/* The following array is used to find the best insn from ready when
350 the automaton pipeline interface is used. */
351signed char *ready_try = NULL;
352
353/* The ready list. */
354struct ready_list ready = {NULL, 0, 0, 0, 0};
355
356/* The pointer to the ready list (to be removed). */
357static struct ready_list *readyp = &ready;
358
359/* Scheduling clock. */
360static int clock_var;
361
362/* Clock at which the previous instruction was issued. */
363static int last_clock_var;
364
365/* Set to true if, when queuing a shadow insn, we discover that it would be
366 scheduled too late. */
367static bool must_backtrack;
368
369/* The following variable value is number of essential insns issued on
370 the current cycle. An insn is essential one if it changes the
371 processors state. */
372int cycle_issued_insns;
373
374/* This records the actual schedule. It is built up during the main phase
375 of schedule_block, and afterwards used to reorder the insns in the RTL. */
376static vec<rtx_insn *> scheduled_insns;
377
378static int may_trap_exp (const_rtx, int);
379
380/* Nonzero iff the address is comprised from at most 1 register. */
381#define CONST_BASED_ADDRESS_P(x) \
382 (REG_P (x) \
383 || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
384 || (GET_CODE (x) == LO_SUM)) \
385 && (CONSTANT_P (XEXP (x, 0)) \
386 || CONSTANT_P (XEXP (x, 1)))))
387
388/* Returns a class that insn with GET_DEST(insn)=x may belong to,
389 as found by analyzing insn's expression. */
390
391
392static int haifa_luid_for_non_insn (rtx x);
393
394/* Haifa version of sched_info hooks common to all headers. */
395const struct common_sched_info_def haifa_common_sched_info =
396 {
397 NULL, /* fix_recovery_cfg */
398 NULL, /* add_block */
399 NULL, /* estimate_number_of_insns */
400 haifa_luid_for_non_insn, /* luid_for_non_insn */
401 SCHED_PASS_UNKNOWN /* sched_pass_id */
402 };
403
404/* Mapping from instruction UID to its Logical UID. */
405vec<int> sched_luids;
406
407/* Next LUID to assign to an instruction. */
408int sched_max_luid = 1;
409
410/* Haifa Instruction Data. */
411vec<haifa_insn_data_def> h_i_d;
412
413void (* sched_init_only_bb) (basic_block, basic_block);
414
415/* Split block function. Different schedulers might use different functions
416 to handle their internal data consistent. */
417basic_block (* sched_split_block) (basic_block, rtx);
418
419/* Create empty basic block after the specified block. */
420basic_block (* sched_create_empty_bb) (basic_block);
421
422/* Return the number of cycles until INSN is expected to be ready.
423 Return zero if it already is. */
424static int
425insn_delay (rtx_insn *insn)
426{
427 return MAX (INSN_TICK (insn) - clock_var, 0);
428}
429
430static int
431may_trap_exp (const_rtx x, int is_store)
432{
433 enum rtx_code code;
434
435 if (x == 0)
436 return TRAP_FREE;
437 code = GET_CODE (x);
438 if (is_store)
439 {
440 if (code == MEM && may_trap_p (x))
441 return TRAP_RISKY;
442 else
443 return TRAP_FREE;
444 }
445 if (code == MEM)
446 {
447 /* The insn uses memory: a volatile load. */
448 if (MEM_VOLATILE_P (x))
449 return IRISKY;
450 /* An exception-free load. */
451 if (!may_trap_p (x))
452 return IFREE;
453 /* A load with 1 base register, to be further checked. */
454 if (CONST_BASED_ADDRESS_P (XEXP (x, 0)))
455 return PFREE_CANDIDATE;
456 /* No info on the load, to be further checked. */
457 return PRISKY_CANDIDATE;
458 }
459 else
460 {
461 const char *fmt;
462 int i, insn_class = TRAP_FREE;
463
464 /* Neither store nor load, check if it may cause a trap. */
465 if (may_trap_p (x))
466 return TRAP_RISKY;
467 /* Recursive step: walk the insn... */
468 fmt = GET_RTX_FORMAT (code);
469 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
470 {
471 if (fmt[i] == 'e')
472 {
473 int tmp_class = may_trap_exp (XEXP (x, i), is_store);
474 insn_class = WORST_CLASS (insn_class, tmp_class);
475 }
476 else if (fmt[i] == 'E')
477 {
478 int j;
479 for (j = 0; j < XVECLEN (x, i); j++)
480 {
481 int tmp_class = may_trap_exp (XVECEXP (x, i, j), is_store);
482 insn_class = WORST_CLASS (insn_class, tmp_class);
483 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
484 break;
485 }
486 }
487 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
488 break;
489 }
490 return insn_class;
491 }
492}
493
494/* Classifies rtx X of an insn for the purpose of verifying that X can be
495 executed speculatively (and consequently the insn can be moved
496 speculatively), by examining X, returning:
497 TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
498 TRAP_FREE: non-load insn.
499 IFREE: load from a globally safe location.
500 IRISKY: volatile load.
501 PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
502 being either PFREE or PRISKY. */
503
504static int
505haifa_classify_rtx (const_rtx x)
506{
507 int tmp_class = TRAP_FREE;
508 int insn_class = TRAP_FREE;
509 enum rtx_code code;
510
511 if (GET_CODE (x) == PARALLEL)
512 {
513 int i, len = XVECLEN (x, 0);
514
515 for (i = len - 1; i >= 0; i--)
516 {
517 tmp_class = haifa_classify_rtx (XVECEXP (x, 0, i));
518 insn_class = WORST_CLASS (insn_class, tmp_class);
519 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
520 break;
521 }
522 }
523 else
524 {
525 code = GET_CODE (x);
526 switch (code)
527 {
528 case CLOBBER:
529 /* Test if it is a 'store'. */
530 tmp_class = may_trap_exp (XEXP (x, 0), 1);
531 break;
532 case SET:
533 /* Test if it is a store. */
534 tmp_class = may_trap_exp (SET_DEST (x), 1);
535 if (tmp_class == TRAP_RISKY)
536 break;
537 /* Test if it is a load. */
538 tmp_class =
539 WORST_CLASS (tmp_class,
540 may_trap_exp (SET_SRC (x), 0));
541 break;
542 case COND_EXEC:
543 tmp_class = haifa_classify_rtx (COND_EXEC_CODE (x));
544 if (tmp_class == TRAP_RISKY)
545 break;
546 tmp_class = WORST_CLASS (tmp_class,
547 may_trap_exp (COND_EXEC_TEST (x), 0));
548 break;
549 case TRAP_IF:
550 tmp_class = TRAP_RISKY;
551 break;
552 default:;
553 }
554 insn_class = tmp_class;
555 }
556
557 return insn_class;
558}
559
560int
561haifa_classify_insn (const_rtx insn)
562{
563 return haifa_classify_rtx (PATTERN (insn));
564}
565
566/* After the scheduler initialization function has been called, this function
567 can be called to enable modulo scheduling. II is the initiation interval
568 we should use, it affects the delays for delay_pairs that were recorded as
569 separated by a given number of stages.
570
571 MAX_STAGES provides us with a limit
572 after which we give up scheduling; the caller must have unrolled at least
573 as many copies of the loop body and recorded delay_pairs for them.
574
575 INSNS is the number of real (non-debug) insns in one iteration of
576 the loop. MAX_UID can be used to test whether an insn belongs to
577 the first iteration of the loop; all of them have a uid lower than
578 MAX_UID. */
579void
580set_modulo_params (int ii, int max_stages, int insns, int max_uid)
581{
582 modulo_ii = ii;
583 modulo_max_stages = max_stages;
584 modulo_n_insns = insns;
585 modulo_iter0_max_uid = max_uid;
586 modulo_backtracks_left = PARAM_VALUE (PARAM_MAX_MODULO_BACKTRACK_ATTEMPTS);
587}
588
589/* A structure to record a pair of insns where the first one is a real
590 insn that has delay slots, and the second is its delayed shadow.
591 I1 is scheduled normally and will emit an assembly instruction,
592 while I2 describes the side effect that takes place at the
593 transition between cycles CYCLES and (CYCLES + 1) after I1. */
594struct delay_pair
595{
596 struct delay_pair *next_same_i1;
597 rtx_insn *i1, *i2;
598 int cycles;
599 /* When doing modulo scheduling, we a delay_pair can also be used to
600 show that I1 and I2 are the same insn in a different stage. If that
601 is the case, STAGES will be nonzero. */
602 int stages;
603};
604
605/* Helpers for delay hashing. */
606
607struct delay_i1_hasher : nofree_ptr_hash <delay_pair>
608{
609 typedef void *compare_type;
610 static inline hashval_t hash (const delay_pair *);
611 static inline bool equal (const delay_pair *, const void *);
612};
613
614/* Returns a hash value for X, based on hashing just I1. */
615
616inline hashval_t
617delay_i1_hasher::hash (const delay_pair *x)
618{
619 return htab_hash_pointer (x->i1);
620}
621
622/* Return true if I1 of pair X is the same as that of pair Y. */
623
624inline bool
625delay_i1_hasher::equal (const delay_pair *x, const void *y)
626{
627 return x->i1 == y;
628}
629
630struct delay_i2_hasher : free_ptr_hash <delay_pair>
631{
632 typedef void *compare_type;
633 static inline hashval_t hash (const delay_pair *);
634 static inline bool equal (const delay_pair *, const void *);
635};
636
637/* Returns a hash value for X, based on hashing just I2. */
638
639inline hashval_t
640delay_i2_hasher::hash (const delay_pair *x)
641{
642 return htab_hash_pointer (x->i2);
643}
644
645/* Return true if I2 of pair X is the same as that of pair Y. */
646
647inline bool
648delay_i2_hasher::equal (const delay_pair *x, const void *y)
649{
650 return x->i2 == y;
651}
652
653/* Two hash tables to record delay_pairs, one indexed by I1 and the other
654 indexed by I2. */
655static hash_table<delay_i1_hasher> *delay_htab;
656static hash_table<delay_i2_hasher> *delay_htab_i2;
657
658/* Called through htab_traverse. Walk the hashtable using I2 as
659 index, and delete all elements involving an UID higher than
660 that pointed to by *DATA. */
661int
662haifa_htab_i2_traverse (delay_pair **slot, int *data)
663{
664 int maxuid = *data;
665 struct delay_pair *p = *slot;
666 if (INSN_UID (p->i2) >= maxuid || INSN_UID (p->i1) >= maxuid)
667 {
668 delay_htab_i2->clear_slot (slot);
669 }
670 return 1;
671}
672
673/* Called through htab_traverse. Walk the hashtable using I2 as
674 index, and delete all elements involving an UID higher than
675 that pointed to by *DATA. */
676int
677haifa_htab_i1_traverse (delay_pair **pslot, int *data)
678{
679 int maxuid = *data;
680 struct delay_pair *p, *first, **pprev;
681
682 if (INSN_UID ((*pslot)->i1) >= maxuid)
683 {
684 delay_htab->clear_slot (pslot);
685 return 1;
686 }
687 pprev = &first;
688 for (p = *pslot; p; p = p->next_same_i1)
689 {
690 if (INSN_UID (p->i2) < maxuid)
691 {
692 *pprev = p;
693 pprev = &p->next_same_i1;
694 }
695 }
696 *pprev = NULL;
697 if (first == NULL)
698 delay_htab->clear_slot (pslot);
699 else
700 *pslot = first;
701 return 1;
702}
703
704/* Discard all delay pairs which involve an insn with an UID higher
705 than MAX_UID. */
706void
707discard_delay_pairs_above (int max_uid)
708{
709 delay_htab->traverse <int *, haifa_htab_i1_traverse> (&max_uid);
710 delay_htab_i2->traverse <int *, haifa_htab_i2_traverse> (&max_uid);
711}
712
713/* This function can be called by a port just before it starts the final
714 scheduling pass. It records the fact that an instruction with delay
715 slots has been split into two insns, I1 and I2. The first one will be
716 scheduled normally and initiates the operation. The second one is a
717 shadow which must follow a specific number of cycles after I1; its only
718 purpose is to show the side effect that occurs at that cycle in the RTL.
719 If a JUMP_INSN or a CALL_INSN has been split, I1 should be a normal INSN,
720 while I2 retains the original insn type.
721
722 There are two ways in which the number of cycles can be specified,
723 involving the CYCLES and STAGES arguments to this function. If STAGES
724 is zero, we just use the value of CYCLES. Otherwise, STAGES is a factor
725 which is multiplied by MODULO_II to give the number of cycles. This is
726 only useful if the caller also calls set_modulo_params to enable modulo
727 scheduling. */
728
729void
730record_delay_slot_pair (rtx_insn *i1, rtx_insn *i2, int cycles, int stages)
731{
732 struct delay_pair *p = XNEW (struct delay_pair);
733 struct delay_pair **slot;
734
735 p->i1 = i1;
736 p->i2 = i2;
737 p->cycles = cycles;
738 p->stages = stages;
739
740 if (!delay_htab)
741 {
742 delay_htab = new hash_table<delay_i1_hasher> (10);
743 delay_htab_i2 = new hash_table<delay_i2_hasher> (10);
744 }
745 slot = delay_htab->find_slot_with_hash (i1, htab_hash_pointer (i1), INSERT);
746 p->next_same_i1 = *slot;
747 *slot = p;
748 slot = delay_htab_i2->find_slot (p, INSERT);
749 *slot = p;
750}
751
752/* Examine the delay pair hashtable to see if INSN is a shadow for another,
753 and return the other insn if so. Return NULL otherwise. */
754rtx_insn *
755real_insn_for_shadow (rtx_insn *insn)
756{
757 struct delay_pair *pair;
758
759 if (!delay_htab)
760 return NULL;
761
762 pair = delay_htab_i2->find_with_hash (insn, htab_hash_pointer (insn));
763 if (!pair || pair->stages > 0)
764 return NULL;
765 return pair->i1;
766}
767
768/* For a pair P of insns, return the fixed distance in cycles from the first
769 insn after which the second must be scheduled. */
770static int
771pair_delay (struct delay_pair *p)
772{
773 if (p->stages == 0)
774 return p->cycles;
775 else
776 return p->stages * modulo_ii;
777}
778
779/* Given an insn INSN, add a dependence on its delayed shadow if it
780 has one. Also try to find situations where shadows depend on each other
781 and add dependencies to the real insns to limit the amount of backtracking
782 needed. */
783void
784add_delay_dependencies (rtx_insn *insn)
785{
786 struct delay_pair *pair;
787 sd_iterator_def sd_it;
788 dep_t dep;
789
790 if (!delay_htab)
791 return;
792
793 pair = delay_htab_i2->find_with_hash (insn, htab_hash_pointer (insn));
794 if (!pair)
795 return;
796 add_dependence (insn, pair->i1, REG_DEP_ANTI);
797 if (pair->stages)
798 return;
799
800 FOR_EACH_DEP (pair->i2, SD_LIST_BACK, sd_it, dep)
801 {
802 rtx_insn *pro = DEP_PRO (dep);
803 struct delay_pair *other_pair
804 = delay_htab_i2->find_with_hash (pro, htab_hash_pointer (pro));
805 if (!other_pair || other_pair->stages)
806 continue;
807 if (pair_delay (other_pair) >= pair_delay (pair))
808 {
809 if (sched_verbose >= 4)
810 {
811 fprintf (sched_dump, ";;\tadding dependence %d <- %d\n",
812 INSN_UID (other_pair->i1),
813 INSN_UID (pair->i1));
814 fprintf (sched_dump, ";;\tpair1 %d <- %d, cost %d\n",
815 INSN_UID (pair->i1),
816 INSN_UID (pair->i2),
817 pair_delay (pair));
818 fprintf (sched_dump, ";;\tpair2 %d <- %d, cost %d\n",
819 INSN_UID (other_pair->i1),
820 INSN_UID (other_pair->i2),
821 pair_delay (other_pair));
822 }
823 add_dependence (pair->i1, other_pair->i1, REG_DEP_ANTI);
824 }
825 }
826}
827
828/* Forward declarations. */
829
830static int priority (rtx_insn *);
831static int autopref_rank_for_schedule (const rtx_insn *, const rtx_insn *);
832static int rank_for_schedule (const void *, const void *);
833static void swap_sort (rtx_insn **, int);
834static void queue_insn (rtx_insn *, int, const char *);
835static int schedule_insn (rtx_insn *);
836static void adjust_priority (rtx_insn *);
837static void advance_one_cycle (void);
838static void extend_h_i_d (void);
839
840
841/* Notes handling mechanism:
842 =========================
843 Generally, NOTES are saved before scheduling and restored after scheduling.
844 The scheduler distinguishes between two types of notes:
845
846 (1) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes:
847 Before scheduling a region, a pointer to the note is added to the insn
848 that follows or precedes it. (This happens as part of the data dependence
849 computation). After scheduling an insn, the pointer contained in it is
850 used for regenerating the corresponding note (in reemit_notes).
851
852 (2) All other notes (e.g. INSN_DELETED): Before scheduling a block,
853 these notes are put in a list (in rm_other_notes() and
854 unlink_other_notes ()). After scheduling the block, these notes are
855 inserted at the beginning of the block (in schedule_block()). */
856
857static void ready_add (struct ready_list *, rtx_insn *, bool);
858static rtx_insn *ready_remove_first (struct ready_list *);
859static rtx_insn *ready_remove_first_dispatch (struct ready_list *ready);
860
861static void queue_to_ready (struct ready_list *);
862static int early_queue_to_ready (state_t, struct ready_list *);
863
864/* The following functions are used to implement multi-pass scheduling
865 on the first cycle. */
866static rtx_insn *ready_remove (struct ready_list *, int);
867static void ready_remove_insn (rtx_insn *);
868
869static void fix_inter_tick (rtx_insn *, rtx_insn *);
870static int fix_tick_ready (rtx_insn *);
871static void change_queue_index (rtx_insn *, int);
872
873/* The following functions are used to implement scheduling of data/control
874 speculative instructions. */
875
876static void extend_h_i_d (void);
877static void init_h_i_d (rtx_insn *);
878static int haifa_speculate_insn (rtx_insn *, ds_t, rtx *);
879static void generate_recovery_code (rtx_insn *);
880static void process_insn_forw_deps_be_in_spec (rtx_insn *, rtx_insn *, ds_t);
881static void begin_speculative_block (rtx_insn *);
882static void add_to_speculative_block (rtx_insn *);
883static void init_before_recovery (basic_block *);
884static void create_check_block_twin (rtx_insn *, bool);
885static void fix_recovery_deps (basic_block);
886static bool haifa_change_pattern (rtx_insn *, rtx);
887static void dump_new_block_header (int, basic_block, rtx_insn *, rtx_insn *);
888static void restore_bb_notes (basic_block);
889static void fix_jump_move (rtx_insn *);
890static void move_block_after_check (rtx_insn *);
891static void move_succs (vec<edge, va_gc> **, basic_block);
892static void sched_remove_insn (rtx_insn *);
893static void clear_priorities (rtx_insn *, rtx_vec_t *);
894static void calc_priorities (rtx_vec_t);
895static void add_jump_dependencies (rtx_insn *, rtx_insn *);
896
897#endif /* INSN_SCHEDULING */
898
899/* Point to state used for the current scheduling pass. */
900struct haifa_sched_info *current_sched_info;
901
902#ifndef INSN_SCHEDULING
903void
904schedule_insns (void)
905{
906}
907#else
908
909/* Do register pressure sensitive insn scheduling if the flag is set
910 up. */
911enum sched_pressure_algorithm sched_pressure;
912
913/* Map regno -> its pressure class. The map defined only when
914 SCHED_PRESSURE != SCHED_PRESSURE_NONE. */
915enum reg_class *sched_regno_pressure_class;
916
917/* The current register pressure. Only elements corresponding pressure
918 classes are defined. */
919static int curr_reg_pressure[N_REG_CLASSES];
920
921/* Saved value of the previous array. */
922static int saved_reg_pressure[N_REG_CLASSES];
923
924/* Register living at given scheduling point. */
925static bitmap curr_reg_live;
926
927/* Saved value of the previous array. */
928static bitmap saved_reg_live;
929
930/* Registers mentioned in the current region. */
931static bitmap region_ref_regs;
932
933/* Temporary bitmap used for SCHED_PRESSURE_MODEL. */
934static bitmap tmp_bitmap;
935
936/* Effective number of available registers of a given class (see comment
937 in sched_pressure_start_bb). */
938static int sched_class_regs_num[N_REG_CLASSES];
939/* Number of call_saved_regs and fixed_regs. Helpers for calculating of
940 sched_class_regs_num. */
941static int call_saved_regs_num[N_REG_CLASSES];
942static int fixed_regs_num[N_REG_CLASSES];
943
944/* Initiate register pressure relative info for scheduling the current
945 region. Currently it is only clearing register mentioned in the
946 current region. */
947void
948sched_init_region_reg_pressure_info (void)
949{
950 bitmap_clear (region_ref_regs);
951}
952
953/* PRESSURE[CL] describes the pressure on register class CL. Update it
954 for the birth (if BIRTH_P) or death (if !BIRTH_P) of register REGNO.
955 LIVE tracks the set of live registers; if it is null, assume that
956 every birth or death is genuine. */
957static inline void
958mark_regno_birth_or_death (bitmap live, int *pressure, int regno, bool birth_p)
959{
960 enum reg_class pressure_class;
961
962 pressure_class = sched_regno_pressure_class[regno];
963 if (regno >= FIRST_PSEUDO_REGISTER)
964 {
965 if (pressure_class != NO_REGS)
966 {
967 if (birth_p)
968 {
969 if (!live || bitmap_set_bit (live, regno))
970 pressure[pressure_class]
971 += (ira_reg_class_max_nregs
972 [pressure_class][PSEUDO_REGNO_MODE (regno)]);
973 }
974 else
975 {
976 if (!live || bitmap_clear_bit (live, regno))
977 pressure[pressure_class]
978 -= (ira_reg_class_max_nregs
979 [pressure_class][PSEUDO_REGNO_MODE (regno)]);
980 }
981 }
982 }
983 else if (pressure_class != NO_REGS
984 && ! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
985 {
986 if (birth_p)
987 {
988 if (!live || bitmap_set_bit (live, regno))
989 pressure[pressure_class]++;
990 }
991 else
992 {
993 if (!live || bitmap_clear_bit (live, regno))
994 pressure[pressure_class]--;
995 }
996 }
997}
998
999/* Initiate current register pressure related info from living
1000 registers given by LIVE. */
1001static void
1002initiate_reg_pressure_info (bitmap live)
1003{
1004 int i;
1005 unsigned int j;
1006 bitmap_iterator bi;
1007
1008 for (i = 0; i < ira_pressure_classes_num; i++)
1009 curr_reg_pressure[ira_pressure_classes[i]] = 0;
1010 bitmap_clear (curr_reg_live);
1011 EXECUTE_IF_SET_IN_BITMAP (live, 0, j, bi)
1012 if (sched_pressure == SCHED_PRESSURE_MODEL
1013 || current_nr_blocks == 1
1014 || bitmap_bit_p (region_ref_regs, j))
1015 mark_regno_birth_or_death (curr_reg_live, curr_reg_pressure, j, true);
1016}
1017
1018/* Mark registers in X as mentioned in the current region. */
1019static void
1020setup_ref_regs (rtx x)
1021{
1022 int i, j;
1023 const RTX_CODE code = GET_CODE (x);
1024 const char *fmt;
1025
1026 if (REG_P (x))
1027 {
1028 bitmap_set_range (region_ref_regs, REGNO (x), REG_NREGS (x));
1029 return;
1030 }
1031 fmt = GET_RTX_FORMAT (code);
1032 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1033 if (fmt[i] == 'e')
1034 setup_ref_regs (XEXP (x, i));
1035 else if (fmt[i] == 'E')
1036 {
1037 for (j = 0; j < XVECLEN (x, i); j++)
1038 setup_ref_regs (XVECEXP (x, i, j));
1039 }
1040}
1041
1042/* Initiate current register pressure related info at the start of
1043 basic block BB. */
1044static void
1045initiate_bb_reg_pressure_info (basic_block bb)
1046{
1047 unsigned int i ATTRIBUTE_UNUSED;
1048 rtx_insn *insn;
1049
1050 if (current_nr_blocks > 1)
1051 FOR_BB_INSNS (bb, insn)
1052 if (NONDEBUG_INSN_P (insn))
1053 setup_ref_regs (PATTERN (insn));
1054 initiate_reg_pressure_info (df_get_live_in (bb));
1055 if (bb_has_eh_pred (bb))
1056 for (i = 0; ; ++i)
1057 {
1058 unsigned int regno = EH_RETURN_DATA_REGNO (i);
1059
1060 if (regno == INVALID_REGNUM)
1061 break;
1062 if (! bitmap_bit_p (df_get_live_in (bb), regno))
1063 mark_regno_birth_or_death (curr_reg_live, curr_reg_pressure,
1064 regno, true);
1065 }
1066}
1067
1068/* Save current register pressure related info. */
1069static void
1070save_reg_pressure (void)
1071{
1072 int i;
1073
1074 for (i = 0; i < ira_pressure_classes_num; i++)
1075 saved_reg_pressure[ira_pressure_classes[i]]
1076 = curr_reg_pressure[ira_pressure_classes[i]];
1077 bitmap_copy (saved_reg_live, curr_reg_live);
1078}
1079
1080/* Restore saved register pressure related info. */
1081static void
1082restore_reg_pressure (void)
1083{
1084 int i;
1085
1086 for (i = 0; i < ira_pressure_classes_num; i++)
1087 curr_reg_pressure[ira_pressure_classes[i]]
1088 = saved_reg_pressure[ira_pressure_classes[i]];
1089 bitmap_copy (curr_reg_live, saved_reg_live);
1090}
1091
1092/* Return TRUE if the register is dying after its USE. */
1093static bool
1094dying_use_p (struct reg_use_data *use)
1095{
1096 struct reg_use_data *next;
1097
1098 for (next = use->next_regno_use; next != use; next = next->next_regno_use)
1099 if (NONDEBUG_INSN_P (next->insn)
1100 && QUEUE_INDEX (next->insn) != QUEUE_SCHEDULED)
1101 return false;
1102 return true;
1103}
1104
1105/* Print info about the current register pressure and its excess for
1106 each pressure class. */
1107static void
1108print_curr_reg_pressure (void)
1109{
1110 int i;
1111 enum reg_class cl;
1112
1113 fprintf (sched_dump, ";;\t");
1114 for (i = 0; i < ira_pressure_classes_num; i++)
1115 {
1116 cl = ira_pressure_classes[i];
1117 gcc_assert (curr_reg_pressure[cl] >= 0);
1118 fprintf (sched_dump, " %s:%d(%d)", reg_class_names[cl],
1119 curr_reg_pressure[cl],
1120 curr_reg_pressure[cl] - sched_class_regs_num[cl]);
1121 }
1122 fprintf (sched_dump, "\n");
1123}
1124
1125/* Determine if INSN has a condition that is clobbered if a register
1126 in SET_REGS is modified. */
1127static bool
1128cond_clobbered_p (rtx_insn *insn, HARD_REG_SET set_regs)
1129{
1130 rtx pat = PATTERN (insn);
1131 gcc_assert (GET_CODE (pat) == COND_EXEC);
1132 if (TEST_HARD_REG_BIT (set_regs, REGNO (XEXP (COND_EXEC_TEST (pat), 0))))
1133 {
1134 sd_iterator_def sd_it;
1135 dep_t dep;
1136 haifa_change_pattern (insn, ORIG_PAT (insn));
1137 FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
1138 DEP_STATUS (dep) &= ~DEP_CANCELLED;
1139 TODO_SPEC (insn) = HARD_DEP;
1140 if (sched_verbose >= 2)
1141 fprintf (sched_dump,
1142 ";;\t\tdequeue insn %s because of clobbered condition\n",
1143 (*current_sched_info->print_insn) (insn, 0));
1144 return true;
1145 }
1146
1147 return false;
1148}
1149
1150/* This function should be called after modifying the pattern of INSN,
1151 to update scheduler data structures as needed. */
1152static void
1153update_insn_after_change (rtx_insn *insn)
1154{
1155 sd_iterator_def sd_it;
1156 dep_t dep;
1157
1158 dfa_clear_single_insn_cache (insn);
1159
1160 sd_it = sd_iterator_start (insn,
1161 SD_LIST_FORW | SD_LIST_BACK | SD_LIST_RES_BACK);
1162 while (sd_iterator_cond (&sd_it, &dep))
1163 {
1164 DEP_COST (dep) = UNKNOWN_DEP_COST;
1165 sd_iterator_next (&sd_it);
1166 }
1167
1168 /* Invalidate INSN_COST, so it'll be recalculated. */
1169 INSN_COST (insn) = -1;
1170 /* Invalidate INSN_TICK, so it'll be recalculated. */
1171 INSN_TICK (insn) = INVALID_TICK;
1172
1173 /* Invalidate autoprefetch data entry. */
1174 INSN_AUTOPREF_MULTIPASS_DATA (insn)[0].status
1175 = AUTOPREF_MULTIPASS_DATA_UNINITIALIZED;
1176 INSN_AUTOPREF_MULTIPASS_DATA (insn)[1].status
1177 = AUTOPREF_MULTIPASS_DATA_UNINITIALIZED;
1178}
1179
1180
1181/* Two VECs, one to hold dependencies for which pattern replacements
1182 need to be applied or restored at the start of the next cycle, and
1183 another to hold an integer that is either one, to apply the
1184 corresponding replacement, or zero to restore it. */
1185static vec<dep_t> next_cycle_replace_deps;
1186static vec<int> next_cycle_apply;
1187
1188static void apply_replacement (dep_t, bool);
1189static void restore_pattern (dep_t, bool);
1190
1191/* Look at the remaining dependencies for insn NEXT, and compute and return
1192 the TODO_SPEC value we should use for it. This is called after one of
1193 NEXT's dependencies has been resolved.
1194 We also perform pattern replacements for predication, and for broken
1195 replacement dependencies. The latter is only done if FOR_BACKTRACK is
1196 false. */
1197
1198static ds_t
1199recompute_todo_spec (rtx_insn *next, bool for_backtrack)
1200{
1201 ds_t new_ds;
1202 sd_iterator_def sd_it;
1203 dep_t dep, modify_dep = NULL;
1204 int n_spec = 0;
1205 int n_control = 0;
1206 int n_replace = 0;
1207 bool first_p = true;
1208
1209 if (sd_lists_empty_p (next, SD_LIST_BACK))
1210 /* NEXT has all its dependencies resolved. */
1211 return 0;
1212
1213 if (!sd_lists_empty_p (next, SD_LIST_HARD_BACK))
1214 return HARD_DEP;
1215
1216 /* If NEXT is intended to sit adjacent to this instruction, we don't
1217 want to try to break any dependencies. Treat it as a HARD_DEP. */
1218 if (SCHED_GROUP_P (next))
1219 return HARD_DEP;
1220
1221 /* Now we've got NEXT with speculative deps only.
1222 1. Look at the deps to see what we have to do.
1223 2. Check if we can do 'todo'. */
1224 new_ds = 0;
1225
1226 FOR_EACH_DEP (next, SD_LIST_BACK, sd_it, dep)
1227 {
1228 rtx_insn *pro = DEP_PRO (dep);
1229 ds_t ds = DEP_STATUS (dep) & SPECULATIVE;
1230
1231 if (DEBUG_INSN_P (pro) && !DEBUG_INSN_P (next))
1232 continue;
1233
1234 if (ds)
1235 {
1236 n_spec++;
1237 if (first_p)
1238 {
1239 first_p = false;
1240
1241 new_ds = ds;
1242 }
1243 else
1244 new_ds = ds_merge (new_ds, ds);
1245 }
1246 else if (DEP_TYPE (dep) == REG_DEP_CONTROL)
1247 {
1248 if (QUEUE_INDEX (pro) != QUEUE_SCHEDULED)
1249 {
1250 n_control++;
1251 modify_dep = dep;
1252 }
1253 DEP_STATUS (dep) &= ~DEP_CANCELLED;
1254 }
1255 else if (DEP_REPLACE (dep) != NULL)
1256 {
1257 if (QUEUE_INDEX (pro) != QUEUE_SCHEDULED)
1258 {
1259 n_replace++;
1260 modify_dep = dep;
1261 }
1262 DEP_STATUS (dep) &= ~DEP_CANCELLED;
1263 }
1264 }
1265
1266 if (n_replace > 0 && n_control == 0 && n_spec == 0)
1267 {
1268 if (!dbg_cnt (sched_breakdep))
1269 return HARD_DEP;
1270 FOR_EACH_DEP (next, SD_LIST_BACK, sd_it, dep)
1271 {
1272 struct dep_replacement *desc = DEP_REPLACE (dep);
1273 if (desc != NULL)
1274 {
1275 if (desc->insn == next && !for_backtrack)
1276 {
1277 gcc_assert (n_replace == 1);
1278 apply_replacement (dep, true);
1279 }
1280 DEP_STATUS (dep) |= DEP_CANCELLED;
1281 }
1282 }
1283 return 0;
1284 }
1285
1286 else if (n_control == 1 && n_replace == 0 && n_spec == 0)
1287 {
1288 rtx_insn *pro, *other;
1289 rtx new_pat;
1290 rtx cond = NULL_RTX;
1291 bool success;
1292 rtx_insn *prev = NULL;
1293 int i;
1294 unsigned regno;
1295
1296 if ((current_sched_info->flags & DO_PREDICATION) == 0
1297 || (ORIG_PAT (next) != NULL_RTX
1298 && PREDICATED_PAT (next) == NULL_RTX))
1299 return HARD_DEP;
1300
1301 pro = DEP_PRO (modify_dep);
1302 other = real_insn_for_shadow (pro);
1303 if (other != NULL_RTX)
1304 pro = other;
1305
1306 cond = sched_get_reverse_condition_uncached (pro);
1307 regno = REGNO (XEXP (cond, 0));
1308
1309 /* Find the last scheduled insn that modifies the condition register.
1310 We can stop looking once we find the insn we depend on through the
1311 REG_DEP_CONTROL; if the condition register isn't modified after it,
1312 we know that it still has the right value. */
1313 if (QUEUE_INDEX (pro) == QUEUE_SCHEDULED)
1314 FOR_EACH_VEC_ELT_REVERSE (scheduled_insns, i, prev)
1315 {
1316 HARD_REG_SET t;
1317
1318 find_all_hard_reg_sets (prev, &t, true);
1319 if (TEST_HARD_REG_BIT (t, regno))
1320 return HARD_DEP;
1321 if (prev == pro)
1322 break;
1323 }
1324 if (ORIG_PAT (next) == NULL_RTX)
1325 {
1326 ORIG_PAT (next) = PATTERN (next);
1327
1328 new_pat = gen_rtx_COND_EXEC (VOIDmode, cond, PATTERN (next));
1329 success = haifa_change_pattern (next, new_pat);
1330 if (!success)
1331 return HARD_DEP;
1332 PREDICATED_PAT (next) = new_pat;
1333 }
1334 else if (PATTERN (next) != PREDICATED_PAT (next))
1335 {
1336 bool success = haifa_change_pattern (next,
1337 PREDICATED_PAT (next));
1338 gcc_assert (success);
1339 }
1340 DEP_STATUS (modify_dep) |= DEP_CANCELLED;
1341 return DEP_CONTROL;
1342 }
1343
1344 if (PREDICATED_PAT (next) != NULL_RTX)
1345 {
1346 int tick = INSN_TICK (next);
1347 bool success = haifa_change_pattern (next,
1348 ORIG_PAT (next));
1349 INSN_TICK (next) = tick;
1350 gcc_assert (success);
1351 }
1352
1353 /* We can't handle the case where there are both speculative and control
1354 dependencies, so we return HARD_DEP in such a case. Also fail if
1355 we have speculative dependencies with not enough points, or more than
1356 one control dependency. */
1357 if ((n_spec > 0 && (n_control > 0 || n_replace > 0))
1358 || (n_spec > 0
1359 /* Too few points? */
1360 && ds_weak (new_ds) < spec_info->data_weakness_cutoff)
1361 || n_control > 0
1362 || n_replace > 0)
1363 return HARD_DEP;
1364
1365 return new_ds;
1366}
1367
1368/* Pointer to the last instruction scheduled. */
1369static rtx_insn *last_scheduled_insn;
1370
1371/* Pointer to the last nondebug instruction scheduled within the
1372 block, or the prev_head of the scheduling block. Used by
1373 rank_for_schedule, so that insns independent of the last scheduled
1374 insn will be preferred over dependent instructions. */
1375static rtx_insn *last_nondebug_scheduled_insn;
1376
1377/* Pointer that iterates through the list of unscheduled insns if we
1378 have a dbg_cnt enabled. It always points at an insn prior to the
1379 first unscheduled one. */
1380static rtx_insn *nonscheduled_insns_begin;
1381
1382/* Compute cost of executing INSN.
1383 This is the number of cycles between instruction issue and
1384 instruction results. */
1385int
1386insn_sched_cost (rtx_insn *insn)
1387{
1388 int cost;
1389
1390 if (sched_fusion)
1391 return 0;
1392
1393 if (sel_sched_p ())
1394 {
1395 if (recog_memoized (insn) < 0)
1396 return 0;
1397
1398 cost = insn_default_latency (insn);
1399 if (cost < 0)
1400 cost = 0;
1401
1402 return cost;
1403 }
1404
1405 cost = INSN_COST (insn);
1406
1407 if (cost < 0)
1408 {
1409 /* A USE insn, or something else we don't need to
1410 understand. We can't pass these directly to
1411 result_ready_cost or insn_default_latency because it will
1412 trigger a fatal error for unrecognizable insns. */
1413 if (recog_memoized (insn) < 0)
1414 {
1415 INSN_COST (insn) = 0;
1416 return 0;
1417 }
1418 else
1419 {
1420 cost = insn_default_latency (insn);
1421 if (cost < 0)
1422 cost = 0;
1423
1424 INSN_COST (insn) = cost;
1425 }
1426 }
1427
1428 return cost;
1429}
1430
1431/* Compute cost of dependence LINK.
1432 This is the number of cycles between instruction issue and
1433 instruction results.
1434 ??? We also use this function to call recog_memoized on all insns. */
1435int
1436dep_cost_1 (dep_t link, dw_t dw)
1437{
1438 rtx_insn *insn = DEP_PRO (link);
1439 rtx_insn *used = DEP_CON (link);
1440 int cost;
1441
1442 if (DEP_COST (link) != UNKNOWN_DEP_COST)
1443 return DEP_COST (link);
1444
1445 if (delay_htab)
1446 {
1447 struct delay_pair *delay_entry;
1448 delay_entry
1449 = delay_htab_i2->find_with_hash (used, htab_hash_pointer (used));
1450 if (delay_entry)
1451 {
1452 if (delay_entry->i1 == insn)
1453 {
1454 DEP_COST (link) = pair_delay (delay_entry);
1455 return DEP_COST (link);
1456 }
1457 }
1458 }
1459
1460 /* A USE insn should never require the value used to be computed.
1461 This allows the computation of a function's result and parameter
1462 values to overlap the return and call. We don't care about the
1463 dependence cost when only decreasing register pressure. */
1464 if (recog_memoized (used) < 0)
1465 {
1466 cost = 0;
1467 recog_memoized (insn);
1468 }
1469 else
1470 {
1471 enum reg_note dep_type = DEP_TYPE (link);
1472
1473 cost = insn_sched_cost (insn);
1474
1475 if (INSN_CODE (insn) >= 0)
1476 {
1477 if (dep_type == REG_DEP_ANTI)
1478 cost = 0;
1479 else if (dep_type == REG_DEP_OUTPUT)
1480 {
1481 cost = (insn_default_latency (insn)
1482 - insn_default_latency (used));
1483 if (cost <= 0)
1484 cost = 1;
1485 }
1486 else if (bypass_p (insn))
1487 cost = insn_latency (insn, used);
1488 }
1489
1490
1491 if (targetm.sched.adjust_cost)
1492 cost = targetm.sched.adjust_cost (used, (int) dep_type, insn, cost,
1493 dw);
1494
1495 if (cost < 0)
1496 cost = 0;
1497 }
1498
1499 DEP_COST (link) = cost;
1500 return cost;
1501}
1502
1503/* Compute cost of dependence LINK.
1504 This is the number of cycles between instruction issue and
1505 instruction results. */
1506int
1507dep_cost (dep_t link)
1508{
1509 return dep_cost_1 (link, 0);
1510}
1511
1512/* Use this sel-sched.c friendly function in reorder2 instead of increasing
1513 INSN_PRIORITY explicitly. */
1514void
1515increase_insn_priority (rtx_insn *insn, int amount)
1516{
1517 if (!sel_sched_p ())
1518 {
1519 /* We're dealing with haifa-sched.c INSN_PRIORITY. */
1520 if (INSN_PRIORITY_KNOWN (insn))
1521 INSN_PRIORITY (insn) += amount;
1522 }
1523 else
1524 {
1525 /* In sel-sched.c INSN_PRIORITY is not kept up to date.
1526 Use EXPR_PRIORITY instead. */
1527 sel_add_to_insn_priority (insn, amount);
1528 }
1529}
1530
1531/* Return 'true' if DEP should be included in priority calculations. */
1532static bool
1533contributes_to_priority_p (dep_t dep)
1534{
1535 if (DEBUG_INSN_P (DEP_CON (dep))
1536 || DEBUG_INSN_P (DEP_PRO (dep)))
1537 return false;
1538
1539 /* Critical path is meaningful in block boundaries only. */
1540 if (!current_sched_info->contributes_to_priority (DEP_CON (dep),
1541 DEP_PRO (dep)))
1542 return false;
1543
1544 if (DEP_REPLACE (dep) != NULL)
1545 return false;
1546
1547 /* If flag COUNT_SPEC_IN_CRITICAL_PATH is set,
1548 then speculative instructions will less likely be
1549 scheduled. That is because the priority of
1550 their producers will increase, and, thus, the
1551 producers will more likely be scheduled, thus,
1552 resolving the dependence. */
1553 if (sched_deps_info->generate_spec_deps
1554 && !(spec_info->flags & COUNT_SPEC_IN_CRITICAL_PATH)
1555 && (DEP_STATUS (dep) & SPECULATIVE))
1556 return false;
1557
1558 return true;
1559}
1560
1561/* Compute the number of nondebug deps in list LIST for INSN. */
1562
1563static int
1564dep_list_size (rtx_insn *insn, sd_list_types_def list)
1565{
1566 sd_iterator_def sd_it;
1567 dep_t dep;
1568 int dbgcount = 0, nodbgcount = 0;
1569
1570 if (!MAY_HAVE_DEBUG_INSNS)
1571 return sd_lists_size (insn, list);
1572
1573 FOR_EACH_DEP (insn, list, sd_it, dep)
1574 {
1575 if (DEBUG_INSN_P (DEP_CON (dep)))
1576 dbgcount++;
1577 else if (!DEBUG_INSN_P (DEP_PRO (dep)))
1578 nodbgcount++;
1579 }
1580
1581 gcc_assert (dbgcount + nodbgcount == sd_lists_size (insn, list));
1582
1583 return nodbgcount;
1584}
1585
1586bool sched_fusion;
1587
1588/* Compute the priority number for INSN. */
1589static int
1590priority (rtx_insn *insn)
1591{
1592 if (! INSN_P (insn))
1593 return 0;
1594
1595 /* We should not be interested in priority of an already scheduled insn. */
1596 gcc_assert (QUEUE_INDEX (insn) != QUEUE_SCHEDULED);
1597
1598 if (!INSN_PRIORITY_KNOWN (insn))
1599 {
1600 int this_priority = -1;
1601
1602 if (sched_fusion)
1603 {
1604 int this_fusion_priority;
1605
1606 targetm.sched.fusion_priority (insn, FUSION_MAX_PRIORITY,
1607 &this_fusion_priority, &this_priority);
1608 INSN_FUSION_PRIORITY (insn) = this_fusion_priority;
1609 }
1610 else if (dep_list_size (insn, SD_LIST_FORW) == 0)
1611 /* ??? We should set INSN_PRIORITY to insn_sched_cost when and insn
1612 has some forward deps but all of them are ignored by
1613 contributes_to_priority hook. At the moment we set priority of
1614 such insn to 0. */
1615 this_priority = insn_sched_cost (insn);
1616 else
1617 {
1618 rtx_insn *prev_first, *twin;
1619 basic_block rec;
1620
1621 /* For recovery check instructions we calculate priority slightly
1622 different than that of normal instructions. Instead of walking
1623 through INSN_FORW_DEPS (check) list, we walk through
1624 INSN_FORW_DEPS list of each instruction in the corresponding
1625 recovery block. */
1626
1627 /* Selective scheduling does not define RECOVERY_BLOCK macro. */
1628 rec = sel_sched_p () ? NULL : RECOVERY_BLOCK (insn);
1629 if (!rec || rec == EXIT_BLOCK_PTR_FOR_FN (cfun))
1630 {
1631 prev_first = PREV_INSN (insn);
1632 twin = insn;
1633 }
1634 else
1635 {
1636 prev_first = NEXT_INSN (BB_HEAD (rec));
1637 twin = PREV_INSN (BB_END (rec));
1638 }
1639
1640 do
1641 {
1642 sd_iterator_def sd_it;
1643 dep_t dep;
1644
1645 FOR_EACH_DEP (twin, SD_LIST_FORW, sd_it, dep)
1646 {
1647 rtx_insn *next;
1648 int next_priority;
1649
1650 next = DEP_CON (dep);
1651
1652 if (BLOCK_FOR_INSN (next) != rec)
1653 {
1654 int cost;
1655
1656 if (!contributes_to_priority_p (dep))
1657 continue;
1658
1659 if (twin == insn)
1660 cost = dep_cost (dep);
1661 else
1662 {
1663 struct _dep _dep1, *dep1 = &_dep1;
1664
1665 init_dep (dep1, insn, next, REG_DEP_ANTI);
1666
1667 cost = dep_cost (dep1);
1668 }
1669
1670 next_priority = cost + priority (next);
1671
1672 if (next_priority > this_priority)
1673 this_priority = next_priority;
1674 }
1675 }
1676
1677 twin = PREV_INSN (twin);
1678 }
1679 while (twin != prev_first);
1680 }
1681
1682 if (this_priority < 0)
1683 {
1684 gcc_assert (this_priority == -1);
1685
1686 this_priority = insn_sched_cost (insn);
1687 }
1688
1689 INSN_PRIORITY (insn) = this_priority;
1690 INSN_PRIORITY_STATUS (insn) = 1;
1691 }
1692
1693 return INSN_PRIORITY (insn);
1694}
1695
1696/* Macros and functions for keeping the priority queue sorted, and
1697 dealing with queuing and dequeuing of instructions. */
1698
1699/* For each pressure class CL, set DEATH[CL] to the number of registers
1700 in that class that die in INSN. */
1701
1702static void
1703calculate_reg_deaths (rtx_insn *insn, int *death)
1704{
1705 int i;
1706 struct reg_use_data *use;
1707
1708 for (i = 0; i < ira_pressure_classes_num; i++)
1709 death[ira_pressure_classes[i]] = 0;
1710 for (use = INSN_REG_USE_LIST (insn); use != NULL; use = use->next_insn_use)
1711 if (dying_use_p (use))
1712 mark_regno_birth_or_death (0, death, use->regno, true);
1713}
1714
1715/* Setup info about the current register pressure impact of scheduling
1716 INSN at the current scheduling point. */
1717static void
1718setup_insn_reg_pressure_info (rtx_insn *insn)
1719{
1720 int i, change, before, after, hard_regno;
1721 int excess_cost_change;
1722 machine_mode mode;
1723 enum reg_class cl;
1724 struct reg_pressure_data *pressure_info;
1725 int *max_reg_pressure;
1726 static int death[N_REG_CLASSES];
1727
1728 gcc_checking_assert (!DEBUG_INSN_P (insn));
1729
1730 excess_cost_change = 0;
1731 calculate_reg_deaths (insn, death);
1732 pressure_info = INSN_REG_PRESSURE (insn);
1733 max_reg_pressure = INSN_MAX_REG_PRESSURE (insn);
1734 gcc_assert (pressure_info != NULL && max_reg_pressure != NULL);
1735 for (i = 0; i < ira_pressure_classes_num; i++)
1736 {
1737 cl = ira_pressure_classes[i];
1738 gcc_assert (curr_reg_pressure[cl] >= 0);
1739 change = (int) pressure_info[i].set_increase - death[cl];
1740 before = MAX (0, max_reg_pressure[i] - sched_class_regs_num[cl]);
1741 after = MAX (0, max_reg_pressure[i] + change
1742 - sched_class_regs_num[cl]);
1743 hard_regno = ira_class_hard_regs[cl][0];
1744 gcc_assert (hard_regno >= 0);
1745 mode = reg_raw_mode[hard_regno];
1746 excess_cost_change += ((after - before)
1747 * (ira_memory_move_cost[mode][cl][0]
1748 + ira_memory_move_cost[mode][cl][1]));
1749 }
1750 INSN_REG_PRESSURE_EXCESS_COST_CHANGE (insn) = excess_cost_change;
1751}
1752
1753/* This is the first page of code related to SCHED_PRESSURE_MODEL.
1754 It tries to make the scheduler take register pressure into account
1755 without introducing too many unnecessary stalls. It hooks into the
1756 main scheduling algorithm at several points:
1757
1758 - Before scheduling starts, model_start_schedule constructs a
1759 "model schedule" for the current block. This model schedule is
1760 chosen solely to keep register pressure down. It does not take the
1761 target's pipeline or the original instruction order into account,
1762 except as a tie-breaker. It also doesn't work to a particular
1763 pressure limit.
1764
1765 This model schedule gives us an idea of what pressure can be
1766 achieved for the block and gives us an example of a schedule that
1767 keeps to that pressure. It also makes the final schedule less
1768 dependent on the original instruction order. This is important
1769 because the original order can either be "wide" (many values live
1770 at once, such as in user-scheduled code) or "narrow" (few values
1771 live at once, such as after loop unrolling, where several
1772 iterations are executed sequentially).
1773
1774 We do not apply this model schedule to the rtx stream. We simply
1775 record it in model_schedule. We also compute the maximum pressure,
1776 MP, that was seen during this schedule.
1777
1778 - Instructions are added to the ready queue even if they require
1779 a stall. The length of the stall is instead computed as:
1780
1781 MAX (INSN_TICK (INSN) - clock_var, 0)
1782
1783 (= insn_delay). This allows rank_for_schedule to choose between
1784 introducing a deliberate stall or increasing pressure.
1785
1786 - Before sorting the ready queue, model_set_excess_costs assigns
1787 a pressure-based cost to each ready instruction in the queue.
1788 This is the instruction's INSN_REG_PRESSURE_EXCESS_COST_CHANGE
1789 (ECC for short) and is effectively measured in cycles.
1790
1791 - rank_for_schedule ranks instructions based on:
1792
1793 ECC (insn) + insn_delay (insn)
1794
1795 then as:
1796
1797 insn_delay (insn)
1798
1799 So, for example, an instruction X1 with an ECC of 1 that can issue
1800 now will win over an instruction X0 with an ECC of zero that would
1801 introduce a stall of one cycle. However, an instruction X2 with an
1802 ECC of 2 that can issue now will lose to both X0 and X1.
1803
1804 - When an instruction is scheduled, model_recompute updates the model
1805 schedule with the new pressures (some of which might now exceed the
1806 original maximum pressure MP). model_update_limit_points then searches
1807 for the new point of maximum pressure, if not already known. */
1808
1809/* Used to separate high-verbosity debug information for SCHED_PRESSURE_MODEL
1810 from surrounding debug information. */
1811#define MODEL_BAR \
1812 ";;\t\t+------------------------------------------------------\n"
1813
1814/* Information about the pressure on a particular register class at a
1815 particular point of the model schedule. */
1816struct model_pressure_data {
1817 /* The pressure at this point of the model schedule, or -1 if the
1818 point is associated with an instruction that has already been
1819 scheduled. */
1820 int ref_pressure;
1821
1822 /* The maximum pressure during or after this point of the model schedule. */
1823 int max_pressure;
1824};
1825
1826/* Per-instruction information that is used while building the model
1827 schedule. Here, "schedule" refers to the model schedule rather
1828 than the main schedule. */
1829struct model_insn_info {
1830 /* The instruction itself. */
1831 rtx_insn *insn;
1832
1833 /* If this instruction is in model_worklist, these fields link to the
1834 previous (higher-priority) and next (lower-priority) instructions
1835 in the list. */
1836 struct model_insn_info *prev;
1837 struct model_insn_info *next;
1838
1839 /* While constructing the schedule, QUEUE_INDEX describes whether an
1840 instruction has already been added to the schedule (QUEUE_SCHEDULED),
1841 is in model_worklist (QUEUE_READY), or neither (QUEUE_NOWHERE).
1842 old_queue records the value that QUEUE_INDEX had before scheduling
1843 started, so that we can restore it once the schedule is complete. */
1844 int old_queue;
1845
1846 /* The relative importance of an unscheduled instruction. Higher
1847 values indicate greater importance. */
1848 unsigned int model_priority;
1849
1850 /* The length of the longest path of satisfied true dependencies
1851 that leads to this instruction. */
1852 unsigned int depth;
1853
1854 /* The length of the longest path of dependencies of any kind
1855 that leads from this instruction. */
1856 unsigned int alap;
1857
1858 /* The number of predecessor nodes that must still be scheduled. */
1859 int unscheduled_preds;
1860};
1861
1862/* Information about the pressure limit for a particular register class.
1863 This structure is used when applying a model schedule to the main
1864 schedule. */
1865struct model_pressure_limit {
1866 /* The maximum register pressure seen in the original model schedule. */
1867 int orig_pressure;
1868
1869 /* The maximum register pressure seen in the current model schedule
1870 (which excludes instructions that have already been scheduled). */
1871 int pressure;
1872
1873 /* The point of the current model schedule at which PRESSURE is first
1874 reached. It is set to -1 if the value needs to be recomputed. */
1875 int point;
1876};
1877
1878/* Describes a particular way of measuring register pressure. */
1879struct model_pressure_group {
1880 /* Index PCI describes the maximum pressure on ira_pressure_classes[PCI]. */
1881 struct model_pressure_limit limits[N_REG_CLASSES];
1882
1883 /* Index (POINT * ira_num_pressure_classes + PCI) describes the pressure
1884 on register class ira_pressure_classes[PCI] at point POINT of the
1885 current model schedule. A POINT of model_num_insns describes the
1886 pressure at the end of the schedule. */
1887 struct model_pressure_data *model;
1888};
1889
1890/* Index POINT gives the instruction at point POINT of the model schedule.
1891 This array doesn't change during main scheduling. */
1892static vec<rtx_insn *> model_schedule;
1893
1894/* The list of instructions in the model worklist, sorted in order of
1895 decreasing priority. */
1896static struct model_insn_info *model_worklist;
1897
1898/* Index I describes the instruction with INSN_LUID I. */
1899static struct model_insn_info *model_insns;
1900
1901/* The number of instructions in the model schedule. */
1902static int model_num_insns;
1903
1904/* The index of the first instruction in model_schedule that hasn't yet been
1905 added to the main schedule, or model_num_insns if all of them have. */
1906static int model_curr_point;
1907
1908/* Describes the pressure before each instruction in the model schedule. */
1909static struct model_pressure_group model_before_pressure;
1910
1911/* The first unused model_priority value (as used in model_insn_info). */
1912static unsigned int model_next_priority;
1913
1914
1915/* The model_pressure_data for ira_pressure_classes[PCI] in GROUP
1916 at point POINT of the model schedule. */
1917#define MODEL_PRESSURE_DATA(GROUP, POINT, PCI) \
1918 (&(GROUP)->model[(POINT) * ira_pressure_classes_num + (PCI)])
1919
1920/* The maximum pressure on ira_pressure_classes[PCI] in GROUP at or
1921 after point POINT of the model schedule. */
1922#define MODEL_MAX_PRESSURE(GROUP, POINT, PCI) \
1923 (MODEL_PRESSURE_DATA (GROUP, POINT, PCI)->max_pressure)
1924
1925/* The pressure on ira_pressure_classes[PCI] in GROUP at point POINT
1926 of the model schedule. */
1927#define MODEL_REF_PRESSURE(GROUP, POINT, PCI) \
1928 (MODEL_PRESSURE_DATA (GROUP, POINT, PCI)->ref_pressure)
1929
1930/* Information about INSN that is used when creating the model schedule. */
1931#define MODEL_INSN_INFO(INSN) \
1932 (&model_insns[INSN_LUID (INSN)])
1933
1934/* The instruction at point POINT of the model schedule. */
1935#define MODEL_INSN(POINT) \
1936 (model_schedule[POINT])
1937
1938
1939/* Return INSN's index in the model schedule, or model_num_insns if it
1940 doesn't belong to that schedule. */
1941
1942static int
1943model_index (rtx_insn *insn)
1944{
1945 if (INSN_MODEL_INDEX (insn) == 0)
1946 return model_num_insns;
1947 return INSN_MODEL_INDEX (insn) - 1;
1948}
1949
1950/* Make sure that GROUP->limits is up-to-date for the current point
1951 of the model schedule. */
1952
1953static void
1954model_update_limit_points_in_group (struct model_pressure_group *group)
1955{
1956 int pci, max_pressure, point;
1957
1958 for (pci = 0; pci < ira_pressure_classes_num; pci++)
1959 {
1960 /* We may have passed the final point at which the pressure in
1961 group->limits[pci].pressure was reached. Update the limit if so. */
1962 max_pressure = MODEL_MAX_PRESSURE (group, model_curr_point, pci);
1963 group->limits[pci].pressure = max_pressure;
1964
1965 /* Find the point at which MAX_PRESSURE is first reached. We need
1966 to search in three cases:
1967
1968 - We've already moved past the previous pressure point.
1969 In this case we search forward from model_curr_point.
1970
1971 - We scheduled the previous point of maximum pressure ahead of
1972 its position in the model schedule, but doing so didn't bring
1973 the pressure point earlier. In this case we search forward
1974 from that previous pressure point.
1975
1976 - Scheduling an instruction early caused the maximum pressure
1977 to decrease. In this case we will have set the pressure
1978 point to -1, and we search forward from model_curr_point. */
1979 point = MAX (group->limits[pci].point, model_curr_point);
1980 while (point < model_num_insns
1981 && MODEL_REF_PRESSURE (group, point, pci) < max_pressure)
1982 point++;
1983 group->limits[pci].point = point;
1984
1985 gcc_assert (MODEL_REF_PRESSURE (group, point, pci) == max_pressure);
1986 gcc_assert (MODEL_MAX_PRESSURE (group, point, pci) == max_pressure);
1987 }
1988}
1989
1990/* Make sure that all register-pressure limits are up-to-date for the
1991 current position in the model schedule. */
1992
1993static void
1994model_update_limit_points (void)
1995{
1996 model_update_limit_points_in_group (&model_before_pressure);
1997}
1998
1999/* Return the model_index of the last unscheduled use in chain USE
2000 outside of USE's instruction. Return -1 if there are no other uses,
2001 or model_num_insns if the register is live at the end of the block. */
2002
2003static int
2004model_last_use_except (struct reg_use_data *use)
2005{
2006 struct reg_use_data *next;
2007 int last, index;
2008
2009 last = -1;
2010 for (next = use->next_regno_use; next != use; next = next->next_regno_use)
2011 if (NONDEBUG_INSN_P (next->insn)
2012 && QUEUE_INDEX (next->insn) != QUEUE_SCHEDULED)
2013 {
2014 index = model_index (next->insn);
2015 if (index == model_num_insns)
2016 return model_num_insns;
2017 if (last < index)
2018 last = index;
2019 }
2020 return last;
2021}
2022
2023/* An instruction with model_index POINT has just been scheduled, and it
2024 adds DELTA to the pressure on ira_pressure_classes[PCI] after POINT - 1.
2025 Update MODEL_REF_PRESSURE (GROUP, POINT, PCI) and
2026 MODEL_MAX_PRESSURE (GROUP, POINT, PCI) accordingly. */
2027
2028static void
2029model_start_update_pressure (struct model_pressure_group *group,
2030 int point, int pci, int delta)
2031{
2032 int next_max_pressure;
2033
2034 if (point == model_num_insns)
2035 {
2036 /* The instruction wasn't part of the model schedule; it was moved
2037 from a different block. Update the pressure for the end of
2038 the model schedule. */
2039 MODEL_REF_PRESSURE (group, point, pci) += delta;
2040 MODEL_MAX_PRESSURE (group, point, pci) += delta;
2041 }
2042 else
2043 {
2044 /* Record that this instruction has been scheduled. Nothing now
2045 changes between POINT and POINT + 1, so get the maximum pressure
2046 from the latter. If the maximum pressure decreases, the new
2047 pressure point may be before POINT. */
2048 MODEL_REF_PRESSURE (group, point, pci) = -1;
2049 next_max_pressure = MODEL_MAX_PRESSURE (group, point + 1, pci);
2050 if (MODEL_MAX_PRESSURE (group, point, pci) > next_max_pressure)
2051 {
2052 MODEL_MAX_PRESSURE (group, point, pci) = next_max_pressure;
2053 if (group->limits[pci].point == point)
2054 group->limits[pci].point = -1;
2055 }
2056 }
2057}
2058
2059/* Record that scheduling a later instruction has changed the pressure
2060 at point POINT of the model schedule by DELTA (which might be 0).
2061 Update GROUP accordingly. Return nonzero if these changes might
2062 trigger changes to previous points as well. */
2063
2064static int
2065model_update_pressure (struct model_pressure_group *group,
2066 int point, int pci, int delta)
2067{
2068 int ref_pressure, max_pressure, next_max_pressure;
2069
2070 /* If POINT hasn't yet been scheduled, update its pressure. */
2071 ref_pressure = MODEL_REF_PRESSURE (group, point, pci);
2072 if (ref_pressure >= 0 && delta != 0)
2073 {
2074 ref_pressure += delta;
2075 MODEL_REF_PRESSURE (group, point, pci) = ref_pressure;
2076
2077 /* Check whether the maximum pressure in the overall schedule
2078 has increased. (This means that the MODEL_MAX_PRESSURE of
2079 every point <= POINT will need to increase too; see below.) */
2080 if (group->limits[pci].pressure < ref_pressure)
2081 group->limits[pci].pressure = ref_pressure;
2082
2083 /* If we are at maximum pressure, and the maximum pressure
2084 point was previously unknown or later than POINT,
2085 bring it forward. */
2086 if (group->limits[pci].pressure == ref_pressure
2087 && !IN_RANGE (group->limits[pci].point, 0, point))
2088 group->limits[pci].point = point;
2089
2090 /* If POINT used to be the point of maximum pressure, but isn't
2091 any longer, we need to recalculate it using a forward walk. */
2092 if (group->limits[pci].pressure > ref_pressure
2093 && group->limits[pci].point == point)
2094 group->limits[pci].point = -1;
2095 }
2096
2097 /* Update the maximum pressure at POINT. Changes here might also
2098 affect the maximum pressure at POINT - 1. */
2099 next_max_pressure = MODEL_MAX_PRESSURE (group, point + 1, pci);
2100 max_pressure = MAX (ref_pressure, next_max_pressure);
2101 if (MODEL_MAX_PRESSURE (group, point, pci) != max_pressure)
2102 {
2103 MODEL_MAX_PRESSURE (group, point, pci) = max_pressure;
2104 return 1;
2105 }
2106 return 0;
2107}
2108
2109/* INSN has just been scheduled. Update the model schedule accordingly. */
2110
2111static void
2112model_recompute (rtx_insn *insn)
2113{
2114 struct {
2115 int last_use;
2116 int regno;
2117 } uses[FIRST_PSEUDO_REGISTER + MAX_RECOG_OPERANDS];
2118 struct reg_use_data *use;
2119 struct reg_pressure_data *reg_pressure;
2120 int delta[N_REG_CLASSES];
2121 int pci, point, mix, new_last, cl, ref_pressure, queue;
2122 unsigned int i, num_uses, num_pending_births;
2123 bool print_p;
2124
2125 /* The destinations of INSN were previously live from POINT onwards, but are
2126 now live from model_curr_point onwards. Set up DELTA accordingly. */
2127 point = model_index (insn);
2128 reg_pressure = INSN_REG_PRESSURE (insn);
2129 for (pci = 0; pci < ira_pressure_classes_num; pci++)
2130 {
2131 cl = ira_pressure_classes[pci];
2132 delta[cl] = reg_pressure[pci].set_increase;
2133 }
2134
2135 /* Record which registers previously died at POINT, but which now die
2136 before POINT. Adjust DELTA so that it represents the effect of
2137 this change after POINT - 1. Set NUM_PENDING_BIRTHS to the number of
2138 registers that will be born in the range [model_curr_point, POINT). */
2139 num_uses = 0;
2140 num_pending_births = 0;
2141 bitmap_clear (tmp_bitmap);
2142 for (use = INSN_REG_USE_LIST (insn); use != NULL; use = use->next_insn_use)
2143 {
2144 new_last = model_last_use_except (use);
2145 if (new_last < point && bitmap_set_bit (tmp_bitmap, use->regno))
2146 {
2147 gcc_assert (num_uses < ARRAY_SIZE (uses));
2148 uses[num_uses].last_use = new_last;
2149 uses[num_uses].regno = use->regno;
2150 /* This register is no longer live after POINT - 1. */
2151 mark_regno_birth_or_death (NULL, delta, use->regno, false);
2152 num_uses++;
2153 if (new_last >= 0)
2154 num_pending_births++;
2155 }
2156 }
2157
2158 /* Update the MODEL_REF_PRESSURE and MODEL_MAX_PRESSURE for POINT.
2159 Also set each group pressure limit for POINT. */
2160 for (pci = 0; pci < ira_pressure_classes_num; pci++)
2161 {
2162 cl = ira_pressure_classes[pci];
2163 model_start_update_pressure (&model_before_pressure,
2164 point, pci, delta[cl]);
2165 }
2166
2167 /* Walk the model schedule backwards, starting immediately before POINT. */
2168 print_p = false;
2169 if (point != model_curr_point)
2170 do
2171 {
2172 point--;
2173 insn = MODEL_INSN (point);
2174 queue = QUEUE_INDEX (insn);
2175
2176 if (queue != QUEUE_SCHEDULED)
2177 {
2178 /* DELTA describes the effect of the move on the register pressure
2179 after POINT. Make it describe the effect on the pressure
2180 before POINT. */
2181 i = 0;
2182 while (i < num_uses)
2183 {
2184 if (uses[i].last_use == point)
2185 {
2186 /* This register is now live again. */
2187 mark_regno_birth_or_death (NULL, delta,
2188 uses[i].regno, true);
2189
2190 /* Remove this use from the array. */
2191 uses[i] = uses[num_uses - 1];
2192 num_uses--;
2193 num_pending_births--;
2194 }
2195 else
2196 i++;
2197 }
2198
2199 if (sched_verbose >= 5)
2200 {
2201 if (!print_p)
2202 {
2203 fprintf (sched_dump, MODEL_BAR);
2204 fprintf (sched_dump, ";;\t\t| New pressure for model"
2205 " schedule\n");
2206 fprintf (sched_dump, MODEL_BAR);
2207 print_p = true;
2208 }
2209
2210 fprintf (sched_dump, ";;\t\t| %3d %4d %-30s ",
2211 point, INSN_UID (insn),
2212 str_pattern_slim (PATTERN (insn)));
2213 for (pci = 0; pci < ira_pressure_classes_num; pci++)
2214 {
2215 cl = ira_pressure_classes[pci];
2216 ref_pressure = MODEL_REF_PRESSURE (&model_before_pressure,
2217 point, pci);
2218 fprintf (sched_dump, " %s:[%d->%d]",
2219 reg_class_names[ira_pressure_classes[pci]],
2220 ref_pressure, ref_pressure + delta[cl]);
2221 }
2222 fprintf (sched_dump, "\n");
2223 }
2224 }
2225
2226 /* Adjust the pressure at POINT. Set MIX to nonzero if POINT - 1
2227 might have changed as well. */
2228 mix = num_pending_births;
2229 for (pci = 0; pci < ira_pressure_classes_num; pci++)
2230 {
2231 cl = ira_pressure_classes[pci];
2232 mix |= delta[cl];
2233 mix |= model_update_pressure (&model_before_pressure,
2234 point, pci, delta[cl]);
2235 }
2236 }
2237 while (mix && point > model_curr_point);
2238
2239 if (print_p)
2240 fprintf (sched_dump, MODEL_BAR);
2241}
2242
2243/* After DEP, which was cancelled, has been resolved for insn NEXT,
2244 check whether the insn's pattern needs restoring. */
2245static bool
2246must_restore_pattern_p (rtx_insn *next, dep_t dep)
2247{
2248 if (QUEUE_INDEX (next) == QUEUE_SCHEDULED)
2249 return false;
2250
2251 if (DEP_TYPE (dep) == REG_DEP_CONTROL)
2252 {
2253 gcc_assert (ORIG_PAT (next) != NULL_RTX);
2254 gcc_assert (next == DEP_CON (dep));
2255 }
2256 else
2257 {
2258 struct dep_replacement *desc = DEP_REPLACE (dep);
2259 if (desc->insn != next)
2260 {
2261 gcc_assert (*desc->loc == desc->orig);
2262 return false;
2263 }
2264 }
2265 return true;
2266}
2267
2268/* model_spill_cost (CL, P, P') returns the cost of increasing the
2269 pressure on CL from P to P'. We use this to calculate a "base ECC",
2270 baseECC (CL, X), for each pressure class CL and each instruction X.
2271 Supposing X changes the pressure on CL from P to P', and that the
2272 maximum pressure on CL in the current model schedule is MP', then:
2273
2274 * if X occurs before or at the next point of maximum pressure in
2275 the model schedule and P' > MP', then:
2276
2277 baseECC (CL, X) = model_spill_cost (CL, MP, P')
2278
2279 The idea is that the pressure after scheduling a fixed set of
2280 instructions -- in this case, the set up to and including the
2281 next maximum pressure point -- is going to be the same regardless
2282 of the order; we simply want to keep the intermediate pressure
2283 under control. Thus X has a cost of zero unless scheduling it
2284 now would exceed MP'.
2285
2286 If all increases in the set are by the same amount, no zero-cost
2287 instruction will ever cause the pressure to exceed MP'. However,
2288 if X is instead moved past an instruction X' with pressure in the
2289 range (MP' - (P' - P), MP'), the pressure at X' will increase
2290 beyond MP'. Since baseECC is very much a heuristic anyway,
2291 it doesn't seem worth the overhead of tracking cases like these.
2292
2293 The cost of exceeding MP' is always based on the original maximum
2294 pressure MP. This is so that going 2 registers over the original
2295 limit has the same cost regardless of whether it comes from two
2296 separate +1 deltas or from a single +2 delta.
2297
2298 * if X occurs after the next point of maximum pressure in the model
2299 schedule and P' > P, then:
2300
2301 baseECC (CL, X) = model_spill_cost (CL, MP, MP' + (P' - P))
2302
2303 That is, if we move X forward across a point of maximum pressure,
2304 and if X increases the pressure by P' - P, then we conservatively
2305 assume that scheduling X next would increase the maximum pressure
2306 by P' - P. Again, the cost of doing this is based on the original
2307 maximum pressure MP, for the same reason as above.
2308
2309 * if P' < P, P > MP, and X occurs at or after the next point of
2310 maximum pressure, then:
2311
2312 baseECC (CL, X) = -model_spill_cost (CL, MAX (MP, P'), P)
2313
2314 That is, if we have already exceeded the original maximum pressure MP,
2315 and if X might reduce the maximum pressure again -- or at least push
2316 it further back, and thus allow more scheduling freedom -- it is given
2317 a negative cost to reflect the improvement.
2318
2319 * otherwise,
2320
2321 baseECC (CL, X) = 0
2322
2323 In this case, X is not expected to affect the maximum pressure MP',
2324 so it has zero cost.
2325
2326 We then create a combined value baseECC (X) that is the sum of
2327 baseECC (CL, X) for each pressure class CL.
2328
2329 baseECC (X) could itself be used as the ECC value described above.
2330 However, this is often too conservative, in the sense that it
2331 tends to make high-priority instructions that increase pressure
2332 wait too long in cases where introducing a spill would be better.
2333 For this reason the final ECC is a priority-adjusted form of
2334 baseECC (X). Specifically, we calculate:
2335
2336 P (X) = INSN_PRIORITY (X) - insn_delay (X) - baseECC (X)
2337 baseP = MAX { P (X) | baseECC (X) <= 0 }
2338
2339 Then:
2340
2341 ECC (X) = MAX (MIN (baseP - P (X), baseECC (X)), 0)
2342
2343 Thus an instruction's effect on pressure is ignored if it has a high
2344 enough priority relative to the ones that don't increase pressure.
2345 Negative values of baseECC (X) do not increase the priority of X
2346 itself, but they do make it harder for other instructions to
2347 increase the pressure further.
2348
2349 This pressure cost is deliberately timid. The intention has been
2350 to choose a heuristic that rarely interferes with the normal list
2351 scheduler in cases where that scheduler would produce good code.
2352 We simply want to curb some of its worst excesses. */
2353
2354/* Return the cost of increasing the pressure in class CL from FROM to TO.
2355
2356 Here we use the very simplistic cost model that every register above
2357 sched_class_regs_num[CL] has a spill cost of 1. We could use other
2358 measures instead, such as one based on MEMORY_MOVE_COST. However:
2359
2360 (1) In order for an instruction to be scheduled, the higher cost
2361 would need to be justified in a single saving of that many stalls.
2362 This is overly pessimistic, because the benefit of spilling is
2363 often to avoid a sequence of several short stalls rather than
2364 a single long one.
2365
2366 (2) The cost is still arbitrary. Because we are not allocating
2367 registers during scheduling, we have no way of knowing for
2368 sure how many memory accesses will be required by each spill,
2369 where the spills will be placed within the block, or even
2370 which block(s) will contain the spills.
2371
2372 So a higher cost than 1 is often too conservative in practice,
2373 forcing blocks to contain unnecessary stalls instead of spill code.
2374 The simple cost below seems to be the best compromise. It reduces
2375 the interference with the normal list scheduler, which helps make
2376 it more suitable for a default-on option. */
2377
2378static int
2379model_spill_cost (int cl, int from, int to)
2380{
2381 from = MAX (from, sched_class_regs_num[cl]);
2382 return MAX (to, from) - from;
2383}
2384
2385/* Return baseECC (ira_pressure_classes[PCI], POINT), given that
2386 P = curr_reg_pressure[ira_pressure_classes[PCI]] and that
2387 P' = P + DELTA. */
2388
2389static int
2390model_excess_group_cost (struct model_pressure_group *group,
2391 int point, int pci, int delta)
2392{
2393 int pressure, cl;
2394
2395 cl = ira_pressure_classes[pci];
2396 if (delta < 0 && point >= group->limits[pci].point)
2397 {
2398 pressure = MAX (group->limits[pci].orig_pressure,
2399 curr_reg_pressure[cl] + delta);
2400 return -model_spill_cost (cl, pressure, curr_reg_pressure[cl]);
2401 }
2402
2403 if (delta > 0)
2404 {
2405 if (point > group->limits[pci].point)
2406 pressure = group->limits[pci].pressure + delta;
2407 else
2408 pressure = curr_reg_pressure[cl] + delta;
2409
2410 if (pressure > group->limits[pci].pressure)
2411 return model_spill_cost (cl, group->limits[pci].orig_pressure,
2412 pressure);
2413 }
2414
2415 return 0;
2416}
2417
2418/* Return baseECC (MODEL_INSN (INSN)). Dump the costs to sched_dump
2419 if PRINT_P. */
2420
2421static int
2422model_excess_cost (rtx_insn *insn, bool print_p)
2423{
2424 int point, pci, cl, cost, this_cost, delta;
2425 struct reg_pressure_data *insn_reg_pressure;
2426 int insn_death[N_REG_CLASSES];
2427
2428 calculate_reg_deaths (insn, insn_death);
2429 point = model_index (insn);
2430 insn_reg_pressure = INSN_REG_PRESSURE (insn);
2431 cost = 0;
2432
2433 if (print_p)
2434 fprintf (sched_dump, ";;\t\t| %3d %4d | %4d %+3d |", point,
2435 INSN_UID (insn), INSN_PRIORITY (insn), insn_delay (insn));
2436
2437 /* Sum up the individual costs for each register class. */
2438 for (pci = 0; pci < ira_pressure_classes_num; pci++)
2439 {
2440 cl = ira_pressure_classes[pci];
2441 delta = insn_reg_pressure[pci].set_increase - insn_death[cl];
2442 this_cost = model_excess_group_cost (&model_before_pressure,
2443 point, pci, delta);
2444 cost += this_cost;
2445 if (print_p)
2446 fprintf (sched_dump, " %s:[%d base cost %d]",
2447 reg_class_names[cl], delta, this_cost);
2448 }
2449
2450 if (print_p)
2451 fprintf (sched_dump, "\n");
2452
2453 return cost;
2454}
2455
2456/* Dump the next points of maximum pressure for GROUP. */
2457
2458static void
2459model_dump_pressure_points (struct model_pressure_group *group)
2460{
2461 int pci, cl;
2462
2463 fprintf (sched_dump, ";;\t\t| pressure points");
2464 for (pci = 0; pci < ira_pressure_classes_num; pci++)
2465 {
2466 cl = ira_pressure_classes[pci];
2467 fprintf (sched_dump, " %s:[%d->%d at ", reg_class_names[cl],
2468 curr_reg_pressure[cl], group->limits[pci].pressure);
2469 if (group->limits[pci].point < model_num_insns)
2470 fprintf (sched_dump, "%d:%d]", group->limits[pci].point,
2471 INSN_UID (MODEL_INSN (group->limits[pci].point)));
2472 else
2473 fprintf (sched_dump, "end]");
2474 }
2475 fprintf (sched_dump, "\n");
2476}
2477
2478/* Set INSN_REG_PRESSURE_EXCESS_COST_CHANGE for INSNS[0...COUNT-1]. */
2479
2480static void
2481model_set_excess_costs (rtx_insn **insns, int count)
2482{
2483 int i, cost, priority_base, priority;
2484 bool print_p;
2485
2486 /* Record the baseECC value for each instruction in the model schedule,
2487 except that negative costs are converted to zero ones now rather than
2488 later. Do not assign a cost to debug instructions, since they must
2489 not change code-generation decisions. Experiments suggest we also
2490 get better results by not assigning a cost to instructions from
2491 a different block.
2492
2493 Set PRIORITY_BASE to baseP in the block comment above. This is the
2494 maximum priority of the "cheap" instructions, which should always
2495 include the next model instruction. */
2496 priority_base = 0;
2497 print_p = false;
2498 for (i = 0; i < count; i++)
2499 if (INSN_MODEL_INDEX (insns[i]))
2500 {
2501 if (sched_verbose >= 6 && !print_p)
2502 {
2503 fprintf (sched_dump, MODEL_BAR);
2504 fprintf (sched_dump, ";;\t\t| Pressure costs for ready queue\n");
2505 model_dump_pressure_points (&model_before_pressure);
2506 fprintf (sched_dump, MODEL_BAR);
2507 print_p = true;
2508 }
2509 cost = model_excess_cost (insns[i], print_p);
2510 if (cost <= 0)
2511 {
2512 priority = INSN_PRIORITY (insns[i]) - insn_delay (insns[i]) - cost;
2513 priority_base = MAX (priority_base, priority);
2514 cost = 0;
2515 }
2516 INSN_REG_PRESSURE_EXCESS_COST_CHANGE (insns[i]) = cost;
2517 }
2518 if (print_p)
2519 fprintf (sched_dump, MODEL_BAR);
2520
2521 /* Use MAX (baseECC, 0) and baseP to calculcate ECC for each
2522 instruction. */
2523 for (i = 0; i < count; i++)
2524 {
2525 cost = INSN_REG_PRESSURE_EXCESS_COST_CHANGE (insns[i]);
2526 priority = INSN_PRIORITY (insns[i]) - insn_delay (insns[i]);
2527 if (cost > 0 && priority > priority_base)
2528 {
2529 cost += priority_base - priority;
2530 INSN_REG_PRESSURE_EXCESS_COST_CHANGE (insns[i]) = MAX (cost, 0);
2531 }
2532 }
2533}
2534
2535
2536/* Enum of rank_for_schedule heuristic decisions. */
2537enum rfs_decision {
2538 RFS_LIVE_RANGE_SHRINK1, RFS_LIVE_RANGE_SHRINK2,
2539 RFS_SCHED_GROUP, RFS_PRESSURE_DELAY, RFS_PRESSURE_TICK,
2540 RFS_FEEDS_BACKTRACK_INSN, RFS_PRIORITY, RFS_SPECULATION,
2541 RFS_SCHED_RANK, RFS_LAST_INSN, RFS_PRESSURE_INDEX,
2542 RFS_DEP_COUNT, RFS_TIE, RFS_FUSION, RFS_N };
2543
2544/* Corresponding strings for print outs. */
2545static const char *rfs_str[RFS_N] = {
2546 "RFS_LIVE_RANGE_SHRINK1", "RFS_LIVE_RANGE_SHRINK2",
2547 "RFS_SCHED_GROUP", "RFS_PRESSURE_DELAY", "RFS_PRESSURE_TICK",
2548 "RFS_FEEDS_BACKTRACK_INSN", "RFS_PRIORITY", "RFS_SPECULATION",
2549 "RFS_SCHED_RANK", "RFS_LAST_INSN", "RFS_PRESSURE_INDEX",
2550 "RFS_DEP_COUNT", "RFS_TIE", "RFS_FUSION" };
2551
2552/* Statistical breakdown of rank_for_schedule decisions. */
2553struct rank_for_schedule_stats_t { unsigned stats[RFS_N]; };
2554static rank_for_schedule_stats_t rank_for_schedule_stats;
2555
2556/* Return the result of comparing insns TMP and TMP2 and update
2557 Rank_For_Schedule statistics. */
2558static int
2559rfs_result (enum rfs_decision decision, int result, rtx tmp, rtx tmp2)
2560{
2561 ++rank_for_schedule_stats.stats[decision];
2562 if (result < 0)
2563 INSN_LAST_RFS_WIN (tmp) = decision;
2564 else if (result > 0)
2565 INSN_LAST_RFS_WIN (tmp2) = decision;
2566 else
2567 gcc_unreachable ();
2568 return result;
2569}
2570
2571/* Sorting predicate to move DEBUG_INSNs to the top of ready list, while
2572 keeping normal insns in original order. */
2573
2574static int
2575rank_for_schedule_debug (const void *x, const void *y)
2576{
2577 rtx_insn *tmp = *(rtx_insn * const *) y;
2578 rtx_insn *tmp2 = *(rtx_insn * const *) x;
2579
2580 /* Schedule debug insns as early as possible. */
2581 if (DEBUG_INSN_P (tmp) && !DEBUG_INSN_P (tmp2))
2582 return -1;
2583 else if (!DEBUG_INSN_P (tmp) && DEBUG_INSN_P (tmp2))
2584 return 1;
2585 else if (DEBUG_INSN_P (tmp) && DEBUG_INSN_P (tmp2))
2586 return INSN_LUID (tmp) - INSN_LUID (tmp2);
2587 else
2588 return INSN_RFS_DEBUG_ORIG_ORDER (tmp2) - INSN_RFS_DEBUG_ORIG_ORDER (tmp);
2589}
2590
2591/* Returns a positive value if x is preferred; returns a negative value if
2592 y is preferred. Should never return 0, since that will make the sort
2593 unstable. */
2594
2595static int
2596rank_for_schedule (const void *x, const void *y)
2597{
2598 rtx_insn *tmp = *(rtx_insn * const *) y;
2599 rtx_insn *tmp2 = *(rtx_insn * const *) x;
2600 int tmp_class, tmp2_class;
2601 int val, priority_val, info_val, diff;
2602
2603 if (live_range_shrinkage_p)
2604 {
2605 /* Don't use SCHED_PRESSURE_MODEL -- it results in much worse
2606 code. */
2607 gcc_assert (sched_pressure == SCHED_PRESSURE_WEIGHTED);
2608 if ((INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp) < 0
2609 || INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp2) < 0)
2610 && (diff = (INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp)
2611 - INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp2))) != 0)
2612 return rfs_result (RFS_LIVE_RANGE_SHRINK1, diff, tmp, tmp2);
2613 /* Sort by INSN_LUID (original insn order), so that we make the
2614 sort stable. This minimizes instruction movement, thus
2615 minimizing sched's effect on debugging and cross-jumping. */
2616 return rfs_result (RFS_LIVE_RANGE_SHRINK2,
2617 INSN_LUID (tmp) - INSN_LUID (tmp2), tmp, tmp2);
2618 }
2619
2620 /* The insn in a schedule group should be issued the first. */
2621 if (flag_sched_group_heuristic &&
2622 SCHED_GROUP_P (tmp) != SCHED_GROUP_P (tmp2))
2623 return rfs_result (RFS_SCHED_GROUP, SCHED_GROUP_P (tmp2) ? 1 : -1,
2624 tmp, tmp2);
2625
2626 /* Make sure that priority of TMP and TMP2 are initialized. */
2627 gcc_assert (INSN_PRIORITY_KNOWN (tmp) && INSN_PRIORITY_KNOWN (tmp2));
2628
2629 if (sched_fusion)
2630 {
2631 /* The instruction that has the same fusion priority as the last
2632 instruction is the instruction we picked next. If that is not
2633 the case, we sort ready list firstly by fusion priority, then
2634 by priority, and at last by INSN_LUID. */
2635 int a = INSN_FUSION_PRIORITY (tmp);
2636 int b = INSN_FUSION_PRIORITY (tmp2);
2637 int last = -1;
2638
2639 if (last_nondebug_scheduled_insn
2640 && !NOTE_P (last_nondebug_scheduled_insn)
2641 && BLOCK_FOR_INSN (tmp)
2642 == BLOCK_FOR_INSN (last_nondebug_scheduled_insn))
2643 last = INSN_FUSION_PRIORITY (last_nondebug_scheduled_insn);
2644
2645 if (a != last && b != last)
2646 {
2647 if (a == b)
2648 {
2649 a = INSN_PRIORITY (tmp);
2650 b = INSN_PRIORITY (tmp2);
2651 }
2652 if (a != b)
2653 return rfs_result (RFS_FUSION, b - a, tmp, tmp2);
2654 else
2655 return rfs_result (RFS_FUSION,
2656 INSN_LUID (tmp) - INSN_LUID (tmp2), tmp, tmp2);
2657 }
2658 else if (a == b)
2659 {
2660 gcc_assert (last_nondebug_scheduled_insn
2661 && !NOTE_P (last_nondebug_scheduled_insn));
2662 last = INSN_PRIORITY (last_nondebug_scheduled_insn);
2663
2664 a = abs (INSN_PRIORITY (tmp) - last);
2665 b = abs (INSN_PRIORITY (tmp2) - last);
2666 if (a != b)
2667 return rfs_result (RFS_FUSION, a - b, tmp, tmp2);
2668 else
2669 return rfs_result (RFS_FUSION,
2670 INSN_LUID (tmp) - INSN_LUID (tmp2), tmp, tmp2);
2671 }
2672 else if (a == last)
2673 return rfs_result (RFS_FUSION, -1, tmp, tmp2);
2674 else
2675 return rfs_result (RFS_FUSION, 1, tmp, tmp2);
2676 }
2677
2678 if (sched_pressure != SCHED_PRESSURE_NONE)
2679 {
2680 /* Prefer insn whose scheduling results in the smallest register
2681 pressure excess. */
2682 if ((diff = (INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp)
2683 + insn_delay (tmp)
2684 - INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp2)
2685 - insn_delay (tmp2))))
2686 return rfs_result (RFS_PRESSURE_DELAY, diff, tmp, tmp2);
2687 }
2688
2689 if (sched_pressure != SCHED_PRESSURE_NONE
2690 && (INSN_TICK (tmp2) > clock_var || INSN_TICK (tmp) > clock_var)
2691 && INSN_TICK (tmp2) != INSN_TICK (tmp))
2692 {
2693 diff = INSN_TICK (tmp) - INSN_TICK (tmp2);
2694 return rfs_result (RFS_PRESSURE_TICK, diff, tmp, tmp2);
2695 }
2696
2697 /* If we are doing backtracking in this schedule, prefer insns that
2698 have forward dependencies with negative cost against an insn that
2699 was already scheduled. */
2700 if (current_sched_info->flags & DO_BACKTRACKING)
2701 {
2702 priority_val = FEEDS_BACKTRACK_INSN (tmp2) - FEEDS_BACKTRACK_INSN (tmp);
2703 if (priority_val)
2704 return rfs_result (RFS_FEEDS_BACKTRACK_INSN, priority_val, tmp, tmp2);
2705 }
2706
2707 /* Prefer insn with higher priority. */
2708 priority_val = INSN_PRIORITY (tmp2) - INSN_PRIORITY (tmp);
2709
2710 if (flag_sched_critical_path_heuristic && priority_val)
2711 return rfs_result (RFS_PRIORITY, priority_val, tmp, tmp2);
2712
2713 if (PARAM_VALUE (PARAM_SCHED_AUTOPREF_QUEUE_DEPTH) >= 0)
2714 {
2715 int autopref = autopref_rank_for_schedule (tmp, tmp2);
2716 if (autopref != 0)
2717 return autopref;
2718 }
2719
2720 /* Prefer speculative insn with greater dependencies weakness. */
2721 if (flag_sched_spec_insn_heuristic && spec_info)
2722 {
2723 ds_t ds1, ds2;
2724 dw_t dw1, dw2;
2725 int dw;
2726
2727 ds1 = TODO_SPEC (tmp) & SPECULATIVE;
2728 if (ds1)
2729 dw1 = ds_weak (ds1);
2730 else
2731 dw1 = NO_DEP_WEAK;
2732
2733 ds2 = TODO_SPEC (tmp2) & SPECULATIVE;
2734 if (ds2)
2735 dw2 = ds_weak (ds2);
2736 else
2737 dw2 = NO_DEP_WEAK;
2738
2739 dw = dw2 - dw1;
2740 if (dw > (NO_DEP_WEAK / 8) || dw < -(NO_DEP_WEAK / 8))
2741 return rfs_result (RFS_SPECULATION, dw, tmp, tmp2);
2742 }
2743
2744 info_val = (*current_sched_info->rank) (tmp, tmp2);
2745 if (flag_sched_rank_heuristic && info_val)
2746 return rfs_result (RFS_SCHED_RANK, info_val, tmp, tmp2);
2747
2748 /* Compare insns based on their relation to the last scheduled
2749 non-debug insn. */
2750 if (flag_sched_last_insn_heuristic && last_nondebug_scheduled_insn)
2751 {
2752 dep_t dep1;
2753 dep_t dep2;
2754 rtx_insn *last = last_nondebug_scheduled_insn;
2755
2756 /* Classify the instructions into three classes:
2757 1) Data dependent on last schedule insn.
2758 2) Anti/Output dependent on last scheduled insn.
2759 3) Independent of last scheduled insn, or has latency of one.
2760 Choose the insn from the highest numbered class if different. */
2761 dep1 = sd_find_dep_between (last, tmp, true);
2762
2763 if (dep1 == NULL || dep_cost (dep1) == 1)
2764 tmp_class = 3;
2765 else if (/* Data dependence. */
2766 DEP_TYPE (dep1) == REG_DEP_TRUE)
2767 tmp_class = 1;
2768 else
2769 tmp_class = 2;
2770
2771 dep2 = sd_find_dep_between (last, tmp2, true);
2772
2773 if (dep2 == NULL || dep_cost (dep2) == 1)
2774 tmp2_class = 3;
2775 else if (/* Data dependence. */
2776 DEP_TYPE (dep2) == REG_DEP_TRUE)
2777 tmp2_class = 1;
2778 else
2779 tmp2_class = 2;
2780
2781 if ((val = tmp2_class - tmp_class))
2782 return rfs_result (RFS_LAST_INSN, val, tmp, tmp2);
2783 }
2784
2785 /* Prefer instructions that occur earlier in the model schedule. */
2786 if (sched_pressure == SCHED_PRESSURE_MODEL
2787 && INSN_BB (tmp) == target_bb && INSN_BB (tmp2) == target_bb)
2788 {
2789 diff = model_index (tmp) - model_index (tmp2);
2790 gcc_assert (diff != 0);
2791 return rfs_result (RFS_PRESSURE_INDEX, diff, tmp, tmp2);
2792 }
2793
2794 /* Prefer the insn which has more later insns that depend on it.
2795 This gives the scheduler more freedom when scheduling later
2796 instructions at the expense of added register pressure. */
2797
2798 val = (dep_list_size (tmp2, SD_LIST_FORW)
2799 - dep_list_size (tmp, SD_LIST_FORW));
2800
2801 if (flag_sched_dep_count_heuristic && val != 0)
2802 return rfs_result (RFS_DEP_COUNT, val, tmp, tmp2);
2803
2804 /* If insns are equally good, sort by INSN_LUID (original insn order),
2805 so that we make the sort stable. This minimizes instruction movement,
2806 thus minimizing sched's effect on debugging and cross-jumping. */
2807 return rfs_result (RFS_TIE, INSN_LUID (tmp) - INSN_LUID (tmp2), tmp, tmp2);
2808}
2809
2810/* Resort the array A in which only element at index N may be out of order. */
2811
2812HAIFA_INLINE static void
2813swap_sort (rtx_insn **a, int n)
2814{
2815 rtx_insn *insn = a[n - 1];
2816 int i = n - 2;
2817
2818 while (i >= 0 && rank_for_schedule (a + i, &insn) >= 0)
2819 {
2820 a[i + 1] = a[i];
2821 i -= 1;
2822 }
2823 a[i + 1] = insn;
2824}
2825
2826/* Add INSN to the insn queue so that it can be executed at least
2827 N_CYCLES after the currently executing insn. Preserve insns
2828 chain for debugging purposes. REASON will be printed in debugging
2829 output. */
2830
2831HAIFA_INLINE static void
2832queue_insn (rtx_insn *insn, int n_cycles, const char *reason)
2833{
2834 int next_q = NEXT_Q_AFTER (q_ptr, n_cycles);
2835 rtx_insn_list *link = alloc_INSN_LIST (insn, insn_queue[next_q]);
2836 int new_tick;
2837
2838 gcc_assert (n_cycles <= max_insn_queue_index);
2839 gcc_assert (!DEBUG_INSN_P (insn));
2840
2841 insn_queue[next_q] = link;
2842 q_size += 1;
2843
2844 if (sched_verbose >= 2)
2845 {
2846 fprintf (sched_dump, ";;\t\tReady-->Q: insn %s: ",
2847 (*current_sched_info->print_insn) (insn, 0));
2848
2849 fprintf (sched_dump, "queued for %d cycles (%s).\n", n_cycles, reason);
2850 }
2851
2852 QUEUE_INDEX (insn) = next_q;
2853
2854 if (current_sched_info->flags & DO_BACKTRACKING)
2855 {
2856 new_tick = clock_var + n_cycles;
2857 if (INSN_TICK (insn) == INVALID_TICK || INSN_TICK (insn) < new_tick)
2858 INSN_TICK (insn) = new_tick;
2859
2860 if (INSN_EXACT_TICK (insn) != INVALID_TICK
2861 && INSN_EXACT_TICK (insn) < clock_var + n_cycles)
2862 {
2863 must_backtrack = true;
2864 if (sched_verbose >= 2)
2865 fprintf (sched_dump, ";;\t\tcausing a backtrack.\n");
2866 }
2867 }
2868}
2869
2870/* Remove INSN from queue. */
2871static void
2872queue_remove (rtx_insn *insn)
2873{
2874 gcc_assert (QUEUE_INDEX (insn) >= 0);
2875 remove_free_INSN_LIST_elem (insn, &insn_queue[QUEUE_INDEX (insn)]);
2876 q_size--;
2877 QUEUE_INDEX (insn) = QUEUE_NOWHERE;
2878}
2879
2880/* Return a pointer to the bottom of the ready list, i.e. the insn
2881 with the lowest priority. */
2882
2883rtx_insn **
2884ready_lastpos (struct ready_list *ready)
2885{
2886 gcc_assert (ready->n_ready >= 1);
2887 return ready->vec + ready->first - ready->n_ready + 1;
2888}
2889
2890/* Add an element INSN to the ready list so that it ends up with the
2891 lowest/highest priority depending on FIRST_P. */
2892
2893HAIFA_INLINE static void
2894ready_add (struct ready_list *ready, rtx_insn *insn, bool first_p)
2895{
2896 if (!first_p)
2897 {
2898 if (ready->first == ready->n_ready)
2899 {
2900 memmove (ready->vec + ready->veclen - ready->n_ready,
2901 ready_lastpos (ready),
2902 ready->n_ready * sizeof (rtx));
2903 ready->first = ready->veclen - 1;
2904 }
2905 ready->vec[ready->first - ready->n_ready] = insn;
2906 }
2907 else
2908 {
2909 if (ready->first == ready->veclen - 1)
2910 {
2911 if (ready->n_ready)
2912 /* ready_lastpos() fails when called with (ready->n_ready == 0). */
2913 memmove (ready->vec + ready->veclen - ready->n_ready - 1,
2914 ready_lastpos (ready),
2915 ready->n_ready * sizeof (rtx));
2916 ready->first = ready->veclen - 2;
2917 }
2918 ready->vec[++(ready->first)] = insn;
2919 }
2920
2921 ready->n_ready++;
2922 if (DEBUG_INSN_P (insn))
2923 ready->n_debug++;
2924
2925 gcc_assert (QUEUE_INDEX (insn) != QUEUE_READY);
2926 QUEUE_INDEX (insn) = QUEUE_READY;
2927
2928 if (INSN_EXACT_TICK (insn) != INVALID_TICK
2929 && INSN_EXACT_TICK (insn) < clock_var)
2930 {
2931 must_backtrack = true;
2932 }
2933}
2934
2935/* Remove the element with the highest priority from the ready list and
2936 return it. */
2937
2938HAIFA_INLINE static rtx_insn *
2939ready_remove_first (struct ready_list *ready)
2940{
2941 rtx_insn *t;
2942
2943 gcc_assert (ready->n_ready);
2944 t = ready->vec[ready->first--];
2945 ready->n_ready--;
2946 if (DEBUG_INSN_P (t))
2947 ready->n_debug--;
2948 /* If the queue becomes empty, reset it. */
2949 if (ready->n_ready == 0)
2950 ready->first = ready->veclen - 1;
2951
2952 gcc_assert (QUEUE_INDEX (t) == QUEUE_READY);
2953 QUEUE_INDEX (t) = QUEUE_NOWHERE;
2954
2955 return t;
2956}
2957
2958/* The following code implements multi-pass scheduling for the first
2959 cycle. In other words, we will try to choose ready insn which
2960 permits to start maximum number of insns on the same cycle. */
2961
2962/* Return a pointer to the element INDEX from the ready. INDEX for
2963 insn with the highest priority is 0, and the lowest priority has
2964 N_READY - 1. */
2965
2966rtx_insn *
2967ready_element (struct ready_list *ready, int index)
2968{
2969 gcc_assert (ready->n_ready && index < ready->n_ready);
2970
2971 return ready->vec[ready->first - index];
2972}
2973
2974/* Remove the element INDEX from the ready list and return it. INDEX
2975 for insn with the highest priority is 0, and the lowest priority
2976 has N_READY - 1. */
2977
2978HAIFA_INLINE static rtx_insn *
2979ready_remove (struct ready_list *ready, int index)
2980{
2981 rtx_insn *t;
2982 int i;
2983
2984 if (index == 0)
2985 return ready_remove_first (ready);
2986 gcc_assert (ready->n_ready && index < ready->n_ready);
2987 t = ready->vec[ready->first - index];
2988 ready->n_ready--;
2989 if (DEBUG_INSN_P (t))
2990 ready->n_debug--;
2991 for (i = index; i < ready->n_ready; i++)
2992 ready->vec[ready->first - i] = ready->vec[ready->first - i - 1];
2993 QUEUE_INDEX (t) = QUEUE_NOWHERE;
2994 return t;
2995}
2996
2997/* Remove INSN from the ready list. */
2998static void
2999ready_remove_insn (rtx_insn *insn)
3000{
3001 int i;
3002
3003 for (i = 0; i < readyp->n_ready; i++)
3004 if (ready_element (readyp, i) == insn)
3005 {
3006 ready_remove (readyp, i);
3007 return;
3008 }
3009 gcc_unreachable ();
3010}
3011
3012/* Calculate difference of two statistics set WAS and NOW.
3013 Result returned in WAS. */
3014static void
3015rank_for_schedule_stats_diff (rank_for_schedule_stats_t *was,
3016 const rank_for_schedule_stats_t *now)
3017{
3018 for (int i = 0; i < RFS_N; ++i)
3019 was->stats[i] = now->stats[i] - was->stats[i];
3020}
3021
3022/* Print rank_for_schedule statistics. */
3023static void
3024print_rank_for_schedule_stats (const char *prefix,
3025 const rank_for_schedule_stats_t *stats,
3026 struct ready_list *ready)
3027{
3028 for (int i = 0; i < RFS_N; ++i)
3029 if (stats->stats[i])
3030 {
3031 fprintf (sched_dump, "%s%20s: %u", prefix, rfs_str[i], stats->stats[i]);
3032
3033 if (ready != NULL)
3034 /* Print out insns that won due to RFS_<I>. */
3035 {
3036 rtx_insn **p = ready_lastpos (ready);
3037
3038 fprintf (sched_dump, ":");
3039 /* Start with 1 since least-priority insn didn't have any wins. */
3040 for (int j = 1; j < ready->n_ready; ++j)
3041 if (INSN_LAST_RFS_WIN (p[j]) == i)
3042 fprintf (sched_dump, " %s",
3043 (*current_sched_info->print_insn) (p[j], 0));
3044 }
3045 fprintf (sched_dump, "\n");
3046 }
3047}
3048
3049/* Separate DEBUG_INSNS from normal insns. DEBUG_INSNs go to the end
3050 of array. */
3051static void
3052ready_sort_debug (struct ready_list *ready)
3053{
3054 int i;
3055 rtx_insn **first = ready_lastpos (ready);
3056
3057 for (i = 0; i < ready->n_ready; ++i)
3058 if (!DEBUG_INSN_P (first[i]))
3059 INSN_RFS_DEBUG_ORIG_ORDER (first[i]) = i;
3060
3061 qsort (first, ready->n_ready, sizeof (rtx), rank_for_schedule_debug);
3062}
3063
3064/* Sort non-debug insns in the ready list READY by ascending priority.
3065 Assumes that all debug insns are separated from the real insns. */
3066static void
3067ready_sort_real (struct ready_list *ready)
3068{
3069 int i;
3070 rtx_insn **first = ready_lastpos (ready);
3071 int n_ready_real = ready->n_ready - ready->n_debug;
3072
3073 if (sched_pressure == SCHED_PRESSURE_WEIGHTED)
3074 for (i = 0; i < n_ready_real; ++i)
3075 setup_insn_reg_pressure_info (first[i]);
3076 else if (sched_pressure == SCHED_PRESSURE_MODEL
3077 && model_curr_point < model_num_insns)
3078 model_set_excess_costs (first, n_ready_real);
3079
3080 rank_for_schedule_stats_t stats1;
3081 if (sched_verbose >= 4)
3082 stats1 = rank_for_schedule_stats;
3083
3084 if (n_ready_real == 2)
3085 swap_sort (first, n_ready_real);
3086 else if (n_ready_real > 2)
3087 qsort (first, n_ready_real, sizeof (rtx), rank_for_schedule);
3088
3089 if (sched_verbose >= 4)
3090 {
3091 rank_for_schedule_stats_diff (&stats1, &rank_for_schedule_stats);
3092 print_rank_for_schedule_stats (";;\t\t", &stats1, ready);
3093 }
3094}
3095
3096/* Sort the ready list READY by ascending priority. */
3097static void
3098ready_sort (struct ready_list *ready)
3099{
3100 if (ready->n_debug > 0)
3101 ready_sort_debug (ready);
3102 else
3103 ready_sort_real (ready);
3104}
3105
3106/* PREV is an insn that is ready to execute. Adjust its priority if that
3107 will help shorten or lengthen register lifetimes as appropriate. Also
3108 provide a hook for the target to tweak itself. */
3109
3110HAIFA_INLINE static void
3111adjust_priority (rtx_insn *prev)
3112{
3113 /* ??? There used to be code here to try and estimate how an insn
3114 affected register lifetimes, but it did it by looking at REG_DEAD
3115 notes, which we removed in schedule_region. Nor did it try to
3116 take into account register pressure or anything useful like that.
3117
3118 Revisit when we have a machine model to work with and not before. */
3119
3120 if (targetm.sched.adjust_priority)
3121 INSN_PRIORITY (prev) =
3122 targetm.sched.adjust_priority (prev, INSN_PRIORITY (prev));
3123}
3124
3125/* Advance DFA state STATE on one cycle. */
3126void
3127advance_state (state_t state)
3128{
3129 if (targetm.sched.dfa_pre_advance_cycle)
3130 targetm.sched.dfa_pre_advance_cycle ();
3131
3132 if (targetm.sched.dfa_pre_cycle_insn)
3133 state_transition (state,
3134 targetm.sched.dfa_pre_cycle_insn ());
3135
3136 state_transition (state, NULL);
3137
3138 if (targetm.sched.dfa_post_cycle_insn)
3139 state_transition (state,
3140 targetm.sched.dfa_post_cycle_insn ());
3141
3142 if (targetm.sched.dfa_post_advance_cycle)
3143 targetm.sched.dfa_post_advance_cycle ();
3144}
3145
3146/* Advance time on one cycle. */
3147HAIFA_INLINE static void
3148advance_one_cycle (void)
3149{
3150 advance_state (curr_state);
3151 if (sched_verbose >= 4)
3152 fprintf (sched_dump, ";;\tAdvance the current state.\n");
3153}
3154
3155/* Update register pressure after scheduling INSN. */
3156static void
3157update_register_pressure (rtx_insn *insn)
3158{
3159 struct reg_use_data *use;
3160 struct reg_set_data *set;
3161
3162 gcc_checking_assert (!DEBUG_INSN_P (insn));
3163
3164 for (use = INSN_REG_USE_LIST (insn); use != NULL; use = use->next_insn_use)
3165 if (dying_use_p (use))
3166 mark_regno_birth_or_death (curr_reg_live, curr_reg_pressure,
3167 use->regno, false);
3168 for (set = INSN_REG_SET_LIST (insn); set != NULL; set = set->next_insn_set)
3169 mark_regno_birth_or_death (curr_reg_live, curr_reg_pressure,
3170 set->regno, true);
3171}
3172
3173/* Set up or update (if UPDATE_P) max register pressure (see its
3174 meaning in sched-int.h::_haifa_insn_data) for all current BB insns
3175 after insn AFTER. */
3176static void
3177setup_insn_max_reg_pressure (rtx_insn *after, bool update_p)
3178{
3179 int i, p;
3180 bool eq_p;
3181 rtx_insn *insn;
3182 static int max_reg_pressure[N_REG_CLASSES];
3183
3184 save_reg_pressure ();
3185 for (i = 0; i < ira_pressure_classes_num; i++)
3186 max_reg_pressure[ira_pressure_classes[i]]
3187 = curr_reg_pressure[ira_pressure_classes[i]];
3188 for (insn = NEXT_INSN (after);
3189 insn != NULL_RTX && ! BARRIER_P (insn)
3190 && BLOCK_FOR_INSN (insn) == BLOCK_FOR_INSN (after);
3191 insn = NEXT_INSN (insn))
3192 if (NONDEBUG_INSN_P (insn))
3193 {
3194 eq_p = true;
3195 for (i = 0; i < ira_pressure_classes_num; i++)
3196 {
3197 p = max_reg_pressure[ira_pressure_classes[i]];
3198 if (INSN_MAX_REG_PRESSURE (insn)[i] != p)
3199 {
3200 eq_p = false;
3201 INSN_MAX_REG_PRESSURE (insn)[i]
3202 = max_reg_pressure[ira_pressure_classes[i]];
3203 }
3204 }
3205 if (update_p && eq_p)
3206 break;
3207 update_register_pressure (insn);
3208 for (i = 0; i < ira_pressure_classes_num; i++)
3209 if (max_reg_pressure[ira_pressure_classes[i]]
3210 < curr_reg_pressure[ira_pressure_classes[i]])
3211 max_reg_pressure[ira_pressure_classes[i]]
3212 = curr_reg_pressure[ira_pressure_classes[i]];
3213 }
3214 restore_reg_pressure ();
3215}
3216
3217/* Update the current register pressure after scheduling INSN. Update
3218 also max register pressure for unscheduled insns of the current
3219 BB. */
3220static void
3221update_reg_and_insn_max_reg_pressure (rtx_insn *insn)
3222{
3223 int i;
3224 int before[N_REG_CLASSES];
3225
3226 for (i = 0; i < ira_pressure_classes_num; i++)
3227 before[i] = curr_reg_pressure[ira_pressure_classes[i]];
3228 update_register_pressure (insn);
3229 for (i = 0; i < ira_pressure_classes_num; i++)
3230 if (curr_reg_pressure[ira_pressure_classes[i]] != before[i])
3231 break;
3232 if (i < ira_pressure_classes_num)
3233 setup_insn_max_reg_pressure (insn, true);
3234}
3235
3236/* Set up register pressure at the beginning of basic block BB whose
3237 insns starting after insn AFTER. Set up also max register pressure
3238 for all insns of the basic block. */
3239void
3240sched_setup_bb_reg_pressure_info (basic_block bb, rtx_insn *after)
3241{
3242 gcc_assert (sched_pressure == SCHED_PRESSURE_WEIGHTED);
3243 initiate_bb_reg_pressure_info (bb);
3244 setup_insn_max_reg_pressure (after, false);
3245}
3246
3247/* If doing predication while scheduling, verify whether INSN, which
3248 has just been scheduled, clobbers the conditions of any
3249 instructions that must be predicated in order to break their
3250 dependencies. If so, remove them from the queues so that they will
3251 only be scheduled once their control dependency is resolved. */
3252
3253static void
3254check_clobbered_conditions (rtx_insn *insn)
3255{
3256 HARD_REG_SET t;
3257 int i;
3258
3259 if ((current_sched_info->flags & DO_PREDICATION) == 0)
3260 return;
3261
3262 find_all_hard_reg_sets (insn, &t, true);
3263
3264 restart:
3265 for (i = 0; i < ready.n_ready; i++)
3266 {
3267 rtx_insn *x = ready_element (&ready, i);
3268 if (TODO_SPEC (x) == DEP_CONTROL && cond_clobbered_p (x, t))
3269 {
3270 ready_remove_insn (x);
3271 goto restart;
3272 }
3273 }
3274 for (i = 0; i <= max_insn_queue_index; i++)
3275 {
3276 rtx_insn_list *link;
3277 int q = NEXT_Q_AFTER (q_ptr, i);
3278
3279 restart_queue:
3280 for (link = insn_queue[q]; link; link = link->next ())
3281 {
3282 rtx_insn *x = link->insn ();
3283 if (TODO_SPEC (x) == DEP_CONTROL && cond_clobbered_p (x, t))
3284 {
3285 queue_remove (x);
3286 goto restart_queue;
3287 }
3288 }
3289 }
3290}
3291
3292/* Return (in order):
3293
3294 - positive if INSN adversely affects the pressure on one
3295 register class
3296
3297 - negative if INSN reduces the pressure on one register class
3298
3299 - 0 if INSN doesn't affect the pressure on any register class. */
3300
3301static int
3302model_classify_pressure (struct model_insn_info *insn)
3303{
3304 struct reg_pressure_data *reg_pressure;
3305 int death[N_REG_CLASSES];
3306 int pci, cl, sum;
3307
3308 calculate_reg_deaths (insn->insn, death);
3309 reg_pressure = INSN_REG_PRESSURE (insn->insn);
3310 sum = 0;
3311 for (pci = 0; pci < ira_pressure_classes_num; pci++)
3312 {
3313 cl = ira_pressure_classes[pci];
3314 if (death[cl] < reg_pressure[pci].set_increase)
3315 return 1;
3316 sum += reg_pressure[pci].set_increase - death[cl];
3317 }
3318 return sum;
3319}
3320
3321/* Return true if INSN1 should come before INSN2 in the model schedule. */
3322
3323static int
3324model_order_p (struct model_insn_info *insn1, struct model_insn_info *insn2)
3325{
3326 unsigned int height1, height2;
3327 unsigned int priority1, priority2;
3328
3329 /* Prefer instructions with a higher model priority. */
3330 if (insn1->model_priority != insn2->model_priority)
3331 return insn1->model_priority > insn2->model_priority;
3332
3333 /* Combine the length of the longest path of satisfied true dependencies
3334 that leads to each instruction (depth) with the length of the longest
3335 path of any dependencies that leads from the instruction (alap).
3336 Prefer instructions with the greatest combined length. If the combined
3337 lengths are equal, prefer instructions with the greatest depth.
3338
3339 The idea is that, if we have a set S of "equal" instructions that each
3340 have ALAP value X, and we pick one such instruction I, any true-dependent
3341 successors of I that have ALAP value X - 1 should be preferred over S.
3342 This encourages the schedule to be "narrow" rather than "wide".
3343 However, if I is a low-priority instruction that we decided to
3344 schedule because of its model_classify_pressure, and if there
3345 is a set of higher-priority instructions T, the aforementioned
3346 successors of I should not have the edge over T. */
3347 height1 = insn1->depth + insn1->alap;
3348 height2 = insn2->depth + insn2->alap;
3349 if (height1 != height2)
3350 return height1 > height2;
3351 if (insn1->depth != insn2->depth)
3352 return insn1->depth > insn2->depth;
3353
3354 /* We have no real preference between INSN1 an INSN2 as far as attempts
3355 to reduce pressure go. Prefer instructions with higher priorities. */
3356 priority1 = INSN_PRIORITY (insn1->insn);
3357 priority2 = INSN_PRIORITY (insn2->insn);
3358 if (priority1 != priority2)
3359 return priority1 > priority2;
3360
3361 /* Use the original rtl sequence as a tie-breaker. */
3362 return insn1 < insn2;
3363}
3364
3365/* Add INSN to the model worklist immediately after PREV. Add it to the
3366 beginning of the list if PREV is null. */
3367
3368static void
3369model_add_to_worklist_at (struct model_insn_info *insn,
3370 struct model_insn_info *prev)
3371{
3372 gcc_assert (QUEUE_INDEX (insn->insn) == QUEUE_NOWHERE);
3373 QUEUE_INDEX (insn->insn) = QUEUE_READY;
3374
3375 insn->prev = prev;
3376 if (prev)
3377 {
3378 insn->next = prev->next;
3379 prev->next = insn;
3380 }
3381 else
3382 {
3383 insn->next = model_worklist;
3384 model_worklist = insn;
3385 }
3386 if (insn->next)
3387 insn->next->prev = insn;
3388}
3389
3390/* Remove INSN from the model worklist. */
3391
3392static void
3393model_remove_from_worklist (struct model_insn_info *insn)
3394{
3395 gcc_assert (QUEUE_INDEX (insn->insn) == QUEUE_READY);
3396 QUEUE_INDEX (insn->insn) = QUEUE_NOWHERE;
3397
3398 if (insn->prev)
3399 insn->prev->next = insn->next;
3400 else
3401 model_worklist = insn->next;
3402 if (insn->next)
3403 insn->next->prev = insn->prev;
3404}
3405
3406/* Add INSN to the model worklist. Start looking for a suitable position
3407 between neighbors PREV and NEXT, testing at most MAX_SCHED_READY_INSNS
3408 insns either side. A null PREV indicates the beginning of the list and
3409 a null NEXT indicates the end. */
3410
3411static void
3412model_add_to_worklist (struct model_insn_info *insn,
3413 struct model_insn_info *prev,
3414 struct model_insn_info *next)
3415{
3416 int count;
3417
3418 count = MAX_SCHED_READY_INSNS;
3419 if (count > 0 && prev && model_order_p (insn, prev))
3420 do
3421 {
3422 count--;
3423 prev = prev->prev;
3424 }
3425 while (count > 0 && prev && model_order_p (insn, prev));
3426 else
3427 while (count > 0 && next && model_order_p (next, insn))
3428 {
3429 count--;
3430 prev = next;
3431 next = next->next;
3432 }
3433 model_add_to_worklist_at (insn, prev);
3434}
3435
3436/* INSN may now have a higher priority (in the model_order_p sense)
3437 than before. Move it up the worklist if necessary. */
3438
3439static void
3440model_promote_insn (struct model_insn_info *insn)
3441{
3442 struct model_insn_info *prev;
3443 int count;
3444
3445 prev = insn->prev;
3446 count = MAX_SCHED_READY_INSNS;
3447 while (count > 0 && prev && model_order_p (insn, prev))
3448 {
3449 count--;
3450 prev = prev->prev;
3451 }
3452 if (prev != insn->prev)
3453 {
3454 model_remove_from_worklist (insn);
3455 model_add_to_worklist_at (insn, prev);
3456 }
3457}
3458
3459/* Add INSN to the end of the model schedule. */
3460
3461static void
3462model_add_to_schedule (rtx_insn *insn)
3463{
3464 unsigned int point;
3465
3466 gcc_assert (QUEUE_INDEX (insn) == QUEUE_NOWHERE);
3467 QUEUE_INDEX (insn) = QUEUE_SCHEDULED;
3468
3469 point = model_schedule.length ();
3470 model_schedule.quick_push (insn);
3471 INSN_MODEL_INDEX (insn) = point + 1;
3472}
3473
3474/* Analyze the instructions that are to be scheduled, setting up
3475 MODEL_INSN_INFO (...) and model_num_insns accordingly. Add ready
3476 instructions to model_worklist. */
3477
3478static void
3479model_analyze_insns (void)
3480{
3481 rtx_insn *start, *end, *iter;
3482 sd_iterator_def sd_it;
3483 dep_t dep;
3484 struct model_insn_info *insn, *con;
3485
3486 model_num_insns = 0;
3487 start = PREV_INSN (current_sched_info->next_tail);
3488 end = current_sched_info->prev_head;
3489 for (iter = start; iter != end; iter = PREV_INSN (iter))
3490 if (NONDEBUG_INSN_P (iter))
3491 {
3492 insn = MODEL_INSN_INFO (iter);
3493 insn->insn = iter;
3494 FOR_EACH_DEP (iter, SD_LIST_FORW, sd_it, dep)
3495 {
3496 con = MODEL_INSN_INFO (DEP_CON (dep));
3497 if (con->insn && insn->alap < con->alap + 1)
3498 insn->alap = con->alap + 1;
3499 }
3500
3501 insn->old_queue = QUEUE_INDEX (iter);
3502 QUEUE_INDEX (iter) = QUEUE_NOWHERE;
3503
3504 insn->unscheduled_preds = dep_list_size (iter, SD_LIST_HARD_BACK);
3505 if (insn->unscheduled_preds == 0)
3506 model_add_to_worklist (insn, NULL, model_worklist);
3507
3508 model_num_insns++;
3509 }
3510}
3511
3512/* The global state describes the register pressure at the start of the
3513 model schedule. Initialize GROUP accordingly. */
3514
3515static void
3516model_init_pressure_group (struct model_pressure_group *group)
3517{
3518 int pci, cl;
3519
3520 for (pci = 0; pci < ira_pressure_classes_num; pci++)
3521 {
3522 cl = ira_pressure_classes[pci];
3523 group->limits[pci].pressure = curr_reg_pressure[cl];
3524 group->limits[pci].point = 0;
3525 }
3526 /* Use index model_num_insns to record the state after the last
3527 instruction in the model schedule. */
3528 group->model = XNEWVEC (struct model_pressure_data,
3529 (model_num_insns + 1) * ira_pressure_classes_num);
3530}
3531
3532/* Record that MODEL_REF_PRESSURE (GROUP, POINT, PCI) is PRESSURE.
3533 Update the maximum pressure for the whole schedule. */
3534
3535static void
3536model_record_pressure (struct model_pressure_group *group,
3537 int point, int pci, int pressure)
3538{
3539 MODEL_REF_PRESSURE (group, point, pci) = pressure;
3540 if (group->limits[pci].pressure < pressure)
3541 {
3542 group->limits[pci].pressure = pressure;
3543 group->limits[pci].point = point;
3544 }
3545}
3546
3547/* INSN has just been added to the end of the model schedule. Record its
3548 register-pressure information. */
3549
3550static void
3551model_record_pressures (struct model_insn_info *insn)
3552{
3553 struct reg_pressure_data *reg_pressure;
3554 int point, pci, cl, delta;
3555 int death[N_REG_CLASSES];
3556
3557 point = model_index (insn->insn);
3558 if (sched_verbose >= 2)
3559 {
3560 if (point == 0)
3561 {
3562 fprintf (sched_dump, "\n;;\tModel schedule:\n;;\n");
3563 fprintf (sched_dump, ";;\t| idx insn | mpri hght dpth prio |\n");
3564 }
3565 fprintf (sched_dump, ";;\t| %3d %4d | %4d %4d %4d %4d | %-30s ",
3566 point, INSN_UID (insn->insn), insn->model_priority,
3567 insn->depth + insn->alap, insn->depth,
3568 INSN_PRIORITY (insn->insn),
3569 str_pattern_slim (PATTERN (insn->insn)));
3570 }
3571 calculate_reg_deaths (insn->insn, death);
3572 reg_pressure = INSN_REG_PRESSURE (insn->insn);
3573 for (pci = 0; pci < ira_pressure_classes_num; pci++)
3574 {
3575 cl = ira_pressure_classes[pci];
3576 delta = reg_pressure[pci].set_increase - death[cl];
3577 if (sched_verbose >= 2)
3578 fprintf (sched_dump, " %s:[%d,%+d]", reg_class_names[cl],
3579 curr_reg_pressure[cl], delta);
3580 model_record_pressure (&model_before_pressure, point, pci,
3581 curr_reg_pressure[cl]);
3582 }
3583 if (sched_verbose >= 2)
3584 fprintf (sched_dump, "\n");
3585}
3586
3587/* All instructions have been added to the model schedule. Record the
3588 final register pressure in GROUP and set up all MODEL_MAX_PRESSUREs. */
3589
3590static void
3591model_record_final_pressures (struct model_pressure_group *group)
3592{
3593 int point, pci, max_pressure, ref_pressure, cl;
3594
3595 for (pci = 0; pci < ira_pressure_classes_num; pci++)
3596 {
3597 /* Record the final pressure for this class. */
3598 cl = ira_pressure_classes[pci];
3599 point = model_num_insns;
3600 ref_pressure = curr_reg_pressure[cl];
3601 model_record_pressure (group, point, pci, ref_pressure);
3602
3603 /* Record the original maximum pressure. */
3604 group->limits[pci].orig_pressure = group->limits[pci].pressure;
3605
3606 /* Update the MODEL_MAX_PRESSURE for every point of the schedule. */
3607 max_pressure = ref_pressure;
3608 MODEL_MAX_PRESSURE (group, point, pci) = max_pressure;
3609 while (point > 0)
3610 {
3611 point--;
3612 ref_pressure = MODEL_REF_PRESSURE (group, point, pci);
3613 max_pressure = MAX (max_pressure, ref_pressure);
3614 MODEL_MAX_PRESSURE (group, point, pci) = max_pressure;
3615 }
3616 }
3617}
3618
3619/* Update all successors of INSN, given that INSN has just been scheduled. */
3620
3621static void
3622model_add_successors_to_worklist (struct model_insn_info *insn)
3623{
3624 sd_iterator_def sd_it;
3625 struct model_insn_info *con;
3626 dep_t dep;
3627
3628 FOR_EACH_DEP (insn->insn, SD_LIST_FORW, sd_it, dep)
3629 {
3630 con = MODEL_INSN_INFO (DEP_CON (dep));
3631 /* Ignore debug instructions, and instructions from other blocks. */
3632 if (con->insn)
3633 {
3634 con->unscheduled_preds--;
3635
3636 /* Update the depth field of each true-dependent successor.
3637 Increasing the depth gives them a higher priority than
3638 before. */
3639 if (DEP_TYPE (dep) == REG_DEP_TRUE && con->depth < insn->depth + 1)
3640 {
3641 con->depth = insn->depth + 1;
3642 if (QUEUE_INDEX (con->insn) == QUEUE_READY)
3643 model_promote_insn (con);
3644 }
3645
3646 /* If this is a true dependency, or if there are no remaining
3647 dependencies for CON (meaning that CON only had non-true
3648 dependencies), make sure that CON is on the worklist.
3649 We don't bother otherwise because it would tend to fill the
3650 worklist with a lot of low-priority instructions that are not
3651 yet ready to issue. */
3652 if ((con->depth > 0 || con->unscheduled_preds == 0)
3653 && QUEUE_INDEX (con->insn) == QUEUE_NOWHERE)
3654 model_add_to_worklist (con, insn, insn->next);
3655 }
3656 }
3657}
3658
3659/* Give INSN a higher priority than any current instruction, then give
3660 unscheduled predecessors of INSN a higher priority still. If any of
3661 those predecessors are not on the model worklist, do the same for its
3662 predecessors, and so on. */
3663
3664static void
3665model_promote_predecessors (struct model_insn_info *insn)
3666{
3667 struct model_insn_info *pro, *first;
3668 sd_iterator_def sd_it;
3669 dep_t dep;
3670
3671 if (sched_verbose >= 7)
3672 fprintf (sched_dump, ";;\t+--- priority of %d = %d, priority of",
3673 INSN_UID (insn->insn), model_next_priority);
3674 insn->model_priority = model_next_priority++;
3675 model_remove_from_worklist (insn);
3676 model_add_to_worklist_at (insn, NULL);
3677
3678 first = NULL;
3679 for (;;)
3680 {
3681 FOR_EACH_DEP (insn->insn, SD_LIST_HARD_BACK, sd_it, dep)
3682 {
3683 pro = MODEL_INSN_INFO (DEP_PRO (dep));
3684 /* The first test is to ignore debug instructions, and instructions
3685 from other blocks. */
3686 if (pro->insn
3687 && pro->model_priority != model_next_priority
3688 && QUEUE_INDEX (pro->insn) != QUEUE_SCHEDULED)
3689 {
3690 pro->model_priority = model_next_priority;
3691 if (sched_verbose >= 7)
3692 fprintf (sched_dump, " %d", INSN_UID (pro->insn));
3693 if (QUEUE_INDEX (pro->insn) == QUEUE_READY)
3694 {
3695 /* PRO is already in the worklist, but it now has
3696 a higher priority than before. Move it at the
3697 appropriate place. */
3698 model_remove_from_worklist (pro);
3699 model_add_to_worklist (pro, NULL, model_worklist);
3700 }
3701 else
3702 {
3703 /* PRO isn't in the worklist. Recursively process
3704 its predecessors until we find one that is. */
3705 pro->next = first;
3706 first = pro;
3707 }
3708 }
3709 }
3710 if (!first)
3711 break;
3712 insn = first;
3713 first = insn->next;
3714 }
3715 if (sched_verbose >= 7)
3716 fprintf (sched_dump, " = %d\n", model_next_priority);
3717 model_next_priority++;
3718}
3719
3720/* Pick one instruction from model_worklist and process it. */
3721
3722static void
3723model_choose_insn (void)
3724{
3725 struct model_insn_info *insn, *fallback;
3726 int count;
3727
3728 if (sched_verbose >= 7)
3729 {
3730 fprintf (sched_dump, ";;\t+--- worklist:\n");
3731 insn = model_worklist;
3732 count = MAX_SCHED_READY_INSNS;
3733 while (count > 0 && insn)
3734 {
3735 fprintf (sched_dump, ";;\t+--- %d [%d, %d, %d, %d]\n",
3736 INSN_UID (insn->insn), insn->model_priority,
3737 insn->depth + insn->alap, insn->depth,
3738 INSN_PRIORITY (insn->insn));
3739 count--;
3740 insn = insn->next;
3741 }
3742 }
3743
3744 /* Look for a ready instruction whose model_classify_priority is zero
3745 or negative, picking the highest-priority one. Adding such an
3746 instruction to the schedule now should do no harm, and may actually
3747 do some good.
3748
3749 Failing that, see whether there is an instruction with the highest
3750 extant model_priority that is not yet ready, but which would reduce
3751 pressure if it became ready. This is designed to catch cases like:
3752
3753 (set (mem (reg R1)) (reg R2))
3754
3755 where the instruction is the last remaining use of R1 and where the
3756 value of R2 is not yet available (or vice versa). The death of R1
3757 means that this instruction already reduces pressure. It is of
3758 course possible that the computation of R2 involves other registers
3759 that are hard to kill, but such cases are rare enough for this
3760 heuristic to be a win in general.
3761
3762 Failing that, just pick the highest-priority instruction in the
3763 worklist. */
3764 count = MAX_SCHED_READY_INSNS;
3765 insn = model_worklist;
3766 fallback = 0;
3767 for (;;)
3768 {
3769 if (count == 0 || !insn)
3770 {
3771 insn = fallback ? fallback : model_worklist;
3772 break;
3773 }
3774 if (insn->unscheduled_preds)
3775 {
3776 if (model_worklist->model_priority == insn->model_priority
3777 && !fallback
3778 && model_classify_pressure (insn) < 0)
3779 fallback = insn;
3780 }
3781 else
3782 {
3783 if (model_classify_pressure (insn) <= 0)
3784 break;
3785 }
3786 count--;
3787 insn = insn->next;
3788 }
3789
3790 if (sched_verbose >= 7 && insn != model_worklist)
3791 {
3792 if (insn->unscheduled_preds)
3793 fprintf (sched_dump, ";;\t+--- promoting insn %d, with dependencies\n",
3794 INSN_UID (insn->insn));
3795 else
3796 fprintf (sched_dump, ";;\t+--- promoting insn %d, which is ready\n",
3797 INSN_UID (insn->insn));
3798 }
3799 if (insn->unscheduled_preds)
3800 /* INSN isn't yet ready to issue. Give all its predecessors the
3801 highest priority. */
3802 model_promote_predecessors (insn);
3803 else
3804 {
3805 /* INSN is ready. Add it to the end of model_schedule and
3806 process its successors. */
3807 model_add_successors_to_worklist (insn);
3808 model_remove_from_worklist (insn);
3809 model_add_to_schedule (insn->insn);
3810 model_record_pressures (insn);
3811 update_register_pressure (insn->insn);
3812 }
3813}
3814
3815/* Restore all QUEUE_INDEXs to the values that they had before
3816 model_start_schedule was called. */
3817
3818static void
3819model_reset_queue_indices (void)
3820{
3821 unsigned int i;
3822 rtx_insn *insn;
3823
3824 FOR_EACH_VEC_ELT (model_schedule, i, insn)
3825 QUEUE_INDEX (insn) = MODEL_INSN_INFO (insn)->old_queue;
3826}
3827
3828/* We have calculated the model schedule and spill costs. Print a summary
3829 to sched_dump. */
3830
3831static void
3832model_dump_pressure_summary (void)
3833{
3834 int pci, cl;
3835
3836 fprintf (sched_dump, ";; Pressure summary:");
3837 for (pci = 0; pci < ira_pressure_classes_num; pci++)
3838 {
3839 cl = ira_pressure_classes[pci];
3840 fprintf (sched_dump, " %s:%d", reg_class_names[cl],
3841 model_before_pressure.limits[pci].pressure);
3842 }
3843 fprintf (sched_dump, "\n\n");
3844}
3845
3846/* Initialize the SCHED_PRESSURE_MODEL information for the current
3847 scheduling region. */
3848
3849static void
3850model_start_schedule (basic_block bb)
3851{
3852 model_next_priority = 1;
3853 model_schedule.create (sched_max_luid);
3854 model_insns = XCNEWVEC (struct model_insn_info, sched_max_luid);
3855
3856 gcc_assert (bb == BLOCK_FOR_INSN (NEXT_INSN (current_sched_info->prev_head)));
3857 initiate_reg_pressure_info (df_get_live_in (bb));
3858
3859 model_analyze_insns ();
3860 model_init_pressure_group (&model_before_pressure);
3861 while (model_worklist)
3862 model_choose_insn ();
3863 gcc_assert (model_num_insns == (int) model_schedule.length ());
3864 if (sched_verbose >= 2)
3865 fprintf (sched_dump, "\n");
3866
3867 model_record_final_pressures (&model_before_pressure);
3868 model_reset_queue_indices ();
3869
3870 XDELETEVEC (model_insns);
3871
3872 model_curr_point = 0;
3873 initiate_reg_pressure_info (df_get_live_in (bb));
3874 if (sched_verbose >= 1)
3875 model_dump_pressure_summary ();
3876}
3877
3878/* Free the information associated with GROUP. */
3879
3880static void
3881model_finalize_pressure_group (struct model_pressure_group *group)
3882{
3883 XDELETEVEC (group->model);
3884}
3885
3886/* Free the information created by model_start_schedule. */
3887
3888static void
3889model_end_schedule (void)
3890{
3891 model_finalize_pressure_group (&model_before_pressure);
3892 model_schedule.release ();
3893}
3894
3895/* Prepare reg pressure scheduling for basic block BB. */
3896static void
3897sched_pressure_start_bb (basic_block bb)
3898{
3899 /* Set the number of available registers for each class taking into account
3900 relative probability of current basic block versus function prologue and
3901 epilogue.
3902 * If the basic block executes much more often than the prologue/epilogue
3903 (e.g., inside a hot loop), then cost of spill in the prologue is close to
3904 nil, so the effective number of available registers is
3905 (ira_class_hard_regs_num[cl] - fixed_regs_num[cl] - 0).
3906 * If the basic block executes as often as the prologue/epilogue,
3907 then spill in the block is as costly as in the prologue, so the effective
3908 number of available registers is
3909 (ira_class_hard_regs_num[cl] - fixed_regs_num[cl]
3910 - call_saved_regs_num[cl]).
3911 Note that all-else-equal, we prefer to spill in the prologue, since that
3912 allows "extra" registers for other basic blocks of the function.
3913 * If the basic block is on the cold path of the function and executes
3914 rarely, then we should always prefer to spill in the block, rather than
3915 in the prologue/epilogue. The effective number of available register is
3916 (ira_class_hard_regs_num[cl] - fixed_regs_num[cl]
3917 - call_saved_regs_num[cl]). */
3918 {
3919 int i;
3920 int entry_freq = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.to_frequency (cfun);
3921 int bb_freq = bb->count.to_frequency (cfun);
3922
3923 if (bb_freq == 0)
3924 {
3925 if (entry_freq == 0)
3926 entry_freq = bb_freq = 1;
3927 }
3928 if (bb_freq < entry_freq)
3929 bb_freq = entry_freq;
3930
3931 for (i = 0; i < ira_pressure_classes_num; ++i)
3932 {
3933 enum reg_class cl = ira_pressure_classes[i];
3934 sched_class_regs_num[cl] = ira_class_hard_regs_num[cl]
3935 - fixed_regs_num[cl];
3936 sched_class_regs_num[cl]
3937 -= (call_saved_regs_num[cl] * entry_freq) / bb_freq;
3938 }
3939 }
3940
3941 if (sched_pressure == SCHED_PRESSURE_MODEL)
3942 model_start_schedule (bb);
3943}
3944
3945/* A structure that holds local state for the loop in schedule_block. */
3946struct sched_block_state
3947{
3948 /* True if no real insns have been scheduled in the current cycle. */
3949 bool first_cycle_insn_p;
3950 /* True if a shadow insn has been scheduled in the current cycle, which
3951 means that no more normal insns can be issued. */
3952 bool shadows_only_p;
3953 /* True if we're winding down a modulo schedule, which means that we only
3954 issue insns with INSN_EXACT_TICK set. */
3955 bool modulo_epilogue;
3956 /* Initialized with the machine's issue rate every cycle, and updated
3957 by calls to the variable_issue hook. */
3958 int can_issue_more;
3959};
3960
3961/* INSN is the "currently executing insn". Launch each insn which was
3962 waiting on INSN. READY is the ready list which contains the insns
3963 that are ready to fire. CLOCK is the current cycle. The function
3964 returns necessary cycle advance after issuing the insn (it is not
3965 zero for insns in a schedule group). */
3966
3967static int
3968schedule_insn (rtx_insn *insn)
3969{
3970 sd_iterator_def sd_it;
3971 dep_t dep;
3972 int i;
3973 int advance = 0;
3974
3975 if (sched_verbose >= 1)
3976 {
3977 struct reg_pressure_data *pressure_info;
3978 fprintf (sched_dump, ";;\t%3i--> %s %-40s:",
3979 clock_var, (*current_sched_info->print_insn) (insn, 1),
3980 str_pattern_slim (PATTERN (insn)));
3981
3982 if (recog_memoized (insn) < 0)
3983 fprintf (sched_dump, "nothing");
3984 else
3985 print_reservation (sched_dump, insn);
3986 pressure_info = INSN_REG_PRESSURE (insn);
3987 if (pressure_info != NULL)
3988 {
3989 fputc (':', sched_dump);
3990 for (i = 0; i < ira_pressure_classes_num; i++)
3991 fprintf (sched_dump, "%s%s%+d(%d)",
3992 scheduled_insns.length () > 1
3993 && INSN_LUID (insn)
3994 < INSN_LUID (scheduled_insns[scheduled_insns.length () - 2]) ? "@" : "",
3995 reg_class_names[ira_pressure_classes[i]],
3996 pressure_info[i].set_increase, pressure_info[i].change);
3997 }
3998 if (sched_pressure == SCHED_PRESSURE_MODEL
3999 && model_curr_point < model_num_insns
4000 && model_index (insn) == model_curr_point)
4001 fprintf (sched_dump, ":model %d", model_curr_point);
4002 fputc ('\n', sched_dump);
4003 }
4004
4005 if (sched_pressure == SCHED_PRESSURE_WEIGHTED && !DEBUG_INSN_P (insn))
4006 update_reg_and_insn_max_reg_pressure (insn);
4007
4008 /* Scheduling instruction should have all its dependencies resolved and
4009 should have been removed from the ready list. */
4010 gcc_assert (sd_lists_empty_p (insn, SD_LIST_HARD_BACK));
4011
4012 /* Reset debug insns invalidated by moving this insn. */
4013 if (MAY_HAVE_DEBUG_BIND_INSNS && !DEBUG_INSN_P (insn))
4014 for (sd_it = sd_iterator_start (insn, SD_LIST_BACK);
4015 sd_iterator_cond (&sd_it, &dep);)
4016 {
4017 rtx_insn *dbg = DEP_PRO (dep);
4018 struct reg_use_data *use, *next;
4019
4020 if (DEP_STATUS (dep) & DEP_CANCELLED)
4021 {
4022 sd_iterator_next (&sd_it);
4023 continue;
4024 }
4025
4026 gcc_assert (DEBUG_BIND_INSN_P (dbg));
4027
4028 if (sched_verbose >= 6)
4029 fprintf (sched_dump, ";;\t\tresetting: debug insn %d\n",
4030 INSN_UID (dbg));
4031
4032 /* ??? Rather than resetting the debug insn, we might be able
4033 to emit a debug temp before the just-scheduled insn, but
4034 this would involve checking that the expression at the
4035 point of the debug insn is equivalent to the expression
4036 before the just-scheduled insn. They might not be: the
4037 expression in the debug insn may depend on other insns not
4038 yet scheduled that set MEMs, REGs or even other debug
4039 insns. It's not clear that attempting to preserve debug
4040 information in these cases is worth the effort, given how
4041 uncommon these resets are and the likelihood that the debug
4042 temps introduced won't survive the schedule change. */
4043 INSN_VAR_LOCATION_LOC (dbg) = gen_rtx_UNKNOWN_VAR_LOC ();
4044 df_insn_rescan (dbg);
4045
4046 /* Unknown location doesn't use any registers. */
4047 for (use = INSN_REG_USE_LIST (dbg); use != NULL; use = next)
4048 {
4049 struct reg_use_data *prev = use;
4050
4051 /* Remove use from the cyclic next_regno_use chain first. */
4052 while (prev->next_regno_use != use)
4053 prev = prev->next_regno_use;
4054 prev->next_regno_use = use->next_regno_use;
4055 next = use->next_insn_use;
4056 free (use);
4057 }
4058 INSN_REG_USE_LIST (dbg) = NULL;
4059
4060 /* We delete rather than resolve these deps, otherwise we
4061 crash in sched_free_deps(), because forward deps are
4062 expected to be released before backward deps. */
4063 sd_delete_dep (sd_it);
4064 }
4065
4066 gcc_assert (QUEUE_INDEX (insn) == QUEUE_NOWHERE);
4067 QUEUE_INDEX (insn) = QUEUE_SCHEDULED;
4068
4069 if (sched_pressure == SCHED_PRESSURE_MODEL
4070 && model_curr_point < model_num_insns
4071 && NONDEBUG_INSN_P (insn))
4072 {
4073 if (model_index (insn) == model_curr_point)
4074 do
4075 model_curr_point++;
4076 while (model_curr_point < model_num_insns
4077 && (QUEUE_INDEX (MODEL_INSN (model_curr_point))
4078 == QUEUE_SCHEDULED));
4079 else
4080 model_recompute (insn);
4081 model_update_limit_points ();
4082 update_register_pressure (insn);
4083 if (sched_verbose >= 2)
4084 print_curr_reg_pressure ();
4085 }
4086
4087 gcc_assert (INSN_TICK (insn) >= MIN_TICK);
4088 if (INSN_TICK (insn) > clock_var)
4089 /* INSN has been prematurely moved from the queue to the ready list.
4090 This is possible only if following flags are set. */
4091 gcc_assert (flag_sched_stalled_insns || sched_fusion);
4092
4093 /* ??? Probably, if INSN is scheduled prematurely, we should leave
4094 INSN_TICK untouched. This is a machine-dependent issue, actually. */
4095 INSN_TICK (insn) = clock_var;
4096
4097 check_clobbered_conditions (insn);
4098
4099 /* Update dependent instructions. First, see if by scheduling this insn
4100 now we broke a dependence in a way that requires us to change another
4101 insn. */
4102 for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
4103 sd_iterator_cond (&sd_it, &dep); sd_iterator_next (&sd_it))
4104 {
4105 struct dep_replacement *desc = DEP_REPLACE (dep);
4106 rtx_insn *pro = DEP_PRO (dep);
4107 if (QUEUE_INDEX (pro) != QUEUE_SCHEDULED
4108 && desc != NULL && desc->insn == pro)
4109 apply_replacement (dep, false);
4110 }
4111
4112 /* Go through and resolve forward dependencies. */
4113 for (sd_it = sd_iterator_start (insn, SD_LIST_FORW);
4114 sd_iterator_cond (&sd_it, &dep);)
4115 {
4116 rtx_insn *next = DEP_CON (dep);
4117 bool cancelled = (DEP_STATUS (dep) & DEP_CANCELLED) != 0;
4118
4119 /* Resolve the dependence between INSN and NEXT.
4120 sd_resolve_dep () moves current dep to another list thus
4121 advancing the iterator. */
4122 sd_resolve_dep (sd_it);
4123
4124 if (cancelled)
4125 {
4126 if (must_restore_pattern_p (next, dep))
4127 restore_pattern (dep, false);
4128 continue;
4129 }
4130
4131 /* Don't bother trying to mark next as ready if insn is a debug
4132 insn. If insn is the last hard dependency, it will have
4133 already been discounted. */
4134 if (DEBUG_INSN_P (insn) && !DEBUG_INSN_P (next))
4135 continue;
4136
4137 if (!IS_SPECULATION_BRANCHY_CHECK_P (insn))
4138 {
4139 int effective_cost;
4140
4141 effective_cost = try_ready (next);
4142
4143 if (effective_cost >= 0
4144 && SCHED_GROUP_P (next)
4145 && advance < effective_cost)
4146 advance = effective_cost;
4147 }
4148 else
4149 /* Check always has only one forward dependence (to the first insn in
4150 the recovery block), therefore, this will be executed only once. */
4151 {
4152 gcc_assert (sd_lists_empty_p (insn, SD_LIST_FORW));
4153 fix_recovery_deps (RECOVERY_BLOCK (insn));
4154 }
4155 }
4156
4157 /* Annotate the instruction with issue information -- TImode
4158 indicates that the instruction is expected not to be able
4159 to issue on the same cycle as the previous insn. A machine
4160 may use this information to decide how the instruction should
4161 be aligned. */
4162 if (issue_rate > 1
4163 && GET_CODE (PATTERN (insn)) != USE
4164 && GET_CODE (PATTERN (insn)) != CLOBBER
4165 && !DEBUG_INSN_P (insn))
4166 {
4167 if (reload_completed)
4168 PUT_MODE (insn, clock_var > last_clock_var ? TImode : VOIDmode);
4169 last_clock_var = clock_var;
4170 }
4171
4172 if (nonscheduled_insns_begin != NULL_RTX)
4173 /* Indicate to debug counters that INSN is scheduled. */
4174 nonscheduled_insns_begin = insn;
4175
4176 return advance;
4177}
4178
4179/* Functions for handling of notes. */
4180
4181/* Add note list that ends on FROM_END to the end of TO_ENDP. */
4182void
4183concat_note_lists (rtx_insn *from_end, rtx_insn **to_endp)
4184{
4185 rtx_insn *from_start;
4186
4187 /* It's easy when have nothing to concat. */
4188 if (from_end == NULL)
4189 return;
4190
4191 /* It's also easy when destination is empty. */
4192 if (*to_endp == NULL)
4193 {
4194 *to_endp = from_end;
4195 return;
4196 }
4197
4198 from_start = from_end;
4199 while (PREV_INSN (from_start) != NULL)
4200 from_start = PREV_INSN (from_start);
4201
4202 SET_PREV_INSN (from_start) = *to_endp;
4203 SET_NEXT_INSN (*to_endp) = from_start;
4204 *to_endp = from_end;
4205}
4206
4207/* Delete notes between HEAD and TAIL and put them in the chain
4208 of notes ended by NOTE_LIST. */
4209void
4210remove_notes (rtx_insn *head, rtx_insn *tail)
4211{
4212 rtx_insn *next_tail, *insn, *next;
4213
4214 note_list = 0;
4215 if (head == tail && !INSN_P (head))
4216 return;
4217
4218 next_tail = NEXT_INSN (tail);
4219 for (insn = head; insn != next_tail; insn = next)
4220 {
4221 next = NEXT_INSN (insn);
4222 if (!NOTE_P (insn))
4223 continue;
4224
4225 switch (NOTE_KIND (insn))
4226 {
4227 case NOTE_INSN_BASIC_BLOCK:
4228 continue;
4229
4230 case NOTE_INSN_EPILOGUE_BEG:
4231 if (insn != tail)
4232 {
4233 remove_insn (insn);
4234 add_reg_note (next, REG_SAVE_NOTE,
4235 GEN_INT (NOTE_INSN_EPILOGUE_BEG));
4236 break;
4237 }
4238 /* FALLTHRU */
4239
4240 default:
4241 remove_insn (insn);
4242
4243 /* Add the note to list that ends at NOTE_LIST. */
4244 SET_PREV_INSN (insn) = note_list;
4245 SET_NEXT_INSN (insn) = NULL_RTX;
4246 if (note_list)
4247 SET_NEXT_INSN (note_list) = insn;
4248 note_list = insn;
4249 break;
4250 }
4251
4252 gcc_assert ((sel_sched_p () || insn != tail) && insn != head);
4253 }
4254}
4255
4256/* A structure to record enough data to allow us to backtrack the scheduler to
4257 a previous state. */
4258struct haifa_saved_data
4259{
4260 /* Next entry on the list. */
4261 struct haifa_saved_data *next;
4262
4263 /* Backtracking is associated with scheduling insns that have delay slots.
4264 DELAY_PAIR points to the structure that contains the insns involved, and
4265 the number of cycles between them. */
4266 struct delay_pair *delay_pair;
4267
4268 /* Data used by the frontend (e.g. sched-ebb or sched-rgn). */
4269 void *fe_saved_data;
4270 /* Data used by the backend. */
4271 void *be_saved_data;
4272
4273 /* Copies of global state. */
4274 int clock_var, last_clock_var;
4275 struct ready_list ready;
4276 state_t curr_state;
4277
4278 rtx_insn *last_scheduled_insn;
4279 rtx_insn *last_nondebug_scheduled_insn;
4280 rtx_insn *nonscheduled_insns_begin;
4281 int cycle_issued_insns;
4282
4283 /* Copies of state used in the inner loop of schedule_block. */
4284 struct sched_block_state sched_block;
4285
4286 /* We don't need to save q_ptr, as its value is arbitrary and we can set it
4287 to 0 when restoring. */
4288 int q_size;
4289 rtx_insn_list **insn_queue;
4290
4291 /* Describe pattern replacements that occurred since this backtrack point
4292 was queued. */
4293 vec<dep_t> replacement_deps;
4294 vec<int> replace_apply;
4295
4296 /* A copy of the next-cycle replacement vectors at the time of the backtrack
4297 point. */
4298 vec<dep_t> next_cycle_deps;
4299 vec<int> next_cycle_apply;
4300};
4301
4302/* A record, in reverse order, of all scheduled insns which have delay slots
4303 and may require backtracking. */
4304static struct haifa_saved_data *backtrack_queue;
4305
4306/* For every dependency of INSN, set the FEEDS_BACKTRACK_INSN bit according
4307 to SET_P. */
4308static void
4309mark_backtrack_feeds (rtx_insn *insn, int set_p)
4310{
4311 sd_iterator_def sd_it;
4312 dep_t dep;
4313 FOR_EACH_DEP (insn, SD_LIST_HARD_BACK, sd_it, dep)
4314 {
4315 FEEDS_BACKTRACK_INSN (DEP_PRO (dep)) = set_p;
4316 }
4317}
4318
4319/* Save the current scheduler state so that we can backtrack to it
4320 later if necessary. PAIR gives the insns that make it necessary to
4321 save this point. SCHED_BLOCK is the local state of schedule_block
4322 that need to be saved. */
4323static void
4324save_backtrack_point (struct delay_pair *pair,
4325 struct sched_block_state sched_block)
4326{
4327 int i;
4328 struct haifa_saved_data *save = XNEW (struct haifa_saved_data);
4329
4330 save->curr_state = xmalloc (dfa_state_size);
4331 memcpy (save->curr_state, curr_state, dfa_state_size);
4332
4333 save->ready.first = ready.first;
4334 save->ready.n_ready = ready.n_ready;
4335 save->ready.n_debug = ready.n_debug;
4336 save->ready.veclen = ready.veclen;
4337 save->ready.vec = XNEWVEC (rtx_insn *, ready.veclen);
4338 memcpy (save->ready.vec, ready.vec, ready.veclen * sizeof (rtx));
4339
4340 save->insn_queue = XNEWVEC (rtx_insn_list *, max_insn_queue_index + 1);
4341 save->q_size = q_size;
4342 for (i = 0; i <= max_insn_queue_index; i++)
4343 {
4344 int q = NEXT_Q_AFTER (q_ptr, i);
4345 save->insn_queue[i] = copy_INSN_LIST (insn_queue[q]);
4346 }
4347
4348 save->clock_var = clock_var;
4349 save->last_clock_var = last_clock_var;
4350 save->cycle_issued_insns = cycle_issued_insns;
4351 save->last_scheduled_insn = last_scheduled_insn;
4352 save->last_nondebug_scheduled_insn = last_nondebug_scheduled_insn;
4353 save->nonscheduled_insns_begin = nonscheduled_insns_begin;
4354
4355 save->sched_block = sched_block;
4356
4357 save->replacement_deps.create (0);
4358 save->replace_apply.create (0);
4359 save->next_cycle_deps = next_cycle_replace_deps.copy ();
4360 save->next_cycle_apply = next_cycle_apply.copy ();
4361
4362 if (current_sched_info->save_state)
4363 save->fe_saved_data = (*current_sched_info->save_state) ();
4364
4365 if (targetm.sched.alloc_sched_context)
4366 {
4367 save->be_saved_data = targetm.sched.alloc_sched_context ();
4368 targetm.sched.init_sched_context (save->be_saved_data, false);
4369 }
4370 else
4371 save->be_saved_data = NULL;
4372
4373 save->delay_pair = pair;
4374
4375 save->next = backtrack_queue;
4376 backtrack_queue = save;
4377
4378 while (pair)
4379 {
4380 mark_backtrack_feeds (pair->i2, 1);
4381 INSN_TICK (pair->i2) = INVALID_TICK;
4382 INSN_EXACT_TICK (pair->i2) = clock_var + pair_delay (pair);
4383 SHADOW_P (pair->i2) = pair->stages == 0;
4384 pair = pair->next_same_i1;
4385 }
4386}
4387
4388/* Walk the ready list and all queues. If any insns have unresolved backwards
4389 dependencies, these must be cancelled deps, broken by predication. Set or
4390 clear (depending on SET) the DEP_CANCELLED bit in DEP_STATUS. */
4391
4392static void
4393toggle_cancelled_flags (bool set)
4394{
4395 int i;
4396 sd_iterator_def sd_it;
4397 dep_t dep;
4398
4399 if (ready.n_ready > 0)
4400 {
4401 rtx_insn **first = ready_lastpos (&ready);
4402 for (i = 0; i < ready.n_ready; i++)
4403 FOR_EACH_DEP (first[i], SD_LIST_BACK, sd_it, dep)
4404 if (!DEBUG_INSN_P (DEP_PRO (dep)))
4405 {
4406 if (set)
4407 DEP_STATUS (dep) |= DEP_CANCELLED;
4408 else
4409 DEP_STATUS (dep) &= ~DEP_CANCELLED;
4410 }
4411 }
4412 for (i = 0; i <= max_insn_queue_index; i++)
4413 {
4414 int q = NEXT_Q_AFTER (q_ptr, i);
4415 rtx_insn_list *link;
4416 for (link = insn_queue[q]; link; link = link->next ())
4417 {
4418 rtx_insn *insn = link->insn ();
4419 FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
4420 if (!DEBUG_INSN_P (DEP_PRO (dep)))
4421 {
4422 if (set)
4423 DEP_STATUS (dep) |= DEP_CANCELLED;
4424 else
4425 DEP_STATUS (dep) &= ~DEP_CANCELLED;
4426 }
4427 }
4428 }
4429}
4430
4431/* Undo the replacements that have occurred after backtrack point SAVE
4432 was placed. */
4433static void
4434undo_replacements_for_backtrack (struct haifa_saved_data *save)
4435{
4436 while (!save->replacement_deps.is_empty ())
4437 {
4438 dep_t dep = save->replacement_deps.pop ();
4439 int apply_p = save->replace_apply.pop ();
4440
4441 if (apply_p)
4442 restore_pattern (dep, true);
4443 else
4444 apply_replacement (dep, true);
4445 }
4446 save->replacement_deps.release ();
4447 save->replace_apply.release ();
4448}
4449
4450/* Pop entries from the SCHEDULED_INSNS vector up to and including INSN.
4451 Restore their dependencies to an unresolved state, and mark them as
4452 queued nowhere. */
4453
4454static void
4455unschedule_insns_until (rtx_insn *insn)
4456{
4457 auto_vec<rtx_insn *> recompute_vec;
4458
4459 /* Make two passes over the insns to be unscheduled. First, we clear out
4460 dependencies and other trivial bookkeeping. */
4461 for (;;)
4462 {
4463 rtx_insn *last;
4464 sd_iterator_def sd_it;
4465 dep_t dep;
4466
4467 last = scheduled_insns.pop ();
4468
4469 /* This will be changed by restore_backtrack_point if the insn is in
4470 any queue. */
4471 QUEUE_INDEX (last) = QUEUE_NOWHERE;
4472 if (last != insn)
4473 INSN_TICK (last) = INVALID_TICK;
4474
4475 if (modulo_ii > 0 && INSN_UID (last) < modulo_iter0_max_uid)
4476 modulo_insns_scheduled--;
4477
4478 for (sd_it = sd_iterator_start (last, SD_LIST_RES_FORW);
4479 sd_iterator_cond (&sd_it, &dep);)
4480 {
4481 rtx_insn *con = DEP_CON (dep);
4482 sd_unresolve_dep (sd_it);
4483 if (!MUST_RECOMPUTE_SPEC_P (con))
4484 {
4485 MUST_RECOMPUTE_SPEC_P (con) = 1;
4486 recompute_vec.safe_push (con);
4487 }
4488 }
4489
4490 if (last == insn)
4491 break;
4492 }
4493
4494 /* A second pass, to update ready and speculation status for insns
4495 depending on the unscheduled ones. The first pass must have
4496 popped the scheduled_insns vector up to the point where we
4497 restart scheduling, as recompute_todo_spec requires it to be
4498 up-to-date. */
4499 while (!recompute_vec.is_empty ())
4500 {
4501 rtx_insn *con;
4502
4503 con = recompute_vec.pop ();
4504 MUST_RECOMPUTE_SPEC_P (con) = 0;
4505 if (!sd_lists_empty_p (con, SD_LIST_HARD_BACK))
4506 {
4507 TODO_SPEC (con) = HARD_DEP;
4508 INSN_TICK (con) = INVALID_TICK;
4509 if (PREDICATED_PAT (con) != NULL_RTX)
4510 haifa_change_pattern (con, ORIG_PAT (con));
4511 }
4512 else if (QUEUE_INDEX (con) != QUEUE_SCHEDULED)
4513 TODO_SPEC (con) = recompute_todo_spec (con, true);
4514 }
4515}
4516
4517/* Restore scheduler state from the topmost entry on the backtracking queue.
4518 PSCHED_BLOCK_P points to the local data of schedule_block that we must
4519 overwrite with the saved data.
4520 The caller must already have called unschedule_insns_until. */
4521
4522static void
4523restore_last_backtrack_point (struct sched_block_state *psched_block)
4524{
4525 int i;
4526 struct haifa_saved_data *save = backtrack_queue;
4527
4528 backtrack_queue = save->next;
4529
4530 if (current_sched_info->restore_state)
4531 (*current_sched_info->restore_state) (save->fe_saved_data);
4532
4533 if (targetm.sched.alloc_sched_context)
4534 {
4535 targetm.sched.set_sched_context (save->be_saved_data);
4536 targetm.sched.free_sched_context (save->be_saved_data);
4537 }
4538
4539 /* Do this first since it clobbers INSN_TICK of the involved
4540 instructions. */
4541 undo_replacements_for_backtrack (save);
4542
4543 /* Clear the QUEUE_INDEX of everything in the ready list or one
4544 of the queues. */
4545 if (ready.n_ready > 0)
4546 {
4547 rtx_insn **first = ready_lastpos (&ready);
4548 for (i = 0; i < ready.n_ready; i++)
4549 {
4550 rtx_insn *insn = first[i];
4551 QUEUE_INDEX (insn) = QUEUE_NOWHERE;
4552 INSN_TICK (insn) = INVALID_TICK;
4553 }
4554 }
4555 for (i = 0; i <= max_insn_queue_index; i++)
4556 {
4557 int q = NEXT_Q_AFTER (q_ptr, i);
4558
4559 for (rtx_insn_list *link = insn_queue[q]; link; link = link->next ())
4560 {
4561 rtx_insn *x = link->insn ();
4562 QUEUE_INDEX (x) = QUEUE_NOWHERE;
4563 INSN_TICK (x) = INVALID_TICK;
4564 }
4565 free_INSN_LIST_list (&insn_queue[q]);
4566 }
4567
4568 free (ready.vec);
4569 ready = save->ready;
4570
4571 if (ready.n_ready > 0)
4572 {
4573 rtx_insn **first = ready_lastpos (&ready);
4574 for (i = 0; i < ready.n_ready; i++)
4575 {
4576 rtx_insn *insn = first[i];
4577 QUEUE_INDEX (insn) = QUEUE_READY;
4578 TODO_SPEC (insn) = recompute_todo_spec (insn, true);
4579 INSN_TICK (insn) = save->clock_var;
4580 }
4581 }
4582
4583 q_ptr = 0;
4584 q_size = save->q_size;
4585 for (i = 0; i <= max_insn_queue_index; i++)
4586 {
4587 int q = NEXT_Q_AFTER (q_ptr, i);
4588
4589 insn_queue[q] = save->insn_queue[q];
4590
4591 for (rtx_insn_list *link = insn_queue[q]; link; link = link->next ())
4592 {
4593 rtx_insn *x = link->insn ();
4594 QUEUE_INDEX (x) = i;
4595 TODO_SPEC (x) = recompute_todo_spec (x, true);
4596 INSN_TICK (x) = save->clock_var + i;
4597 }
4598 }
4599 free (save->insn_queue);
4600
4601 toggle_cancelled_flags (true);
4602
4603 clock_var = save->clock_var;
4604 last_clock_var = save->last_clock_var;
4605 cycle_issued_insns = save->cycle_issued_insns;
4606 last_scheduled_insn = save->last_scheduled_insn;
4607 last_nondebug_scheduled_insn = save->last_nondebug_scheduled_insn;
4608 nonscheduled_insns_begin = save->nonscheduled_insns_begin;
4609
4610 *psched_block = save->sched_block;
4611
4612 memcpy (curr_state, save->curr_state, dfa_state_size);
4613 free (save->curr_state);
4614
4615 mark_backtrack_feeds (save->delay_pair->i2, 0);
4616
4617 gcc_assert (next_cycle_replace_deps.is_empty ());
4618 next_cycle_replace_deps = save->next_cycle_deps.copy ();
4619 next_cycle_apply = save->next_cycle_apply.copy ();
4620
4621 free (save);
4622
4623 for (save = backtrack_queue; save; save = save->next)
4624 {
4625 mark_backtrack_feeds (save->delay_pair->i2, 1);
4626 }
4627}
4628
4629/* Discard all data associated with the topmost entry in the backtrack
4630 queue. If RESET_TICK is false, we just want to free the data. If true,
4631 we are doing this because we discovered a reason to backtrack. In the
4632 latter case, also reset the INSN_TICK for the shadow insn. */
4633static void
4634free_topmost_backtrack_point (bool reset_tick)
4635{
4636 struct haifa_saved_data *save = backtrack_queue;
4637 int i;
4638
4639 backtrack_queue = save->next;
4640
4641 if (reset_tick)
4642 {
4643 struct delay_pair *pair = save->delay_pair;
4644 while (pair)
4645 {
4646 INSN_TICK (pair->i2) = INVALID_TICK;
4647 INSN_EXACT_TICK (pair->i2) = INVALID_TICK;
4648 pair = pair->next_same_i1;
4649 }
4650 undo_replacements_for_backtrack (save);
4651 }
4652 else
4653 {
4654 save->replacement_deps.release ();
4655 save->replace_apply.release ();
4656 }
4657
4658 if (targetm.sched.free_sched_context)
4659 targetm.sched.free_sched_context (save->be_saved_data);
4660 if (current_sched_info->restore_state)
4661 free (save->fe_saved_data);
4662 for (i = 0; i <= max_insn_queue_index; i++)
4663 free_INSN_LIST_list (&save->insn_queue[i]);
4664 free (save->insn_queue);
4665 free (save->curr_state);
4666 free (save->ready.vec);
4667 free (save);
4668}
4669
4670/* Free the entire backtrack queue. */
4671static void
4672free_backtrack_queue (void)
4673{
4674 while (backtrack_queue)
4675 free_topmost_backtrack_point (false);
4676}
4677
4678/* Apply a replacement described by DESC. If IMMEDIATELY is false, we
4679 may have to postpone the replacement until the start of the next cycle,
4680 at which point we will be called again with IMMEDIATELY true. This is
4681 only done for machines which have instruction packets with explicit
4682 parallelism however. */
4683static void
4684apply_replacement (dep_t dep, bool immediately)
4685{
4686 struct dep_replacement *desc = DEP_REPLACE (dep);
4687 if (!immediately && targetm.sched.exposed_pipeline && reload_completed)
4688 {
4689 next_cycle_replace_deps.safe_push (dep);
4690 next_cycle_apply.safe_push (1);
4691 }
4692 else
4693 {
4694 bool success;
4695
4696 if (QUEUE_INDEX (desc->insn) == QUEUE_SCHEDULED)
4697 return;
4698
4699 if (sched_verbose >= 5)
4700 fprintf (sched_dump, "applying replacement for insn %d\n",
4701 INSN_UID (desc->insn));
4702
4703 success = validate_change (desc->insn, desc->loc, desc->newval, 0);
4704 gcc_assert (success);
4705
4706 update_insn_after_change (desc->insn);
4707 if ((TODO_SPEC (desc->insn) & (HARD_DEP | DEP_POSTPONED)) == 0)
4708 fix_tick_ready (desc->insn);
4709
4710 if (backtrack_queue != NULL)
4711 {
4712 backtrack_queue->replacement_deps.safe_push (dep);
4713 backtrack_queue->replace_apply.safe_push (1);
4714 }
4715 }
4716}
4717
4718/* We have determined that a pattern involved in DEP must be restored.
4719 If IMMEDIATELY is false, we may have to postpone the replacement
4720 until the start of the next cycle, at which point we will be called
4721 again with IMMEDIATELY true. */
4722static void
4723restore_pattern (dep_t dep, bool immediately)
4724{
4725 rtx_insn *next = DEP_CON (dep);
4726 int tick = INSN_TICK (next);
4727
4728 /* If we already scheduled the insn, the modified version is
4729 correct. */
4730 if (QUEUE_INDEX (next) == QUEUE_SCHEDULED)
4731 return;
4732
4733 if (!immediately && targetm.sched.exposed_pipeline && reload_completed)
4734 {
4735 next_cycle_replace_deps.safe_push (dep);
4736 next_cycle_apply.safe_push (0);
4737 return;
4738 }
4739
4740
4741 if (DEP_TYPE (dep) == REG_DEP_CONTROL)
4742 {
4743 if (sched_verbose >= 5)
4744 fprintf (sched_dump, "restoring pattern for insn %d\n",
4745 INSN_UID (next));
4746 haifa_change_pattern (next, ORIG_PAT (next));
4747 }
4748 else
4749 {
4750 struct dep_replacement *desc = DEP_REPLACE (dep);
4751 bool success;
4752
4753 if (sched_verbose >= 5)
4754 fprintf (sched_dump, "restoring pattern for insn %d\n",
4755 INSN_UID (desc->insn));
4756 tick = INSN_TICK (desc->insn);
4757
4758 success = validate_change (desc->insn, desc->loc, desc->orig, 0);
4759 gcc_assert (success);
4760 update_insn_after_change (desc->insn);
4761 if (backtrack_queue != NULL)
4762 {
4763 backtrack_queue->replacement_deps.safe_push (dep);
4764 backtrack_queue->replace_apply.safe_push (0);
4765 }
4766 }
4767 INSN_TICK (next) = tick;
4768 if (TODO_SPEC (next) == DEP_POSTPONED)
4769 return;
4770
4771 if (sd_lists_empty_p (next, SD_LIST_BACK))
4772 TODO_SPEC (next) = 0;
4773 else if (!sd_lists_empty_p (next, SD_LIST_HARD_BACK))
4774 TODO_SPEC (next) = HARD_DEP;
4775}
4776
4777/* Perform pattern replacements that were queued up until the next
4778 cycle. */
4779static void
4780perform_replacements_new_cycle (void)
4781{
4782 int i;
4783 dep_t dep;
4784 FOR_EACH_VEC_ELT (next_cycle_replace_deps, i, dep)
4785 {
4786 int apply_p = next_cycle_apply[i];
4787 if (apply_p)
4788 apply_replacement (dep, true);
4789 else
4790 restore_pattern (dep, true);
4791 }
4792 next_cycle_replace_deps.truncate (0);
4793 next_cycle_apply.truncate (0);
4794}
4795
4796/* Compute INSN_TICK_ESTIMATE for INSN. PROCESSED is a bitmap of
4797 instructions we've previously encountered, a set bit prevents
4798 recursion. BUDGET is a limit on how far ahead we look, it is
4799 reduced on recursive calls. Return true if we produced a good
4800 estimate, or false if we exceeded the budget. */
4801static bool
4802estimate_insn_tick (bitmap processed, rtx_insn *insn, int budget)
4803{
4804 sd_iterator_def sd_it;
4805 dep_t dep;
4806 int earliest = INSN_TICK (insn);
4807
4808 FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
4809 {
4810 rtx_insn *pro = DEP_PRO (dep);
4811 int t;
4812
4813 if (DEP_STATUS (dep) & DEP_CANCELLED)
4814 continue;
4815
4816 if (QUEUE_INDEX (pro) == QUEUE_SCHEDULED)
4817 gcc_assert (INSN_TICK (pro) + dep_cost (dep) <= INSN_TICK (insn));
4818 else
4819 {
4820 int cost = dep_cost (dep);
4821 if (cost >= budget)
4822 return false;
4823 if (!bitmap_bit_p (processed, INSN_LUID (pro)))
4824 {
4825 if (!estimate_insn_tick (processed, pro, budget - cost))
4826 return false;
4827 }
4828 gcc_assert (INSN_TICK_ESTIMATE (pro) != INVALID_TICK);
4829 t = INSN_TICK_ESTIMATE (pro) + cost;
4830 if (earliest == INVALID_TICK || t > earliest)
4831 earliest = t;
4832 }
4833 }
4834 bitmap_set_bit (processed, INSN_LUID (insn));
4835 INSN_TICK_ESTIMATE (insn) = earliest;
4836 return true;
4837}
4838
4839/* Examine the pair of insns in P, and estimate (optimis