1 /* Instruction scheduling pass.
2 Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
4 Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
5 and currently maintained by, Jim Wilson (wilson@cygnus.com)
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 2, or (at your option) any later
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING. If not, write to the Free
21 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
24 /* Instruction scheduling pass. This file, along with sched-deps.c,
25 contains the generic parts. The actual entry point is found for
26 the normal instruction scheduling pass is found in sched-rgn.c.
28 We compute insn priorities based on data dependencies. Flow
29 analysis only creates a fraction of the data-dependencies we must
30 observe: namely, only those dependencies which the combiner can be
31 expected to use. For this pass, we must therefore create the
32 remaining dependencies we need to observe: register dependencies,
33 memory dependencies, dependencies to keep function calls in order,
34 and the dependence between a conditional branch and the setting of
35 condition codes are all dealt with here.
37 The scheduler first traverses the data flow graph, starting with
38 the last instruction, and proceeding to the first, assigning values
39 to insn_priority as it goes. This sorts the instructions
40 topologically by data dependence.
42 Once priorities have been established, we order the insns using
43 list scheduling. This works as follows: starting with a list of
44 all the ready insns, and sorted according to priority number, we
45 schedule the insn from the end of the list by placing its
46 predecessors in the list according to their priority order. We
47 consider this insn scheduled by setting the pointer to the "end" of
48 the list to point to the previous insn. When an insn has no
49 predecessors, we either queue it until sufficient time has elapsed
50 or add it to the ready list. As the instructions are scheduled or
51 when stalls are introduced, the queue advances and dumps insns into
52 the ready list. When all insns down to the lowest priority have
53 been scheduled, the critical path of the basic block has been made
54 as short as possible. The remaining insns are then scheduled in
57 The following list shows the order in which we want to break ties
58 among insns in the ready list:
60 1. choose insn with the longest path to end of bb, ties
62 2. choose insn with least contribution to register pressure,
64 3. prefer in-block upon interblock motion, ties broken by
65 4. prefer useful upon speculative motion, ties broken by
66 5. choose insn with largest control flow probability, ties
68 6. choose insn with the least dependences upon the previously
69 scheduled insn, or finally
70 7 choose the insn which has the most insns dependent on it.
71 8. choose insn with lowest UID.
73 Memory references complicate matters. Only if we can be certain
74 that memory references are not part of the data dependency graph
75 (via true, anti, or output dependence), can we move operations past
76 memory references. To first approximation, reads can be done
77 independently, while writes introduce dependencies. Better
78 approximations will yield fewer dependencies.
80 Before reload, an extended analysis of interblock data dependences
81 is required for interblock scheduling. This is performed in
82 compute_block_backward_dependences ().
84 Dependencies set up by memory references are treated in exactly the
85 same way as other dependencies, by using LOG_LINKS backward
86 dependences. LOG_LINKS are translated into INSN_DEPEND forward
87 dependences for the purpose of forward list scheduling.
89 Having optimized the critical path, we may have also unduly
90 extended the lifetimes of some registers. If an operation requires
91 that constants be loaded into registers, it is certainly desirable
92 to load those constants as early as necessary, but no earlier.
93 I.e., it will not do to load up a bunch of registers at the
94 beginning of a basic block only to use them at the end, if they
95 could be loaded later, since this may result in excessive register
98 Note that since branches are never in basic blocks, but only end
99 basic blocks, this pass will not move branches. But that is ok,
100 since we can use GNU's delayed branch scheduling pass to take care
103 Also note that no further optimizations based on algebraic
104 identities are performed, so this pass would be a good one to
105 perform instruction splitting, such as breaking up a multiply
106 instruction into shifts and adds where that is profitable.
108 Given the memory aliasing analysis that this pass should perform,
109 it should be possible to remove redundant stores to memory, and to
110 load values from registers instead of hitting memory.
112 Before reload, speculative insns are moved only if a 'proof' exists
113 that no exception will be caused by this, and if no live registers
114 exist that inhibit the motion (live registers constraints are not
115 represented by data dependence edges).
117 This pass must update information that subsequent passes expect to
118 be correct. Namely: reg_n_refs, reg_n_sets, reg_n_deaths,
119 reg_n_calls_crossed, and reg_live_length. Also, BB_HEAD, BB_END.
121 The information in the line number notes is carefully retained by
122 this pass. Notes that refer to the starting and ending of
123 exception regions are also carefully retained by this pass. All
124 other NOTE insns are grouped in their same relative order at the
125 beginning of basic blocks and regions that have been scheduled. */
129 #include "coretypes.h"
134 #include "hard-reg-set.h"
136 #include "function.h"
138 #include "insn-config.h"
139 #include "insn-attr.h"
143 #include "sched-int.h"
146 #ifdef INSN_SCHEDULING
148 /* issue_rate is the number of insns that can be scheduled in the same
149 machine cycle. It can be defined in the config/mach/mach.h file,
150 otherwise we set it to 1. */
152 static int issue_rate
;
154 /* sched-verbose controls the amount of debugging output the
155 scheduler prints. It is controlled by -fsched-verbose=N:
156 N>0 and no -DSR : the output is directed to stderr.
157 N>=10 will direct the printouts to stderr (regardless of -dSR).
159 N=2: bb's probabilities, detailed ready list info, unit/insn info.
160 N=3: rtl at abort point, control-flow, regions info.
161 N=5: dependences info. */
163 static int sched_verbose_param
= 0;
164 int sched_verbose
= 0;
166 /* Debugging file. All printouts are sent to dump, which is always set,
167 either to stderr, or to the dump listing file (-dRS). */
168 FILE *sched_dump
= 0;
170 /* Highest uid before scheduling. */
171 static int old_max_uid
;
173 /* fix_sched_param() is called from toplev.c upon detection
174 of the -fsched-verbose=N option. */
177 fix_sched_param (const char *param
, const char *val
)
179 if (!strcmp (param
, "verbose"))
180 sched_verbose_param
= atoi (val
);
182 warning (0, "fix_sched_param: unknown param: %s", param
);
185 struct haifa_insn_data
*h_i_d
;
187 #define LINE_NOTE(INSN) (h_i_d[INSN_UID (INSN)].line_note)
188 #define INSN_TICK(INSN) (h_i_d[INSN_UID (INSN)].tick)
190 /* Vector indexed by basic block number giving the starting line-number
191 for each basic block. */
192 static rtx
*line_note_head
;
194 /* List of important notes we must keep around. This is a pointer to the
195 last element in the list. */
196 static rtx note_list
;
200 /* An instruction is ready to be scheduled when all insns preceding it
201 have already been scheduled. It is important to ensure that all
202 insns which use its result will not be executed until its result
203 has been computed. An insn is maintained in one of four structures:
205 (P) the "Pending" set of insns which cannot be scheduled until
206 their dependencies have been satisfied.
207 (Q) the "Queued" set of insns that can be scheduled when sufficient
209 (R) the "Ready" list of unscheduled, uncommitted insns.
210 (S) the "Scheduled" list of insns.
212 Initially, all insns are either "Pending" or "Ready" depending on
213 whether their dependencies are satisfied.
215 Insns move from the "Ready" list to the "Scheduled" list as they
216 are committed to the schedule. As this occurs, the insns in the
217 "Pending" list have their dependencies satisfied and move to either
218 the "Ready" list or the "Queued" set depending on whether
219 sufficient time has passed to make them ready. As time passes,
220 insns move from the "Queued" set to the "Ready" list.
222 The "Pending" list (P) are the insns in the INSN_DEPEND of the unscheduled
223 insns, i.e., those that are ready, queued, and pending.
224 The "Queued" set (Q) is implemented by the variable `insn_queue'.
225 The "Ready" list (R) is implemented by the variables `ready' and
227 The "Scheduled" list (S) is the new insn chain built by this pass.
229 The transition (R->S) is implemented in the scheduling loop in
230 `schedule_block' when the best insn to schedule is chosen.
231 The transitions (P->R and P->Q) are implemented in `schedule_insn' as
232 insns move from the ready list to the scheduled list.
233 The transition (Q->R) is implemented in 'queue_to_insn' as time
234 passes or stalls are introduced. */
236 /* Implement a circular buffer to delay instructions until sufficient
237 time has passed. For the new pipeline description interface,
238 MAX_INSN_QUEUE_INDEX is a power of two minus one which is larger
239 than maximal time of instruction execution computed by genattr.c on
240 the base maximal time of functional unit reservations and getting a
241 result. This is the longest time an insn may be queued. */
243 static rtx
*insn_queue
;
244 static int q_ptr
= 0;
245 static int q_size
= 0;
246 #define NEXT_Q(X) (((X)+1) & max_insn_queue_index)
247 #define NEXT_Q_AFTER(X, C) (((X)+C) & max_insn_queue_index)
249 /* The following variable value refers for all current and future
250 reservations of the processor units. */
253 /* The following variable value is size of memory representing all
254 current and future reservations of the processor units. */
255 static size_t dfa_state_size
;
257 /* The following array is used to find the best insn from ready when
258 the automaton pipeline interface is used. */
259 static char *ready_try
;
261 /* Describe the ready list of the scheduler.
262 VEC holds space enough for all insns in the current region. VECLEN
263 says how many exactly.
264 FIRST is the index of the element with the highest priority; i.e. the
265 last one in the ready list, since elements are ordered by ascending
267 N_READY determines how many insns are on the ready list. */
277 static int may_trap_exp (rtx
, int);
279 /* Nonzero iff the address is comprised from at most 1 register. */
280 #define CONST_BASED_ADDRESS_P(x) \
282 || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
283 || (GET_CODE (x) == LO_SUM)) \
284 && (CONSTANT_P (XEXP (x, 0)) \
285 || CONSTANT_P (XEXP (x, 1)))))
287 /* Returns a class that insn with GET_DEST(insn)=x may belong to,
288 as found by analyzing insn's expression. */
291 may_trap_exp (rtx x
, int is_store
)
300 if (code
== MEM
&& may_trap_p (x
))
307 /* The insn uses memory: a volatile load. */
308 if (MEM_VOLATILE_P (x
))
310 /* An exception-free load. */
313 /* A load with 1 base register, to be further checked. */
314 if (CONST_BASED_ADDRESS_P (XEXP (x
, 0)))
315 return PFREE_CANDIDATE
;
316 /* No info on the load, to be further checked. */
317 return PRISKY_CANDIDATE
;
322 int i
, insn_class
= TRAP_FREE
;
324 /* Neither store nor load, check if it may cause a trap. */
327 /* Recursive step: walk the insn... */
328 fmt
= GET_RTX_FORMAT (code
);
329 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
333 int tmp_class
= may_trap_exp (XEXP (x
, i
), is_store
);
334 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
336 else if (fmt
[i
] == 'E')
339 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
341 int tmp_class
= may_trap_exp (XVECEXP (x
, i
, j
), is_store
);
342 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
343 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
347 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
354 /* Classifies insn for the purpose of verifying that it can be
355 moved speculatively, by examining it's patterns, returning:
356 TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
357 TRAP_FREE: non-load insn.
358 IFREE: load from a globally safe location.
359 IRISKY: volatile load.
360 PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
361 being either PFREE or PRISKY. */
364 haifa_classify_insn (rtx insn
)
366 rtx pat
= PATTERN (insn
);
367 int tmp_class
= TRAP_FREE
;
368 int insn_class
= TRAP_FREE
;
371 if (GET_CODE (pat
) == PARALLEL
)
373 int i
, len
= XVECLEN (pat
, 0);
375 for (i
= len
- 1; i
>= 0; i
--)
377 code
= GET_CODE (XVECEXP (pat
, 0, i
));
381 /* Test if it is a 'store'. */
382 tmp_class
= may_trap_exp (XEXP (XVECEXP (pat
, 0, i
), 0), 1);
385 /* Test if it is a store. */
386 tmp_class
= may_trap_exp (SET_DEST (XVECEXP (pat
, 0, i
)), 1);
387 if (tmp_class
== TRAP_RISKY
)
389 /* Test if it is a load. */
391 = WORST_CLASS (tmp_class
,
392 may_trap_exp (SET_SRC (XVECEXP (pat
, 0, i
)),
397 tmp_class
= TRAP_RISKY
;
402 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
403 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
409 code
= GET_CODE (pat
);
413 /* Test if it is a 'store'. */
414 tmp_class
= may_trap_exp (XEXP (pat
, 0), 1);
417 /* Test if it is a store. */
418 tmp_class
= may_trap_exp (SET_DEST (pat
), 1);
419 if (tmp_class
== TRAP_RISKY
)
421 /* Test if it is a load. */
423 WORST_CLASS (tmp_class
,
424 may_trap_exp (SET_SRC (pat
), 0));
428 tmp_class
= TRAP_RISKY
;
432 insn_class
= tmp_class
;
438 /* Forward declarations. */
440 static int priority (rtx
);
441 static int rank_for_schedule (const void *, const void *);
442 static void swap_sort (rtx
*, int);
443 static void queue_insn (rtx
, int);
444 static int schedule_insn (rtx
, struct ready_list
*, int);
445 static int find_set_reg_weight (rtx
);
446 static void find_insn_reg_weight (int);
447 static void adjust_priority (rtx
);
448 static void advance_one_cycle (void);
450 /* Notes handling mechanism:
451 =========================
452 Generally, NOTES are saved before scheduling and restored after scheduling.
453 The scheduler distinguishes between three types of notes:
455 (1) LINE_NUMBER notes, generated and used for debugging. Here,
456 before scheduling a region, a pointer to the LINE_NUMBER note is
457 added to the insn following it (in save_line_notes()), and the note
458 is removed (in rm_line_notes() and unlink_line_notes()). After
459 scheduling the region, this pointer is used for regeneration of
460 the LINE_NUMBER note (in restore_line_notes()).
462 (2) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes:
463 Before scheduling a region, a pointer to the note is added to the insn
464 that follows or precedes it. (This happens as part of the data dependence
465 computation). After scheduling an insn, the pointer contained in it is
466 used for regenerating the corresponding note (in reemit_notes).
468 (3) All other notes (e.g. INSN_DELETED): Before scheduling a block,
469 these notes are put in a list (in rm_other_notes() and
470 unlink_other_notes ()). After scheduling the block, these notes are
471 inserted at the beginning of the block (in schedule_block()). */
473 static rtx
unlink_other_notes (rtx
, rtx
);
474 static rtx
unlink_line_notes (rtx
, rtx
);
475 static rtx
reemit_notes (rtx
, rtx
);
477 static rtx
*ready_lastpos (struct ready_list
*);
478 static void ready_sort (struct ready_list
*);
479 static rtx
ready_remove_first (struct ready_list
*);
481 static void queue_to_ready (struct ready_list
*);
482 static int early_queue_to_ready (state_t
, struct ready_list
*);
484 static void debug_ready_list (struct ready_list
*);
486 static rtx
move_insn1 (rtx
, rtx
);
487 static rtx
move_insn (rtx
, rtx
);
489 /* The following functions are used to implement multi-pass scheduling
490 on the first cycle. */
491 static rtx
ready_element (struct ready_list
*, int);
492 static rtx
ready_remove (struct ready_list
*, int);
493 static int max_issue (struct ready_list
*, int *);
495 static rtx
choose_ready (struct ready_list
*);
497 #endif /* INSN_SCHEDULING */
499 /* Point to state used for the current scheduling pass. */
500 struct sched_info
*current_sched_info
;
502 #ifndef INSN_SCHEDULING
504 schedule_insns (FILE *dump_file ATTRIBUTE_UNUSED
)
509 /* Pointer to the last instruction scheduled. Used by rank_for_schedule,
510 so that insns independent of the last scheduled insn will be preferred
511 over dependent instructions. */
513 static rtx last_scheduled_insn
;
515 /* Compute cost of executing INSN given the dependence LINK on the insn USED.
516 This is the number of cycles between instruction issue and
517 instruction results. */
520 insn_cost (rtx insn
, rtx link
, rtx used
)
522 int cost
= INSN_COST (insn
);
526 /* A USE insn, or something else we don't need to
527 understand. We can't pass these directly to
528 result_ready_cost or insn_default_latency because it will
529 trigger a fatal error for unrecognizable insns. */
530 if (recog_memoized (insn
) < 0)
532 INSN_COST (insn
) = 0;
537 cost
= insn_default_latency (insn
);
541 INSN_COST (insn
) = cost
;
545 /* In this case estimate cost without caring how insn is used. */
546 if (link
== 0 || used
== 0)
549 /* A USE insn should never require the value used to be computed.
550 This allows the computation of a function's result and parameter
551 values to overlap the return and call. */
552 if (recog_memoized (used
) < 0)
556 if (INSN_CODE (insn
) >= 0)
558 if (REG_NOTE_KIND (link
) == REG_DEP_ANTI
)
560 else if (REG_NOTE_KIND (link
) == REG_DEP_OUTPUT
)
562 cost
= (insn_default_latency (insn
)
563 - insn_default_latency (used
));
567 else if (bypass_p (insn
))
568 cost
= insn_latency (insn
, used
);
571 if (targetm
.sched
.adjust_cost
)
572 cost
= targetm
.sched
.adjust_cost (used
, link
, insn
, cost
);
581 /* Compute the priority number for INSN. */
591 if (! INSN_PRIORITY_KNOWN (insn
))
593 int this_priority
= 0;
595 if (INSN_DEPEND (insn
) == 0)
596 this_priority
= insn_cost (insn
, 0, 0);
599 for (link
= INSN_DEPEND (insn
); link
; link
= XEXP (link
, 1))
604 next
= XEXP (link
, 0);
606 /* Critical path is meaningful in block boundaries only. */
607 if (! (*current_sched_info
->contributes_to_priority
) (next
, insn
))
610 next_priority
= insn_cost (insn
, link
, next
) + priority (next
);
611 if (next_priority
> this_priority
)
612 this_priority
= next_priority
;
615 INSN_PRIORITY (insn
) = this_priority
;
616 INSN_PRIORITY_KNOWN (insn
) = 1;
619 return INSN_PRIORITY (insn
);
622 /* Macros and functions for keeping the priority queue sorted, and
623 dealing with queuing and dequeuing of instructions. */
625 #define SCHED_SORT(READY, N_READY) \
626 do { if ((N_READY) == 2) \
627 swap_sort (READY, N_READY); \
628 else if ((N_READY) > 2) \
629 qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \
632 /* Returns a positive value if x is preferred; returns a negative value if
633 y is preferred. Should never return 0, since that will make the sort
637 rank_for_schedule (const void *x
, const void *y
)
639 rtx tmp
= *(const rtx
*) y
;
640 rtx tmp2
= *(const rtx
*) x
;
642 int tmp_class
, tmp2_class
, depend_count1
, depend_count2
;
643 int val
, priority_val
, weight_val
, info_val
;
645 /* The insn in a schedule group should be issued the first. */
646 if (SCHED_GROUP_P (tmp
) != SCHED_GROUP_P (tmp2
))
647 return SCHED_GROUP_P (tmp2
) ? 1 : -1;
649 /* Prefer insn with higher priority. */
650 priority_val
= INSN_PRIORITY (tmp2
) - INSN_PRIORITY (tmp
);
655 /* Prefer an insn with smaller contribution to registers-pressure. */
656 if (!reload_completed
&&
657 (weight_val
= INSN_REG_WEIGHT (tmp
) - INSN_REG_WEIGHT (tmp2
)))
660 info_val
= (*current_sched_info
->rank
) (tmp
, tmp2
);
664 /* Compare insns based on their relation to the last-scheduled-insn. */
665 if (last_scheduled_insn
)
667 /* Classify the instructions into three classes:
668 1) Data dependent on last schedule insn.
669 2) Anti/Output dependent on last scheduled insn.
670 3) Independent of last scheduled insn, or has latency of one.
671 Choose the insn from the highest numbered class if different. */
672 link
= find_insn_list (tmp
, INSN_DEPEND (last_scheduled_insn
));
673 if (link
== 0 || insn_cost (last_scheduled_insn
, link
, tmp
) == 1)
675 else if (REG_NOTE_KIND (link
) == 0) /* Data dependence. */
680 link
= find_insn_list (tmp2
, INSN_DEPEND (last_scheduled_insn
));
681 if (link
== 0 || insn_cost (last_scheduled_insn
, link
, tmp2
) == 1)
683 else if (REG_NOTE_KIND (link
) == 0) /* Data dependence. */
688 if ((val
= tmp2_class
- tmp_class
))
692 /* Prefer the insn which has more later insns that depend on it.
693 This gives the scheduler more freedom when scheduling later
694 instructions at the expense of added register pressure. */
696 for (link
= INSN_DEPEND (tmp
); link
; link
= XEXP (link
, 1))
700 for (link
= INSN_DEPEND (tmp2
); link
; link
= XEXP (link
, 1))
703 val
= depend_count2
- depend_count1
;
707 /* If insns are equally good, sort by INSN_LUID (original insn order),
708 so that we make the sort stable. This minimizes instruction movement,
709 thus minimizing sched's effect on debugging and cross-jumping. */
710 return INSN_LUID (tmp
) - INSN_LUID (tmp2
);
713 /* Resort the array A in which only element at index N may be out of order. */
715 HAIFA_INLINE
static void
716 swap_sort (rtx
*a
, int n
)
721 while (i
>= 0 && rank_for_schedule (a
+ i
, &insn
) >= 0)
729 /* Add INSN to the insn queue so that it can be executed at least
730 N_CYCLES after the currently executing insn. Preserve insns
731 chain for debugging purposes. */
733 HAIFA_INLINE
static void
734 queue_insn (rtx insn
, int n_cycles
)
736 int next_q
= NEXT_Q_AFTER (q_ptr
, n_cycles
);
737 rtx link
= alloc_INSN_LIST (insn
, insn_queue
[next_q
]);
738 insn_queue
[next_q
] = link
;
741 if (sched_verbose
>= 2)
743 fprintf (sched_dump
, ";;\t\tReady-->Q: insn %s: ",
744 (*current_sched_info
->print_insn
) (insn
, 0));
746 fprintf (sched_dump
, "queued for %d cycles.\n", n_cycles
);
750 /* Return a pointer to the bottom of the ready list, i.e. the insn
751 with the lowest priority. */
753 HAIFA_INLINE
static rtx
*
754 ready_lastpos (struct ready_list
*ready
)
756 gcc_assert (ready
->n_ready
);
757 return ready
->vec
+ ready
->first
- ready
->n_ready
+ 1;
760 /* Add an element INSN to the ready list so that it ends up with the lowest
764 ready_add (struct ready_list
*ready
, rtx insn
)
766 if (ready
->first
== ready
->n_ready
)
768 memmove (ready
->vec
+ ready
->veclen
- ready
->n_ready
,
769 ready_lastpos (ready
),
770 ready
->n_ready
* sizeof (rtx
));
771 ready
->first
= ready
->veclen
- 1;
773 ready
->vec
[ready
->first
- ready
->n_ready
] = insn
;
777 /* Remove the element with the highest priority from the ready list and
780 HAIFA_INLINE
static rtx
781 ready_remove_first (struct ready_list
*ready
)
785 gcc_assert (ready
->n_ready
);
786 t
= ready
->vec
[ready
->first
--];
788 /* If the queue becomes empty, reset it. */
789 if (ready
->n_ready
== 0)
790 ready
->first
= ready
->veclen
- 1;
794 /* The following code implements multi-pass scheduling for the first
795 cycle. In other words, we will try to choose ready insn which
796 permits to start maximum number of insns on the same cycle. */
798 /* Return a pointer to the element INDEX from the ready. INDEX for
799 insn with the highest priority is 0, and the lowest priority has
802 HAIFA_INLINE
static rtx
803 ready_element (struct ready_list
*ready
, int index
)
805 gcc_assert (ready
->n_ready
&& index
< ready
->n_ready
);
807 return ready
->vec
[ready
->first
- index
];
810 /* Remove the element INDEX from the ready list and return it. INDEX
811 for insn with the highest priority is 0, and the lowest priority
814 HAIFA_INLINE
static rtx
815 ready_remove (struct ready_list
*ready
, int index
)
821 return ready_remove_first (ready
);
822 gcc_assert (ready
->n_ready
&& index
< ready
->n_ready
);
823 t
= ready
->vec
[ready
->first
- index
];
825 for (i
= index
; i
< ready
->n_ready
; i
++)
826 ready
->vec
[ready
->first
- i
] = ready
->vec
[ready
->first
- i
- 1];
831 /* Sort the ready list READY by ascending priority, using the SCHED_SORT
834 HAIFA_INLINE
static void
835 ready_sort (struct ready_list
*ready
)
837 rtx
*first
= ready_lastpos (ready
);
838 SCHED_SORT (first
, ready
->n_ready
);
841 /* PREV is an insn that is ready to execute. Adjust its priority if that
842 will help shorten or lengthen register lifetimes as appropriate. Also
843 provide a hook for the target to tweek itself. */
845 HAIFA_INLINE
static void
846 adjust_priority (rtx prev
)
848 /* ??? There used to be code here to try and estimate how an insn
849 affected register lifetimes, but it did it by looking at REG_DEAD
850 notes, which we removed in schedule_region. Nor did it try to
851 take into account register pressure or anything useful like that.
853 Revisit when we have a machine model to work with and not before. */
855 if (targetm
.sched
.adjust_priority
)
856 INSN_PRIORITY (prev
) =
857 targetm
.sched
.adjust_priority (prev
, INSN_PRIORITY (prev
));
860 /* Advance time on one cycle. */
861 HAIFA_INLINE
static void
862 advance_one_cycle (void)
864 if (targetm
.sched
.dfa_pre_cycle_insn
)
865 state_transition (curr_state
,
866 targetm
.sched
.dfa_pre_cycle_insn ());
868 state_transition (curr_state
, NULL
);
870 if (targetm
.sched
.dfa_post_cycle_insn
)
871 state_transition (curr_state
,
872 targetm
.sched
.dfa_post_cycle_insn ());
875 /* Clock at which the previous instruction was issued. */
876 static int last_clock_var
;
878 /* INSN is the "currently executing insn". Launch each insn which was
879 waiting on INSN. READY is the ready list which contains the insns
880 that are ready to fire. CLOCK is the current cycle. The function
881 returns necessary cycle advance after issuing the insn (it is not
882 zero for insns in a schedule group). */
885 schedule_insn (rtx insn
, struct ready_list
*ready
, int clock
)
889 int premature_issue
= 0;
891 if (sched_verbose
>= 1)
895 print_insn (buf
, insn
, 0);
897 fprintf (sched_dump
, ";;\t%3i--> %-40s:", clock
, buf
);
899 if (recog_memoized (insn
) < 0)
900 fprintf (sched_dump
, "nothing");
902 print_reservation (sched_dump
, insn
);
903 fputc ('\n', sched_dump
);
906 if (INSN_TICK (insn
) > clock
)
908 /* 'insn' has been prematurely moved from the queue to the
910 premature_issue
= INSN_TICK (insn
) - clock
;
913 for (link
= INSN_DEPEND (insn
); link
!= 0; link
= XEXP (link
, 1))
915 rtx next
= XEXP (link
, 0);
916 int cost
= insn_cost (insn
, link
, next
);
918 INSN_TICK (next
) = MAX (INSN_TICK (next
), clock
+ cost
+ premature_issue
);
920 if ((INSN_DEP_COUNT (next
) -= 1) == 0)
922 int effective_cost
= INSN_TICK (next
) - clock
;
924 if (! (*current_sched_info
->new_ready
) (next
))
927 if (sched_verbose
>= 2)
929 fprintf (sched_dump
, ";;\t\tdependences resolved: insn %s ",
930 (*current_sched_info
->print_insn
) (next
, 0));
932 if (effective_cost
< 1)
933 fprintf (sched_dump
, "into ready\n");
935 fprintf (sched_dump
, "into queue with cost=%d\n",
939 /* Adjust the priority of NEXT and either put it on the ready
941 adjust_priority (next
);
942 if (effective_cost
< 1)
943 ready_add (ready
, next
);
946 queue_insn (next
, effective_cost
);
948 if (SCHED_GROUP_P (next
) && advance
< effective_cost
)
949 advance
= effective_cost
;
954 /* Annotate the instruction with issue information -- TImode
955 indicates that the instruction is expected not to be able
956 to issue on the same cycle as the previous insn. A machine
957 may use this information to decide how the instruction should
960 && GET_CODE (PATTERN (insn
)) != USE
961 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
963 if (reload_completed
)
964 PUT_MODE (insn
, clock
> last_clock_var
? TImode
: VOIDmode
);
965 last_clock_var
= clock
;
970 /* Functions for handling of notes. */
972 /* Delete notes beginning with INSN and put them in the chain
973 of notes ended by NOTE_LIST.
974 Returns the insn following the notes. */
977 unlink_other_notes (rtx insn
, rtx tail
)
979 rtx prev
= PREV_INSN (insn
);
981 while (insn
!= tail
&& NOTE_P (insn
))
983 rtx next
= NEXT_INSN (insn
);
984 /* Delete the note from its current position. */
986 NEXT_INSN (prev
) = next
;
988 PREV_INSN (next
) = prev
;
990 /* See sched_analyze to see how these are handled. */
991 if (NOTE_LINE_NUMBER (insn
) != NOTE_INSN_LOOP_BEG
992 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_LOOP_END
993 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_BASIC_BLOCK
994 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_EH_REGION_BEG
995 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_EH_REGION_END
)
997 /* Insert the note at the end of the notes list. */
998 PREV_INSN (insn
) = note_list
;
1000 NEXT_INSN (note_list
) = insn
;
1009 /* Delete line notes beginning with INSN. Record line-number notes so
1010 they can be reused. Returns the insn following the notes. */
1013 unlink_line_notes (rtx insn
, rtx tail
)
1015 rtx prev
= PREV_INSN (insn
);
1017 while (insn
!= tail
&& NOTE_P (insn
))
1019 rtx next
= NEXT_INSN (insn
);
1021 if (write_symbols
!= NO_DEBUG
&& NOTE_LINE_NUMBER (insn
) > 0)
1023 /* Delete the note from its current position. */
1025 NEXT_INSN (prev
) = next
;
1027 PREV_INSN (next
) = prev
;
1029 /* Record line-number notes so they can be reused. */
1030 LINE_NOTE (insn
) = insn
;
1040 /* Return the head and tail pointers of BB. */
1043 get_block_head_tail (int b
, rtx
*headp
, rtx
*tailp
)
1045 /* HEAD and TAIL delimit the basic block being scheduled. */
1046 rtx head
= BB_HEAD (BASIC_BLOCK (b
));
1047 rtx tail
= BB_END (BASIC_BLOCK (b
));
1049 /* Don't include any notes or labels at the beginning of the
1050 basic block, or notes at the ends of basic blocks. */
1051 while (head
!= tail
)
1054 head
= NEXT_INSN (head
);
1055 else if (NOTE_P (tail
))
1056 tail
= PREV_INSN (tail
);
1057 else if (LABEL_P (head
))
1058 head
= NEXT_INSN (head
);
1067 /* Return nonzero if there are no real insns in the range [ HEAD, TAIL ]. */
1070 no_real_insns_p (rtx head
, rtx tail
)
1072 while (head
!= NEXT_INSN (tail
))
1074 if (!NOTE_P (head
) && !LABEL_P (head
))
1076 head
= NEXT_INSN (head
);
1081 /* Delete line notes from one block. Save them so they can be later restored
1082 (in restore_line_notes). HEAD and TAIL are the boundaries of the
1083 block in which notes should be processed. */
1086 rm_line_notes (rtx head
, rtx tail
)
1091 next_tail
= NEXT_INSN (tail
);
1092 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
1096 /* Farm out notes, and maybe save them in NOTE_LIST.
1097 This is needed to keep the debugger from
1098 getting completely deranged. */
1102 insn
= unlink_line_notes (insn
, next_tail
);
1104 gcc_assert (prev
!= tail
&& prev
!= head
&& insn
!= next_tail
);
1109 /* Save line number notes for each insn in block B. HEAD and TAIL are
1110 the boundaries of the block in which notes should be processed. */
1113 save_line_notes (int b
, rtx head
, rtx tail
)
1117 /* We must use the true line number for the first insn in the block
1118 that was computed and saved at the start of this pass. We can't
1119 use the current line number, because scheduling of the previous
1120 block may have changed the current line number. */
1122 rtx line
= line_note_head
[b
];
1125 next_tail
= NEXT_INSN (tail
);
1127 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
1128 if (NOTE_P (insn
) && NOTE_LINE_NUMBER (insn
) > 0)
1131 LINE_NOTE (insn
) = line
;
1134 /* After a block was scheduled, insert line notes into the insns list.
1135 HEAD and TAIL are the boundaries of the block in which notes should
1139 restore_line_notes (rtx head
, rtx tail
)
1141 rtx line
, note
, prev
, new;
1142 int added_notes
= 0;
1143 rtx next_tail
, insn
;
1146 next_tail
= NEXT_INSN (tail
);
1148 /* Determine the current line-number. We want to know the current
1149 line number of the first insn of the block here, in case it is
1150 different from the true line number that was saved earlier. If
1151 different, then we need a line number note before the first insn
1152 of this block. If it happens to be the same, then we don't want to
1153 emit another line number note here. */
1154 for (line
= head
; line
; line
= PREV_INSN (line
))
1155 if (NOTE_P (line
) && NOTE_LINE_NUMBER (line
) > 0)
1158 /* Walk the insns keeping track of the current line-number and inserting
1159 the line-number notes as needed. */
1160 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
1161 if (NOTE_P (insn
) && NOTE_LINE_NUMBER (insn
) > 0)
1163 /* This used to emit line number notes before every non-deleted note.
1164 However, this confuses a debugger, because line notes not separated
1165 by real instructions all end up at the same address. I can find no
1166 use for line number notes before other notes, so none are emitted. */
1167 else if (!NOTE_P (insn
)
1168 && INSN_UID (insn
) < old_max_uid
1169 && (note
= LINE_NOTE (insn
)) != 0
1172 #ifdef USE_MAPPED_LOCATION
1173 || NOTE_SOURCE_LOCATION (note
) != NOTE_SOURCE_LOCATION (line
)
1175 || NOTE_LINE_NUMBER (note
) != NOTE_LINE_NUMBER (line
)
1176 || NOTE_SOURCE_FILE (note
) != NOTE_SOURCE_FILE (line
)
1181 prev
= PREV_INSN (insn
);
1182 if (LINE_NOTE (note
))
1184 /* Re-use the original line-number note. */
1185 LINE_NOTE (note
) = 0;
1186 PREV_INSN (note
) = prev
;
1187 NEXT_INSN (prev
) = note
;
1188 PREV_INSN (insn
) = note
;
1189 NEXT_INSN (note
) = insn
;
1194 new = emit_note_after (NOTE_LINE_NUMBER (note
), prev
);
1195 #ifndef USE_MAPPED_LOCATION
1196 NOTE_SOURCE_FILE (new) = NOTE_SOURCE_FILE (note
);
1200 if (sched_verbose
&& added_notes
)
1201 fprintf (sched_dump
, ";; added %d line-number notes\n", added_notes
);
1204 /* After scheduling the function, delete redundant line notes from the
1208 rm_redundant_line_notes (void)
1211 rtx insn
= get_insns ();
1212 int active_insn
= 0;
1215 /* Walk the insns deleting redundant line-number notes. Many of these
1216 are already present. The remainder tend to occur at basic
1217 block boundaries. */
1218 for (insn
= get_last_insn (); insn
; insn
= PREV_INSN (insn
))
1219 if (NOTE_P (insn
) && NOTE_LINE_NUMBER (insn
) > 0)
1221 /* If there are no active insns following, INSN is redundant. */
1222 if (active_insn
== 0)
1225 SET_INSN_DELETED (insn
);
1227 /* If the line number is unchanged, LINE is redundant. */
1229 #ifdef USE_MAPPED_LOCATION
1230 && NOTE_SOURCE_LOCATION (line
) == NOTE_SOURCE_LOCATION (insn
)
1232 && NOTE_LINE_NUMBER (line
) == NOTE_LINE_NUMBER (insn
)
1233 && NOTE_SOURCE_FILE (line
) == NOTE_SOURCE_FILE (insn
)
1238 SET_INSN_DELETED (line
);
1245 else if (!((NOTE_P (insn
)
1246 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_DELETED
)
1247 || (NONJUMP_INSN_P (insn
)
1248 && (GET_CODE (PATTERN (insn
)) == USE
1249 || GET_CODE (PATTERN (insn
)) == CLOBBER
))))
1252 if (sched_verbose
&& notes
)
1253 fprintf (sched_dump
, ";; deleted %d line-number notes\n", notes
);
1256 /* Delete notes between HEAD and TAIL and put them in the chain
1257 of notes ended by NOTE_LIST. */
1260 rm_other_notes (rtx head
, rtx tail
)
1266 if (head
== tail
&& (! INSN_P (head
)))
1269 next_tail
= NEXT_INSN (tail
);
1270 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
1274 /* Farm out notes, and maybe save them in NOTE_LIST.
1275 This is needed to keep the debugger from
1276 getting completely deranged. */
1281 insn
= unlink_other_notes (insn
, next_tail
);
1283 gcc_assert (prev
!= tail
&& prev
!= head
&& insn
!= next_tail
);
1288 /* Functions for computation of registers live/usage info. */
1290 /* This function looks for a new register being defined.
1291 If the destination register is already used by the source,
1292 a new register is not needed. */
1295 find_set_reg_weight (rtx x
)
1297 if (GET_CODE (x
) == CLOBBER
1298 && register_operand (SET_DEST (x
), VOIDmode
))
1300 if (GET_CODE (x
) == SET
1301 && register_operand (SET_DEST (x
), VOIDmode
))
1303 if (REG_P (SET_DEST (x
)))
1305 if (!reg_mentioned_p (SET_DEST (x
), SET_SRC (x
)))
1315 /* Calculate INSN_REG_WEIGHT for all insns of a block. */
1318 find_insn_reg_weight (int b
)
1320 rtx insn
, next_tail
, head
, tail
;
1322 get_block_head_tail (b
, &head
, &tail
);
1323 next_tail
= NEXT_INSN (tail
);
1325 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
1330 /* Handle register life information. */
1331 if (! INSN_P (insn
))
1334 /* Increment weight for each register born here. */
1336 reg_weight
+= find_set_reg_weight (x
);
1337 if (GET_CODE (x
) == PARALLEL
)
1340 for (j
= XVECLEN (x
, 0) - 1; j
>= 0; j
--)
1342 x
= XVECEXP (PATTERN (insn
), 0, j
);
1343 reg_weight
+= find_set_reg_weight (x
);
1346 /* Decrement weight for each register that dies here. */
1347 for (x
= REG_NOTES (insn
); x
; x
= XEXP (x
, 1))
1349 if (REG_NOTE_KIND (x
) == REG_DEAD
1350 || REG_NOTE_KIND (x
) == REG_UNUSED
)
1354 INSN_REG_WEIGHT (insn
) = reg_weight
;
1358 /* Scheduling clock, modified in schedule_block() and queue_to_ready (). */
1359 static int clock_var
;
1361 /* Move insns that became ready to fire from queue to ready list. */
1364 queue_to_ready (struct ready_list
*ready
)
1369 q_ptr
= NEXT_Q (q_ptr
);
1371 /* Add all pending insns that can be scheduled without stalls to the
1373 for (link
= insn_queue
[q_ptr
]; link
; link
= XEXP (link
, 1))
1375 insn
= XEXP (link
, 0);
1378 if (sched_verbose
>= 2)
1379 fprintf (sched_dump
, ";;\t\tQ-->Ready: insn %s: ",
1380 (*current_sched_info
->print_insn
) (insn
, 0));
1382 ready_add (ready
, insn
);
1383 if (sched_verbose
>= 2)
1384 fprintf (sched_dump
, "moving to ready without stalls\n");
1386 insn_queue
[q_ptr
] = 0;
1388 /* If there are no ready insns, stall until one is ready and add all
1389 of the pending insns at that point to the ready list. */
1390 if (ready
->n_ready
== 0)
1394 for (stalls
= 1; stalls
<= max_insn_queue_index
; stalls
++)
1396 if ((link
= insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)]))
1398 for (; link
; link
= XEXP (link
, 1))
1400 insn
= XEXP (link
, 0);
1403 if (sched_verbose
>= 2)
1404 fprintf (sched_dump
, ";;\t\tQ-->Ready: insn %s: ",
1405 (*current_sched_info
->print_insn
) (insn
, 0));
1407 ready_add (ready
, insn
);
1408 if (sched_verbose
>= 2)
1409 fprintf (sched_dump
, "moving to ready with %d stalls\n", stalls
);
1411 insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)] = 0;
1413 advance_one_cycle ();
1418 advance_one_cycle ();
1421 q_ptr
= NEXT_Q_AFTER (q_ptr
, stalls
);
1422 clock_var
+= stalls
;
1426 /* Used by early_queue_to_ready. Determines whether it is "ok" to
1427 prematurely move INSN from the queue to the ready list. Currently,
1428 if a target defines the hook 'is_costly_dependence', this function
1429 uses the hook to check whether there exist any dependences which are
1430 considered costly by the target, between INSN and other insns that
1431 have already been scheduled. Dependences are checked up to Y cycles
1432 back, with default Y=1; The flag -fsched-stalled-insns-dep=Y allows
1433 controlling this value.
1434 (Other considerations could be taken into account instead (or in
1435 addition) depending on user flags and target hooks. */
1438 ok_for_early_queue_removal (rtx insn
)
1441 rtx prev_insn
= last_scheduled_insn
;
1443 if (targetm
.sched
.is_costly_dependence
)
1445 for (n_cycles
= flag_sched_stalled_insns_dep
; n_cycles
; n_cycles
--)
1447 for ( ; prev_insn
; prev_insn
= PREV_INSN (prev_insn
))
1452 if (!NOTE_P (prev_insn
))
1454 dep_link
= find_insn_list (insn
, INSN_DEPEND (prev_insn
));
1457 dep_cost
= insn_cost (prev_insn
, dep_link
, insn
) ;
1458 if (targetm
.sched
.is_costly_dependence (prev_insn
, insn
,
1460 flag_sched_stalled_insns_dep
- n_cycles
))
1465 if (GET_MODE (prev_insn
) == TImode
) /* end of dispatch group */
1471 prev_insn
= PREV_INSN (prev_insn
);
1479 /* Remove insns from the queue, before they become "ready" with respect
1480 to FU latency considerations. */
1483 early_queue_to_ready (state_t state
, struct ready_list
*ready
)
1491 state_t temp_state
= alloca (dfa_state_size
);
1493 int insns_removed
= 0;
1496 Flag '-fsched-stalled-insns=X' determines the aggressiveness of this
1499 X == 0: There is no limit on how many queued insns can be removed
1500 prematurely. (flag_sched_stalled_insns = -1).
1502 X >= 1: Only X queued insns can be removed prematurely in each
1503 invocation. (flag_sched_stalled_insns = X).
1505 Otherwise: Early queue removal is disabled.
1506 (flag_sched_stalled_insns = 0)
1509 if (! flag_sched_stalled_insns
)
1512 for (stalls
= 0; stalls
<= max_insn_queue_index
; stalls
++)
1514 if ((link
= insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)]))
1516 if (sched_verbose
> 6)
1517 fprintf (sched_dump
, ";; look at index %d + %d\n", q_ptr
, stalls
);
1522 next_link
= XEXP (link
, 1);
1523 insn
= XEXP (link
, 0);
1524 if (insn
&& sched_verbose
> 6)
1525 print_rtl_single (sched_dump
, insn
);
1527 memcpy (temp_state
, state
, dfa_state_size
);
1528 if (recog_memoized (insn
) < 0)
1529 /* non-negative to indicate that it's not ready
1530 to avoid infinite Q->R->Q->R... */
1533 cost
= state_transition (temp_state
, insn
);
1535 if (sched_verbose
>= 6)
1536 fprintf (sched_dump
, "transition cost = %d\n", cost
);
1538 move_to_ready
= false;
1541 move_to_ready
= ok_for_early_queue_removal (insn
);
1542 if (move_to_ready
== true)
1544 /* move from Q to R */
1546 ready_add (ready
, insn
);
1549 XEXP (prev_link
, 1) = next_link
;
1551 insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)] = next_link
;
1553 free_INSN_LIST_node (link
);
1555 if (sched_verbose
>= 2)
1556 fprintf (sched_dump
, ";;\t\tEarly Q-->Ready: insn %s\n",
1557 (*current_sched_info
->print_insn
) (insn
, 0));
1560 if (insns_removed
== flag_sched_stalled_insns
)
1561 /* Remove only one insn from Q at a time. */
1562 return insns_removed
;
1566 if (move_to_ready
== false)
1573 } /* for stalls.. */
1575 return insns_removed
;
1579 /* Print the ready list for debugging purposes. Callable from debugger. */
1582 debug_ready_list (struct ready_list
*ready
)
1587 if (ready
->n_ready
== 0)
1589 fprintf (sched_dump
, "\n");
1593 p
= ready_lastpos (ready
);
1594 for (i
= 0; i
< ready
->n_ready
; i
++)
1595 fprintf (sched_dump
, " %s", (*current_sched_info
->print_insn
) (p
[i
], 0));
1596 fprintf (sched_dump
, "\n");
1599 /* move_insn1: Remove INSN from insn chain, and link it after LAST insn. */
1602 move_insn1 (rtx insn
, rtx last
)
1604 NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
1605 PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
1607 NEXT_INSN (insn
) = NEXT_INSN (last
);
1608 PREV_INSN (NEXT_INSN (last
)) = insn
;
1610 NEXT_INSN (last
) = insn
;
1611 PREV_INSN (insn
) = last
;
1616 /* Search INSN for REG_SAVE_NOTE note pairs for
1617 NOTE_INSN_{LOOP,EHREGION}_{BEG,END}; and convert them back into
1618 NOTEs. The REG_SAVE_NOTE note following first one is contains the
1619 saved value for NOTE_BLOCK_NUMBER which is useful for
1620 NOTE_INSN_EH_REGION_{BEG,END} NOTEs. LAST is the last instruction
1621 output by the instruction scheduler. Return the new value of LAST. */
1624 reemit_notes (rtx insn
, rtx last
)
1629 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1631 if (REG_NOTE_KIND (note
) == REG_SAVE_NOTE
)
1633 enum insn_note note_type
= INTVAL (XEXP (note
, 0));
1635 last
= emit_note_before (note_type
, last
);
1636 remove_note (insn
, note
);
1642 /* Move INSN. Reemit notes if needed.
1644 Return the last insn emitted by the scheduler, which is the
1645 return value from the first call to reemit_notes. */
1648 move_insn (rtx insn
, rtx last
)
1652 move_insn1 (insn
, last
);
1654 /* If this is the first call to reemit_notes, then record
1655 its return value. */
1656 if (retval
== NULL_RTX
)
1657 retval
= reemit_notes (insn
, insn
);
1659 reemit_notes (insn
, insn
);
1661 SCHED_GROUP_P (insn
) = 0;
1666 /* The following structure describe an entry of the stack of choices. */
1669 /* Ordinal number of the issued insn in the ready queue. */
1671 /* The number of the rest insns whose issues we should try. */
1673 /* The number of issued essential insns. */
1675 /* State after issuing the insn. */
1679 /* The following array is used to implement a stack of choices used in
1680 function max_issue. */
1681 static struct choice_entry
*choice_stack
;
1683 /* The following variable value is number of essential insns issued on
1684 the current cycle. An insn is essential one if it changes the
1685 processors state. */
1686 static int cycle_issued_insns
;
1688 /* The following variable value is maximal number of tries of issuing
1689 insns for the first cycle multipass insn scheduling. We define
1690 this value as constant*(DFA_LOOKAHEAD**ISSUE_RATE). We would not
1691 need this constraint if all real insns (with non-negative codes)
1692 had reservations because in this case the algorithm complexity is
1693 O(DFA_LOOKAHEAD**ISSUE_RATE). Unfortunately, the dfa descriptions
1694 might be incomplete and such insn might occur. For such
1695 descriptions, the complexity of algorithm (without the constraint)
1696 could achieve DFA_LOOKAHEAD ** N , where N is the queue length. */
1697 static int max_lookahead_tries
;
1699 /* The following value is value of hook
1700 `first_cycle_multipass_dfa_lookahead' at the last call of
1702 static int cached_first_cycle_multipass_dfa_lookahead
= 0;
1704 /* The following value is value of `issue_rate' at the last call of
1706 static int cached_issue_rate
= 0;
1708 /* The following function returns maximal (or close to maximal) number
1709 of insns which can be issued on the same cycle and one of which
1710 insns is insns with the best rank (the first insn in READY). To
1711 make this function tries different samples of ready insns. READY
1712 is current queue `ready'. Global array READY_TRY reflects what
1713 insns are already issued in this try. INDEX will contain index
1714 of the best insn in READY. The following function is used only for
1715 first cycle multipass scheduling. */
1717 max_issue (struct ready_list
*ready
, int *index
)
1719 int n
, i
, all
, n_ready
, best
, delay
, tries_num
;
1720 struct choice_entry
*top
;
1724 memcpy (choice_stack
->state
, curr_state
, dfa_state_size
);
1726 top
->rest
= cached_first_cycle_multipass_dfa_lookahead
;
1728 n_ready
= ready
->n_ready
;
1729 for (all
= i
= 0; i
< n_ready
; i
++)
1736 if (top
->rest
== 0 || i
>= n_ready
)
1738 if (top
== choice_stack
)
1740 if (best
< top
- choice_stack
&& ready_try
[0])
1742 best
= top
- choice_stack
;
1743 *index
= choice_stack
[1].index
;
1744 if (top
->n
== issue_rate
- cycle_issued_insns
|| best
== all
)
1750 memcpy (curr_state
, top
->state
, dfa_state_size
);
1752 else if (!ready_try
[i
])
1755 if (tries_num
> max_lookahead_tries
)
1757 insn
= ready_element (ready
, i
);
1758 delay
= state_transition (curr_state
, insn
);
1761 if (state_dead_lock_p (curr_state
))
1766 if (memcmp (top
->state
, curr_state
, dfa_state_size
) != 0)
1769 top
->rest
= cached_first_cycle_multipass_dfa_lookahead
;
1772 memcpy (top
->state
, curr_state
, dfa_state_size
);
1779 while (top
!= choice_stack
)
1781 ready_try
[top
->index
] = 0;
1784 memcpy (curr_state
, choice_stack
->state
, dfa_state_size
);
1788 /* The following function chooses insn from READY and modifies
1789 *N_READY and READY. The following function is used only for first
1790 cycle multipass scheduling. */
1793 choose_ready (struct ready_list
*ready
)
1797 if (targetm
.sched
.first_cycle_multipass_dfa_lookahead
)
1798 lookahead
= targetm
.sched
.first_cycle_multipass_dfa_lookahead ();
1799 if (lookahead
<= 0 || SCHED_GROUP_P (ready_element (ready
, 0)))
1800 return ready_remove_first (ready
);
1803 /* Try to choose the better insn. */
1807 if (cached_first_cycle_multipass_dfa_lookahead
!= lookahead
)
1809 cached_first_cycle_multipass_dfa_lookahead
= lookahead
;
1810 max_lookahead_tries
= 100;
1811 for (i
= 0; i
< issue_rate
; i
++)
1812 max_lookahead_tries
*= lookahead
;
1814 insn
= ready_element (ready
, 0);
1815 if (INSN_CODE (insn
) < 0)
1816 return ready_remove_first (ready
);
1817 for (i
= 1; i
< ready
->n_ready
; i
++)
1819 insn
= ready_element (ready
, i
);
1821 = (INSN_CODE (insn
) < 0
1822 || (targetm
.sched
.first_cycle_multipass_dfa_lookahead_guard
1823 && !targetm
.sched
.first_cycle_multipass_dfa_lookahead_guard (insn
)));
1825 if (max_issue (ready
, &index
) == 0)
1826 return ready_remove_first (ready
);
1828 return ready_remove (ready
, index
);
1832 /* Use forward list scheduling to rearrange insns of block B in region RGN,
1833 possibly bringing insns from subsequent blocks in the same region. */
1836 schedule_block (int b
, int rgn_n_insns
)
1838 struct ready_list ready
;
1839 int i
, first_cycle_insn_p
;
1841 state_t temp_state
= NULL
; /* It is used for multipass scheduling. */
1842 int sort_p
, advance
, start_clock_var
;
1844 /* Head/tail info for this block. */
1845 rtx prev_head
= current_sched_info
->prev_head
;
1846 rtx next_tail
= current_sched_info
->next_tail
;
1847 rtx head
= NEXT_INSN (prev_head
);
1848 rtx tail
= PREV_INSN (next_tail
);
1850 /* We used to have code to avoid getting parameters moved from hard
1851 argument registers into pseudos.
1853 However, it was removed when it proved to be of marginal benefit
1854 and caused problems because schedule_block and compute_forward_dependences
1855 had different notions of what the "head" insn was. */
1857 gcc_assert (head
!= tail
|| INSN_P (head
));
1862 fprintf (sched_dump
,
1863 ";; ======================================================\n");
1864 fprintf (sched_dump
,
1865 ";; -- basic block %d from %d to %d -- %s reload\n",
1866 b
, INSN_UID (head
), INSN_UID (tail
),
1867 (reload_completed
? "after" : "before"));
1868 fprintf (sched_dump
,
1869 ";; ======================================================\n");
1870 fprintf (sched_dump
, "\n");
1873 state_reset (curr_state
);
1875 /* Allocate the ready list. */
1876 ready
.veclen
= rgn_n_insns
+ 1 + issue_rate
;
1877 ready
.first
= ready
.veclen
- 1;
1878 ready
.vec
= xmalloc (ready
.veclen
* sizeof (rtx
));
1881 /* It is used for first cycle multipass scheduling. */
1882 temp_state
= alloca (dfa_state_size
);
1883 ready_try
= xcalloc ((rgn_n_insns
+ 1), sizeof (char));
1884 choice_stack
= xmalloc ((rgn_n_insns
+ 1)
1885 * sizeof (struct choice_entry
));
1886 for (i
= 0; i
<= rgn_n_insns
; i
++)
1887 choice_stack
[i
].state
= xmalloc (dfa_state_size
);
1889 (*current_sched_info
->init_ready_list
) (&ready
);
1891 if (targetm
.sched
.md_init
)
1892 targetm
.sched
.md_init (sched_dump
, sched_verbose
, ready
.veclen
);
1894 /* We start inserting insns after PREV_HEAD. */
1895 last_scheduled_insn
= prev_head
;
1897 /* Initialize INSN_QUEUE. Q_SIZE is the total number of insns in the
1902 insn_queue
= alloca ((max_insn_queue_index
+ 1) * sizeof (rtx
));
1903 memset (insn_queue
, 0, (max_insn_queue_index
+ 1) * sizeof (rtx
));
1904 last_clock_var
= -1;
1906 /* Start just before the beginning of time. */
1911 /* Loop until all the insns in BB are scheduled. */
1912 while ((*current_sched_info
->schedule_more_p
) ())
1916 start_clock_var
= clock_var
;
1920 advance_one_cycle ();
1922 /* Add to the ready list all pending insns that can be issued now.
1923 If there are no ready insns, increment clock until one
1924 is ready and add all pending insns at that point to the ready
1926 queue_to_ready (&ready
);
1928 gcc_assert (ready
.n_ready
);
1930 if (sched_verbose
>= 2)
1932 fprintf (sched_dump
, ";;\t\tReady list after queue_to_ready: ");
1933 debug_ready_list (&ready
);
1935 advance
-= clock_var
- start_clock_var
;
1937 while (advance
> 0);
1941 /* Sort the ready list based on priority. */
1942 ready_sort (&ready
);
1944 if (sched_verbose
>= 2)
1946 fprintf (sched_dump
, ";;\t\tReady list after ready_sort: ");
1947 debug_ready_list (&ready
);
1951 /* Allow the target to reorder the list, typically for
1952 better instruction bundling. */
1953 if (sort_p
&& targetm
.sched
.reorder
1954 && (ready
.n_ready
== 0
1955 || !SCHED_GROUP_P (ready_element (&ready
, 0))))
1957 targetm
.sched
.reorder (sched_dump
, sched_verbose
,
1958 ready_lastpos (&ready
),
1959 &ready
.n_ready
, clock_var
);
1961 can_issue_more
= issue_rate
;
1963 first_cycle_insn_p
= 1;
1964 cycle_issued_insns
= 0;
1971 if (sched_verbose
>= 2)
1973 fprintf (sched_dump
, ";;\tReady list (t =%3d): ",
1975 debug_ready_list (&ready
);
1978 if (ready
.n_ready
== 0
1980 && reload_completed
)
1982 /* Allow scheduling insns directly from the queue in case
1983 there's nothing better to do (ready list is empty) but
1984 there are still vacant dispatch slots in the current cycle. */
1985 if (sched_verbose
>= 6)
1986 fprintf(sched_dump
,";;\t\tSecond chance\n");
1987 memcpy (temp_state
, curr_state
, dfa_state_size
);
1988 if (early_queue_to_ready (temp_state
, &ready
))
1989 ready_sort (&ready
);
1992 if (ready
.n_ready
== 0 || !can_issue_more
1993 || state_dead_lock_p (curr_state
)
1994 || !(*current_sched_info
->schedule_more_p
) ())
1997 /* Select and remove the insn from the ready list. */
1999 insn
= choose_ready (&ready
);
2001 insn
= ready_remove_first (&ready
);
2003 if (targetm
.sched
.dfa_new_cycle
2004 && targetm
.sched
.dfa_new_cycle (sched_dump
, sched_verbose
,
2005 insn
, last_clock_var
,
2006 clock_var
, &sort_p
))
2008 ready_add (&ready
, insn
);
2013 memcpy (temp_state
, curr_state
, dfa_state_size
);
2014 if (recog_memoized (insn
) < 0)
2016 asm_p
= (GET_CODE (PATTERN (insn
)) == ASM_INPUT
2017 || asm_noperands (PATTERN (insn
)) >= 0);
2018 if (!first_cycle_insn_p
&& asm_p
)
2019 /* This is asm insn which is tryed to be issued on the
2020 cycle not first. Issue it on the next cycle. */
2023 /* A USE insn, or something else we don't need to
2024 understand. We can't pass these directly to
2025 state_transition because it will trigger a
2026 fatal error for unrecognizable insns. */
2031 cost
= state_transition (temp_state
, insn
);
2040 queue_insn (insn
, cost
);
2041 if (SCHED_GROUP_P (insn
))
2050 if (! (*current_sched_info
->can_schedule_ready_p
) (insn
))
2053 last_scheduled_insn
= move_insn (insn
, last_scheduled_insn
);
2055 if (memcmp (curr_state
, temp_state
, dfa_state_size
) != 0)
2056 cycle_issued_insns
++;
2057 memcpy (curr_state
, temp_state
, dfa_state_size
);
2059 if (targetm
.sched
.variable_issue
)
2061 targetm
.sched
.variable_issue (sched_dump
, sched_verbose
,
2062 insn
, can_issue_more
);
2063 /* A naked CLOBBER or USE generates no instruction, so do
2064 not count them against the issue rate. */
2065 else if (GET_CODE (PATTERN (insn
)) != USE
2066 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
2069 advance
= schedule_insn (insn
, &ready
, clock_var
);
2071 /* After issuing an asm insn we should start a new cycle. */
2072 if (advance
== 0 && asm_p
)
2078 first_cycle_insn_p
= 0;
2080 /* Sort the ready list based on priority. This must be
2081 redone here, as schedule_insn may have readied additional
2082 insns that will not be sorted correctly. */
2083 if (ready
.n_ready
> 0)
2084 ready_sort (&ready
);
2086 if (targetm
.sched
.reorder2
2087 && (ready
.n_ready
== 0
2088 || !SCHED_GROUP_P (ready_element (&ready
, 0))))
2091 targetm
.sched
.reorder2 (sched_dump
, sched_verbose
,
2093 ? ready_lastpos (&ready
) : NULL
,
2094 &ready
.n_ready
, clock_var
);
2099 if (targetm
.sched
.md_finish
)
2100 targetm
.sched
.md_finish (sched_dump
, sched_verbose
);
2105 fprintf (sched_dump
, ";;\tReady list (final): ");
2106 debug_ready_list (&ready
);
2109 /* Sanity check -- queue must be empty now. Meaningless if region has
2111 gcc_assert (!current_sched_info
->queue_must_finish_empty
|| !q_size
);
2113 /* Update head/tail boundaries. */
2114 head
= NEXT_INSN (prev_head
);
2115 tail
= last_scheduled_insn
;
2117 if (!reload_completed
)
2119 rtx insn
, link
, next
;
2121 /* INSN_TICK (minimum clock tick at which the insn becomes
2122 ready) may be not correct for the insn in the subsequent
2123 blocks of the region. We should use a correct value of
2124 `clock_var' or modify INSN_TICK. It is better to keep
2125 clock_var value equal to 0 at the start of a basic block.
2126 Therefore we modify INSN_TICK here. */
2127 for (insn
= head
; insn
!= tail
; insn
= NEXT_INSN (insn
))
2130 for (link
= INSN_DEPEND (insn
); link
!= 0; link
= XEXP (link
, 1))
2132 next
= XEXP (link
, 0);
2133 INSN_TICK (next
) -= clock_var
;
2138 /* Restore-other-notes: NOTE_LIST is the end of a chain of notes
2139 previously found among the insns. Insert them at the beginning
2143 rtx note_head
= note_list
;
2145 while (PREV_INSN (note_head
))
2147 note_head
= PREV_INSN (note_head
);
2150 PREV_INSN (note_head
) = PREV_INSN (head
);
2151 NEXT_INSN (PREV_INSN (head
)) = note_head
;
2152 PREV_INSN (head
) = note_list
;
2153 NEXT_INSN (note_list
) = head
;
2160 fprintf (sched_dump
, ";; total time = %d\n;; new head = %d\n",
2161 clock_var
, INSN_UID (head
));
2162 fprintf (sched_dump
, ";; new tail = %d\n\n",
2166 current_sched_info
->head
= head
;
2167 current_sched_info
->tail
= tail
;
2172 for (i
= 0; i
<= rgn_n_insns
; i
++)
2173 free (choice_stack
[i
].state
);
2174 free (choice_stack
);
2177 /* Set_priorities: compute priority of each insn in the block. */
2180 set_priorities (rtx head
, rtx tail
)
2184 int sched_max_insns_priority
=
2185 current_sched_info
->sched_max_insns_priority
;
2188 prev_head
= PREV_INSN (head
);
2190 if (head
== tail
&& (! INSN_P (head
)))
2194 sched_max_insns_priority
= 0;
2195 for (insn
= tail
; insn
!= prev_head
; insn
= PREV_INSN (insn
))
2201 (void) priority (insn
);
2203 if (INSN_PRIORITY_KNOWN (insn
))
2204 sched_max_insns_priority
=
2205 MAX (sched_max_insns_priority
, INSN_PRIORITY (insn
));
2207 sched_max_insns_priority
+= 1;
2208 current_sched_info
->sched_max_insns_priority
=
2209 sched_max_insns_priority
;
2214 /* Initialize some global state for the scheduler. DUMP_FILE is to be used
2215 for debugging output. */
2218 sched_init (FILE *dump_file
)
2225 /* Disable speculative loads in their presence if cc0 defined. */
2227 flag_schedule_speculative_load
= 0;
2230 /* Set dump and sched_verbose for the desired debugging output. If no
2231 dump-file was specified, but -fsched-verbose=N (any N), print to stderr.
2232 For -fsched-verbose=N, N>=10, print everything to stderr. */
2233 sched_verbose
= sched_verbose_param
;
2234 if (sched_verbose_param
== 0 && dump_file
)
2236 sched_dump
= ((sched_verbose_param
>= 10 || !dump_file
)
2237 ? stderr
: dump_file
);
2239 /* Initialize issue_rate. */
2240 if (targetm
.sched
.issue_rate
)
2241 issue_rate
= targetm
.sched
.issue_rate ();
2245 if (cached_issue_rate
!= issue_rate
)
2247 cached_issue_rate
= issue_rate
;
2248 /* To invalidate max_lookahead_tries: */
2249 cached_first_cycle_multipass_dfa_lookahead
= 0;
2252 /* We use LUID 0 for the fake insn (UID 0) which holds dependencies for
2253 pseudos which do not cross calls. */
2254 old_max_uid
= get_max_uid () + 1;
2256 h_i_d
= xcalloc (old_max_uid
, sizeof (*h_i_d
));
2258 for (i
= 0; i
< old_max_uid
; i
++)
2259 h_i_d
[i
].cost
= -1;
2261 if (targetm
.sched
.init_dfa_pre_cycle_insn
)
2262 targetm
.sched
.init_dfa_pre_cycle_insn ();
2264 if (targetm
.sched
.init_dfa_post_cycle_insn
)
2265 targetm
.sched
.init_dfa_post_cycle_insn ();
2268 dfa_state_size
= state_size ();
2269 curr_state
= xmalloc (dfa_state_size
);
2274 for (insn
= BB_HEAD (b
); ; insn
= NEXT_INSN (insn
))
2276 INSN_LUID (insn
) = luid
;
2278 /* Increment the next luid, unless this is a note. We don't
2279 really need separate IDs for notes and we don't want to
2280 schedule differently depending on whether or not there are
2281 line-number notes, i.e., depending on whether or not we're
2282 generating debugging information. */
2286 if (insn
== BB_END (b
))
2290 init_dependency_caches (luid
);
2292 init_alias_analysis ();
2294 if (write_symbols
!= NO_DEBUG
)
2298 line_note_head
= xcalloc (last_basic_block
, sizeof (rtx
));
2300 /* Save-line-note-head:
2301 Determine the line-number at the start of each basic block.
2302 This must be computed and saved now, because after a basic block's
2303 predecessor has been scheduled, it is impossible to accurately
2304 determine the correct line number for the first insn of the block. */
2308 for (line
= BB_HEAD (b
); line
; line
= PREV_INSN (line
))
2309 if (NOTE_P (line
) && NOTE_LINE_NUMBER (line
) > 0)
2311 line_note_head
[b
->index
] = line
;
2314 /* Do a forward search as well, since we won't get to see the first
2315 notes in a basic block. */
2316 for (line
= BB_HEAD (b
); line
; line
= NEXT_INSN (line
))
2320 if (NOTE_P (line
) && NOTE_LINE_NUMBER (line
) > 0)
2321 line_note_head
[b
->index
] = line
;
2326 /* ??? Add a NOTE after the last insn of the last basic block. It is not
2327 known why this is done. */
2329 insn
= BB_END (EXIT_BLOCK_PTR
->prev_bb
);
2330 if (NEXT_INSN (insn
) == 0
2333 /* Don't emit a NOTE if it would end up before a BARRIER. */
2334 && !BARRIER_P (NEXT_INSN (insn
))))
2336 emit_note_after (NOTE_INSN_DELETED
, BB_END (EXIT_BLOCK_PTR
->prev_bb
));
2337 /* Make insn to appear outside BB. */
2338 BB_END (EXIT_BLOCK_PTR
->prev_bb
) = PREV_INSN (BB_END (EXIT_BLOCK_PTR
->prev_bb
));
2341 /* Compute INSN_REG_WEIGHT for all blocks. We must do this before
2342 removing death notes. */
2343 FOR_EACH_BB_REVERSE (b
)
2344 find_insn_reg_weight (b
->index
);
2346 if (targetm
.sched
.md_init_global
)
2347 targetm
.sched
.md_init_global (sched_dump
, sched_verbose
, old_max_uid
);
2350 /* Free global data used during insn scheduling. */
2358 free_dependency_caches ();
2359 end_alias_analysis ();
2360 if (write_symbols
!= NO_DEBUG
)
2361 free (line_note_head
);
2363 if (targetm
.sched
.md_finish_global
)
2364 targetm
.sched
.md_finish_global (sched_dump
, sched_verbose
);
2366 #endif /* INSN_SCHEDULING */