1 /* Instruction scheduling pass.
2 Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000, 2001 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 GNU CC.
9 GNU CC is free software; you can redistribute it and/or modify it
10 under the terms of the GNU General Public License as published by the
11 Free Software Foundation; either version 2, or (at your option) any
14 GNU CC is distributed in the hope that it will be useful, but WITHOUT
15 ANY 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 GNU CC; see the file COPYING. If not, write to the Free
21 the Free Software Foundation, 59 Temple Place - Suite 330, 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 Function unit conflicts are resolved during forward list scheduling
58 by tracking the time when each insn is committed to the schedule
59 and from that, the time the function units it uses must be free.
60 As insns on the ready list are considered for scheduling, those
61 that would result in a blockage of the already committed insns are
62 queued until no blockage will result.
64 The following list shows the order in which we want to break ties
65 among insns in the ready list:
67 1. choose insn with the longest path to end of bb, ties
69 2. choose insn with least contribution to register pressure,
71 3. prefer in-block upon interblock motion, ties broken by
72 4. prefer useful upon speculative motion, ties broken by
73 5. choose insn with largest control flow probability, ties
75 6. choose insn with the least dependences upon the previously
76 scheduled insn, or finally
77 7 choose the insn which has the most insns dependent on it.
78 8. choose insn with lowest UID.
80 Memory references complicate matters. Only if we can be certain
81 that memory references are not part of the data dependency graph
82 (via true, anti, or output dependence), can we move operations past
83 memory references. To first approximation, reads can be done
84 independently, while writes introduce dependencies. Better
85 approximations will yield fewer dependencies.
87 Before reload, an extended analysis of interblock data dependences
88 is required for interblock scheduling. This is performed in
89 compute_block_backward_dependences ().
91 Dependencies set up by memory references are treated in exactly the
92 same way as other dependencies, by using LOG_LINKS backward
93 dependences. LOG_LINKS are translated into INSN_DEPEND forward
94 dependences for the purpose of forward list scheduling.
96 Having optimized the critical path, we may have also unduly
97 extended the lifetimes of some registers. If an operation requires
98 that constants be loaded into registers, it is certainly desirable
99 to load those constants as early as necessary, but no earlier.
100 I.e., it will not do to load up a bunch of registers at the
101 beginning of a basic block only to use them at the end, if they
102 could be loaded later, since this may result in excessive register
105 Note that since branches are never in basic blocks, but only end
106 basic blocks, this pass will not move branches. But that is ok,
107 since we can use GNU's delayed branch scheduling pass to take care
110 Also note that no further optimizations based on algebraic
111 identities are performed, so this pass would be a good one to
112 perform instruction splitting, such as breaking up a multiply
113 instruction into shifts and adds where that is profitable.
115 Given the memory aliasing analysis that this pass should perform,
116 it should be possible to remove redundant stores to memory, and to
117 load values from registers instead of hitting memory.
119 Before reload, speculative insns are moved only if a 'proof' exists
120 that no exception will be caused by this, and if no live registers
121 exist that inhibit the motion (live registers constraints are not
122 represented by data dependence edges).
124 This pass must update information that subsequent passes expect to
125 be correct. Namely: reg_n_refs, reg_n_sets, reg_n_deaths,
126 reg_n_calls_crossed, and reg_live_length. Also, BLOCK_HEAD,
129 The information in the line number notes is carefully retained by
130 this pass. Notes that refer to the starting and ending of
131 exception regions are also carefully retained by this pass. All
132 other NOTE insns are grouped in their same relative order at the
133 beginning of basic blocks and regions that have been scheduled. */
140 #include "hard-reg-set.h"
141 #include "basic-block.h"
143 #include "function.h"
145 #include "insn-config.h"
146 #include "insn-attr.h"
150 #include "sched-int.h"
152 #ifdef INSN_SCHEDULING
154 /* issue_rate is the number of insns that can be scheduled in the same
155 machine cycle. It can be defined in the config/mach/mach.h file,
156 otherwise we set it to 1. */
158 static int issue_rate;
164 /* sched-verbose controls the amount of debugging output the
165 scheduler prints. It is controlled by -fsched-verbose=N:
166 N>0 and no -DSR : the output is directed to stderr.
167 N>=10 will direct the printouts to stderr (regardless of -dSR).
169 N=2: bb's probabilities, detailed ready list info, unit/insn info.
170 N=3: rtl at abort point, control-flow, regions info.
171 N=5: dependences info. */
173 static int sched_verbose_param = 0;
174 int sched_verbose = 0;
176 /* Debugging file. All printouts are sent to dump, which is always set,
177 either to stderr, or to the dump listing file (-dRS). */
178 FILE *sched_dump = 0;
180 /* Highest uid before scheduling. */
181 static int old_max_uid;
183 /* fix_sched_param() is called from toplev.c upon detection
184 of the -fsched-verbose=N option. */
187 fix_sched_param (param, val)
188 const char *param, *val;
190 if (!strcmp (param, "verbose"))
191 sched_verbose_param = atoi (val);
193 warning ("fix_sched_param: unknown param: %s", param);
196 struct haifa_insn_data *h_i_d;
198 #define DONE_PRIORITY -1
199 #define MAX_PRIORITY 0x7fffffff
200 #define TAIL_PRIORITY 0x7ffffffe
201 #define LAUNCH_PRIORITY 0x7f000001
202 #define DONE_PRIORITY_P(INSN) (INSN_PRIORITY (INSN) < 0)
203 #define LOW_PRIORITY_P(INSN) ((INSN_PRIORITY (INSN) & 0x7f000000) == 0)
205 #define LINE_NOTE(INSN) (h_i_d[INSN_UID (INSN)].line_note)
206 #define INSN_TICK(INSN) (h_i_d[INSN_UID (INSN)].tick)
208 /* Vector indexed by basic block number giving the starting line-number
209 for each basic block. */
210 static rtx *line_note_head;
212 /* List of important notes we must keep around. This is a pointer to the
213 last element in the list. */
214 static rtx note_list;
218 /* An instruction is ready to be scheduled when all insns preceding it
219 have already been scheduled. It is important to ensure that all
220 insns which use its result will not be executed until its result
221 has been computed. An insn is maintained in one of four structures:
223 (P) the "Pending" set of insns which cannot be scheduled until
224 their dependencies have been satisfied.
225 (Q) the "Queued" set of insns that can be scheduled when sufficient
227 (R) the "Ready" list of unscheduled, uncommitted insns.
228 (S) the "Scheduled" list of insns.
230 Initially, all insns are either "Pending" or "Ready" depending on
231 whether their dependencies are satisfied.
233 Insns move from the "Ready" list to the "Scheduled" list as they
234 are committed to the schedule. As this occurs, the insns in the
235 "Pending" list have their dependencies satisfied and move to either
236 the "Ready" list or the "Queued" set depending on whether
237 sufficient time has passed to make them ready. As time passes,
238 insns move from the "Queued" set to the "Ready" list. Insns may
239 move from the "Ready" list to the "Queued" set if they are blocked
240 due to a function unit conflict.
242 The "Pending" list (P) are the insns in the INSN_DEPEND of the unscheduled
243 insns, i.e., those that are ready, queued, and pending.
244 The "Queued" set (Q) is implemented by the variable `insn_queue'.
245 The "Ready" list (R) is implemented by the variables `ready' and
247 The "Scheduled" list (S) is the new insn chain built by this pass.
249 The transition (R->S) is implemented in the scheduling loop in
250 `schedule_block' when the best insn to schedule is chosen.
251 The transition (R->Q) is implemented in `queue_insn' when an
252 insn is found to have a function unit conflict with the already
254 The transitions (P->R and P->Q) are implemented in `schedule_insn' as
255 insns move from the ready list to the scheduled list.
256 The transition (Q->R) is implemented in 'queue_to_insn' as time
257 passes or stalls are introduced. */
259 /* Implement a circular buffer to delay instructions until sufficient
260 time has passed. INSN_QUEUE_SIZE is a power of two larger than
261 MAX_BLOCKAGE and MAX_READY_COST computed by genattr.c. This is the
262 longest time an isnsn may be queued. */
263 static rtx insn_queue[INSN_QUEUE_SIZE];
264 static int q_ptr = 0;
265 static int q_size = 0;
266 #define NEXT_Q(X) (((X)+1) & (INSN_QUEUE_SIZE-1))
267 #define NEXT_Q_AFTER(X, C) (((X)+C) & (INSN_QUEUE_SIZE-1))
269 /* Describe the ready list of the scheduler.
270 VEC holds space enough for all insns in the current region. VECLEN
271 says how many exactly.
272 FIRST is the index of the element with the highest priority; i.e. the
273 last one in the ready list, since elements are ordered by ascending
275 N_READY determines how many insns are on the ready list. */
285 /* Forward declarations. */
286 static unsigned int blockage_range PARAMS ((int, rtx));
287 static void clear_units PARAMS ((void));
288 static void schedule_unit PARAMS ((int, rtx, int));
289 static int actual_hazard PARAMS ((int, rtx, int, int));
290 static int potential_hazard PARAMS ((int, rtx, int));
291 static int priority PARAMS ((rtx));
292 static int rank_for_schedule PARAMS ((const PTR, const PTR));
293 static void swap_sort PARAMS ((rtx *, int));
294 static void queue_insn PARAMS ((rtx, int));
295 static void schedule_insn PARAMS ((rtx, struct ready_list *, int));
296 static void find_insn_reg_weight PARAMS ((int));
297 static void adjust_priority PARAMS ((rtx));
299 /* Notes handling mechanism:
300 =========================
301 Generally, NOTES are saved before scheduling and restored after scheduling.
302 The scheduler distinguishes between three types of notes:
304 (1) LINE_NUMBER notes, generated and used for debugging. Here,
305 before scheduling a region, a pointer to the LINE_NUMBER note is
306 added to the insn following it (in save_line_notes()), and the note
307 is removed (in rm_line_notes() and unlink_line_notes()). After
308 scheduling the region, this pointer is used for regeneration of
309 the LINE_NUMBER note (in restore_line_notes()).
311 (2) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes:
312 Before scheduling a region, a pointer to the note is added to the insn
313 that follows or precedes it. (This happens as part of the data dependence
314 computation). After scheduling an insn, the pointer contained in it is
315 used for regenerating the corresponding note (in reemit_notes).
317 (3) All other notes (e.g. INSN_DELETED): Before scheduling a block,
318 these notes are put in a list (in rm_other_notes() and
319 unlink_other_notes ()). After scheduling the block, these notes are
320 inserted at the beginning of the block (in schedule_block()). */
322 static rtx unlink_other_notes PARAMS ((rtx, rtx));
323 static rtx unlink_line_notes PARAMS ((rtx, rtx));
324 static rtx reemit_notes PARAMS ((rtx, rtx));
326 static rtx *ready_lastpos PARAMS ((struct ready_list *));
327 static void ready_sort PARAMS ((struct ready_list *));
328 static rtx ready_remove_first PARAMS ((struct ready_list *));
330 static void queue_to_ready PARAMS ((struct ready_list *));
332 static void debug_ready_list PARAMS ((struct ready_list *));
334 static rtx move_insn1 PARAMS ((rtx, rtx));
335 static rtx move_insn PARAMS ((rtx, rtx));
337 #endif /* INSN_SCHEDULING */
339 /* Point to state used for the current scheduling pass. */
340 struct sched_info *current_sched_info;
342 #ifndef INSN_SCHEDULING
344 schedule_insns (dump_file)
345 FILE *dump_file ATTRIBUTE_UNUSED;
350 /* Pointer to the last instruction scheduled. Used by rank_for_schedule,
351 so that insns independent of the last scheduled insn will be preferred
352 over dependent instructions. */
354 static rtx last_scheduled_insn;
356 /* Compute the function units used by INSN. This caches the value
357 returned by function_units_used. A function unit is encoded as the
358 unit number if the value is non-negative and the compliment of a
359 mask if the value is negative. A function unit index is the
360 non-negative encoding. */
366 register int unit = INSN_UNIT (insn);
370 recog_memoized (insn);
372 /* A USE insn, or something else we don't need to understand.
373 We can't pass these directly to function_units_used because it will
374 trigger a fatal error for unrecognizable insns. */
375 if (INSN_CODE (insn) < 0)
379 unit = function_units_used (insn);
380 /* Increment non-negative values so we can cache zero. */
384 /* We only cache 16 bits of the result, so if the value is out of
385 range, don't cache it. */
386 if (FUNCTION_UNITS_SIZE < HOST_BITS_PER_SHORT
388 || (unit & ~((1 << (HOST_BITS_PER_SHORT - 1)) - 1)) == 0)
389 INSN_UNIT (insn) = unit;
391 return (unit > 0 ? unit - 1 : unit);
394 /* Compute the blockage range for executing INSN on UNIT. This caches
395 the value returned by the blockage_range_function for the unit.
396 These values are encoded in an int where the upper half gives the
397 minimum value and the lower half gives the maximum value. */
399 HAIFA_INLINE static unsigned int
400 blockage_range (unit, insn)
404 unsigned int blockage = INSN_BLOCKAGE (insn);
407 if ((int) UNIT_BLOCKED (blockage) != unit + 1)
409 range = function_units[unit].blockage_range_function (insn);
410 /* We only cache the blockage range for one unit and then only if
412 if (HOST_BITS_PER_INT >= UNIT_BITS + 2 * BLOCKAGE_BITS)
413 INSN_BLOCKAGE (insn) = ENCODE_BLOCKAGE (unit + 1, range);
416 range = BLOCKAGE_RANGE (blockage);
421 /* A vector indexed by function unit instance giving the last insn to use
422 the unit. The value of the function unit instance index for unit U
423 instance I is (U + I * FUNCTION_UNITS_SIZE). */
424 static rtx unit_last_insn[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY];
426 /* A vector indexed by function unit instance giving the minimum time when
427 the unit will unblock based on the maximum blockage cost. */
428 static int unit_tick[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY];
430 /* A vector indexed by function unit number giving the number of insns
431 that remain to use the unit. */
432 static int unit_n_insns[FUNCTION_UNITS_SIZE];
434 /* Access the unit_last_insn array. Used by the visualization code. */
437 get_unit_last_insn (instance)
440 return unit_last_insn[instance];
443 /* Reset the function unit state to the null state. */
448 memset ((char *) unit_last_insn, 0, sizeof (unit_last_insn));
449 memset ((char *) unit_tick, 0, sizeof (unit_tick));
450 memset ((char *) unit_n_insns, 0, sizeof (unit_n_insns));
453 /* Return the issue-delay of an insn. */
456 insn_issue_delay (insn)
460 int unit = insn_unit (insn);
462 /* Efficiency note: in fact, we are working 'hard' to compute a
463 value that was available in md file, and is not available in
464 function_units[] structure. It would be nice to have this
468 if (function_units[unit].blockage_range_function &&
469 function_units[unit].blockage_function)
470 delay = function_units[unit].blockage_function (insn, insn);
473 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
474 if ((unit & 1) != 0 && function_units[i].blockage_range_function
475 && function_units[i].blockage_function)
476 delay = MAX (delay, function_units[i].blockage_function (insn, insn));
481 /* Return the actual hazard cost of executing INSN on the unit UNIT,
482 instance INSTANCE at time CLOCK if the previous actual hazard cost
486 actual_hazard_this_instance (unit, instance, insn, clock, cost)
487 int unit, instance, clock, cost;
490 int tick = unit_tick[instance]; /* Issue time of the last issued insn. */
492 if (tick - clock > cost)
494 /* The scheduler is operating forward, so unit's last insn is the
495 executing insn and INSN is the candidate insn. We want a
496 more exact measure of the blockage if we execute INSN at CLOCK
497 given when we committed the execution of the unit's last insn.
499 The blockage value is given by either the unit's max blockage
500 constant, blockage range function, or blockage function. Use
501 the most exact form for the given unit. */
503 if (function_units[unit].blockage_range_function)
505 if (function_units[unit].blockage_function)
506 tick += (function_units[unit].blockage_function
507 (unit_last_insn[instance], insn)
508 - function_units[unit].max_blockage);
510 tick += ((int) MAX_BLOCKAGE_COST (blockage_range (unit, insn))
511 - function_units[unit].max_blockage);
513 if (tick - clock > cost)
519 /* Record INSN as having begun execution on the units encoded by UNIT at
522 HAIFA_INLINE static void
523 schedule_unit (unit, insn, clock)
532 #if MAX_MULTIPLICITY > 1
533 /* Find the first free instance of the function unit and use that
534 one. We assume that one is free. */
535 for (i = function_units[unit].multiplicity - 1; i > 0; i--)
537 if (!actual_hazard_this_instance (unit, instance, insn, clock, 0))
539 instance += FUNCTION_UNITS_SIZE;
542 unit_last_insn[instance] = insn;
543 unit_tick[instance] = (clock + function_units[unit].max_blockage);
546 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
548 schedule_unit (i, insn, clock);
551 /* Return the actual hazard cost of executing INSN on the units encoded by
552 UNIT at time CLOCK if the previous actual hazard cost was COST. */
554 HAIFA_INLINE static int
555 actual_hazard (unit, insn, clock, cost)
556 int unit, clock, cost;
563 /* Find the instance of the function unit with the minimum hazard. */
565 int best_cost = actual_hazard_this_instance (unit, instance, insn,
567 #if MAX_MULTIPLICITY > 1
570 if (best_cost > cost)
572 for (i = function_units[unit].multiplicity - 1; i > 0; i--)
574 instance += FUNCTION_UNITS_SIZE;
575 this_cost = actual_hazard_this_instance (unit, instance, insn,
577 if (this_cost < best_cost)
579 best_cost = this_cost;
580 if (this_cost <= cost)
586 cost = MAX (cost, best_cost);
589 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
591 cost = actual_hazard (i, insn, clock, cost);
596 /* Return the potential hazard cost of executing an instruction on the
597 units encoded by UNIT if the previous potential hazard cost was COST.
598 An insn with a large blockage time is chosen in preference to one
599 with a smaller time; an insn that uses a unit that is more likely
600 to be used is chosen in preference to one with a unit that is less
601 used. We are trying to minimize a subsequent actual hazard. */
603 HAIFA_INLINE static int
604 potential_hazard (unit, insn, cost)
609 unsigned int minb, maxb;
613 minb = maxb = function_units[unit].max_blockage;
616 if (function_units[unit].blockage_range_function)
618 maxb = minb = blockage_range (unit, insn);
619 maxb = MAX_BLOCKAGE_COST (maxb);
620 minb = MIN_BLOCKAGE_COST (minb);
625 /* Make the number of instructions left dominate. Make the
626 minimum delay dominate the maximum delay. If all these
627 are the same, use the unit number to add an arbitrary
628 ordering. Other terms can be added. */
629 ncost = minb * 0x40 + maxb;
630 ncost *= (unit_n_insns[unit] - 1) * 0x1000 + unit;
637 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
639 cost = potential_hazard (i, insn, cost);
644 /* Compute cost of executing INSN given the dependence LINK on the insn USED.
645 This is the number of cycles between instruction issue and
646 instruction results. */
649 insn_cost (insn, link, used)
650 rtx insn, link, used;
652 register int cost = INSN_COST (insn);
656 recog_memoized (insn);
658 /* A USE insn, or something else we don't need to understand.
659 We can't pass these directly to result_ready_cost because it will
660 trigger a fatal error for unrecognizable insns. */
661 if (INSN_CODE (insn) < 0)
663 INSN_COST (insn) = 1;
668 cost = result_ready_cost (insn);
673 INSN_COST (insn) = cost;
677 /* In this case estimate cost without caring how insn is used. */
678 if (link == 0 && used == 0)
681 /* A USE insn should never require the value used to be computed. This
682 allows the computation of a function's result and parameter values to
683 overlap the return and call. */
684 recog_memoized (used);
685 if (INSN_CODE (used) < 0)
686 LINK_COST_FREE (link) = 1;
688 /* If some dependencies vary the cost, compute the adjustment. Most
689 commonly, the adjustment is complete: either the cost is ignored
690 (in the case of an output- or anti-dependence), or the cost is
691 unchanged. These values are cached in the link as LINK_COST_FREE
692 and LINK_COST_ZERO. */
694 if (LINK_COST_FREE (link))
697 else if (!LINK_COST_ZERO (link))
701 ADJUST_COST (used, link, insn, ncost);
704 LINK_COST_FREE (link) = 1;
708 LINK_COST_ZERO (link) = 1;
715 /* Compute the priority number for INSN. */
726 if (! INSN_PRIORITY_KNOWN (insn))
728 int this_priority = 0;
730 if (INSN_DEPEND (insn) == 0)
731 this_priority = insn_cost (insn, 0, 0);
734 for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
739 if (RTX_INTEGRATED_P (link))
742 next = XEXP (link, 0);
744 /* Critical path is meaningful in block boundaries only. */
745 if (! (*current_sched_info->contributes_to_priority) (next, insn))
748 next_priority = insn_cost (insn, link, next) + priority (next);
749 if (next_priority > this_priority)
750 this_priority = next_priority;
753 INSN_PRIORITY (insn) = this_priority;
754 INSN_PRIORITY_KNOWN (insn) = 1;
757 return INSN_PRIORITY (insn);
760 /* Macros and functions for keeping the priority queue sorted, and
761 dealing with queueing and dequeueing of instructions. */
763 #define SCHED_SORT(READY, N_READY) \
764 do { if ((N_READY) == 2) \
765 swap_sort (READY, N_READY); \
766 else if ((N_READY) > 2) \
767 qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \
770 /* Returns a positive value if x is preferred; returns a negative value if
771 y is preferred. Should never return 0, since that will make the sort
775 rank_for_schedule (x, y)
779 rtx tmp = *(const rtx *) y;
780 rtx tmp2 = *(const rtx *) x;
782 int tmp_class, tmp2_class, depend_count1, depend_count2;
783 int val, priority_val, weight_val, info_val;
785 /* Prefer insn with higher priority. */
786 priority_val = INSN_PRIORITY (tmp2) - INSN_PRIORITY (tmp);
790 /* Prefer an insn with smaller contribution to registers-pressure. */
791 if (!reload_completed &&
792 (weight_val = INSN_REG_WEIGHT (tmp) - INSN_REG_WEIGHT (tmp2)))
795 info_val = (*current_sched_info->rank) (tmp, tmp2);
799 /* Compare insns based on their relation to the last-scheduled-insn. */
800 if (last_scheduled_insn)
802 /* Classify the instructions into three classes:
803 1) Data dependent on last schedule insn.
804 2) Anti/Output dependent on last scheduled insn.
805 3) Independent of last scheduled insn, or has latency of one.
806 Choose the insn from the highest numbered class if different. */
807 link = find_insn_list (tmp, INSN_DEPEND (last_scheduled_insn));
808 if (link == 0 || insn_cost (last_scheduled_insn, link, tmp) == 1)
810 else if (REG_NOTE_KIND (link) == 0) /* Data dependence. */
815 link = find_insn_list (tmp2, INSN_DEPEND (last_scheduled_insn));
816 if (link == 0 || insn_cost (last_scheduled_insn, link, tmp2) == 1)
818 else if (REG_NOTE_KIND (link) == 0) /* Data dependence. */
823 if ((val = tmp2_class - tmp_class))
827 /* Prefer the insn which has more later insns that depend on it.
828 This gives the scheduler more freedom when scheduling later
829 instructions at the expense of added register pressure. */
831 for (link = INSN_DEPEND (tmp); link; link = XEXP (link, 1))
835 for (link = INSN_DEPEND (tmp2); link; link = XEXP (link, 1))
838 val = depend_count2 - depend_count1;
842 /* If insns are equally good, sort by INSN_LUID (original insn order),
843 so that we make the sort stable. This minimizes instruction movement,
844 thus minimizing sched's effect on debugging and cross-jumping. */
845 return INSN_LUID (tmp) - INSN_LUID (tmp2);
848 /* Resort the array A in which only element at index N may be out of order. */
850 HAIFA_INLINE static void
858 while (i >= 0 && rank_for_schedule (a + i, &insn) >= 0)
866 /* Add INSN to the insn queue so that it can be executed at least
867 N_CYCLES after the currently executing insn. Preserve insns
868 chain for debugging purposes. */
870 HAIFA_INLINE static void
871 queue_insn (insn, n_cycles)
875 int next_q = NEXT_Q_AFTER (q_ptr, n_cycles);
876 rtx link = alloc_INSN_LIST (insn, insn_queue[next_q]);
877 insn_queue[next_q] = link;
880 if (sched_verbose >= 2)
882 fprintf (sched_dump, ";;\t\tReady-->Q: insn %s: ",
883 (*current_sched_info->print_insn) (insn, 0));
885 fprintf (sched_dump, "queued for %d cycles.\n", n_cycles);
889 /* Return a pointer to the bottom of the ready list, i.e. the insn
890 with the lowest priority. */
892 HAIFA_INLINE static rtx *
893 ready_lastpos (ready)
894 struct ready_list *ready;
896 if (ready->n_ready == 0)
898 return ready->vec + ready->first - ready->n_ready + 1;
901 /* Add an element INSN to the ready list so that it ends up with the lowest
905 ready_add (ready, insn)
906 struct ready_list *ready;
909 if (ready->first == ready->n_ready)
911 memmove (ready->vec + ready->veclen - ready->n_ready,
912 ready_lastpos (ready),
913 ready->n_ready * sizeof (rtx));
914 ready->first = ready->veclen - 1;
916 ready->vec[ready->first - ready->n_ready] = insn;
920 /* Remove the element with the highest priority from the ready list and
923 HAIFA_INLINE static rtx
924 ready_remove_first (ready)
925 struct ready_list *ready;
928 if (ready->n_ready == 0)
930 t = ready->vec[ready->first--];
932 /* If the queue becomes empty, reset it. */
933 if (ready->n_ready == 0)
934 ready->first = ready->veclen - 1;
938 /* Sort the ready list READY by ascending priority, using the SCHED_SORT
941 HAIFA_INLINE static void
943 struct ready_list *ready;
945 rtx *first = ready_lastpos (ready);
946 SCHED_SORT (first, ready->n_ready);
949 /* PREV is an insn that is ready to execute. Adjust its priority if that
950 will help shorten or lengthen register lifetimes as appropriate. Also
951 provide a hook for the target to tweek itself. */
953 HAIFA_INLINE static void
954 adjust_priority (prev)
955 rtx prev ATTRIBUTE_UNUSED;
957 /* ??? There used to be code here to try and estimate how an insn
958 affected register lifetimes, but it did it by looking at REG_DEAD
959 notes, which we removed in schedule_region. Nor did it try to
960 take into account register pressure or anything useful like that.
962 Revisit when we have a machine model to work with and not before. */
964 #ifdef ADJUST_PRIORITY
965 ADJUST_PRIORITY (prev);
969 /* Clock at which the previous instruction was issued. */
970 static int last_clock_var;
972 /* INSN is the "currently executing insn". Launch each insn which was
973 waiting on INSN. READY is the ready list which contains the insns
974 that are ready to fire. CLOCK is the current cycle.
978 schedule_insn (insn, ready, clock)
980 struct ready_list *ready;
986 unit = insn_unit (insn);
988 if (sched_verbose >= 2)
990 fprintf (sched_dump, ";;\t\t--> scheduling insn <<<%d>>> on unit ",
992 insn_print_units (insn);
993 fprintf (sched_dump, "\n");
996 if (sched_verbose && unit == -1)
997 visualize_no_unit (insn);
999 if (MAX_BLOCKAGE > 1 || issue_rate > 1 || sched_verbose)
1000 schedule_unit (unit, insn, clock);
1002 if (INSN_DEPEND (insn) == 0)
1005 for (link = INSN_DEPEND (insn); link != 0; link = XEXP (link, 1))
1007 rtx next = XEXP (link, 0);
1008 int cost = insn_cost (insn, link, next);
1010 INSN_TICK (next) = MAX (INSN_TICK (next), clock + cost);
1012 if ((INSN_DEP_COUNT (next) -= 1) == 0)
1014 int effective_cost = INSN_TICK (next) - clock;
1016 if (! (*current_sched_info->new_ready) (next))
1019 if (sched_verbose >= 2)
1021 fprintf (sched_dump, ";;\t\tdependences resolved: insn %s ",
1022 (*current_sched_info->print_insn) (next, 0));
1024 if (effective_cost < 1)
1025 fprintf (sched_dump, "into ready\n");
1027 fprintf (sched_dump, "into queue with cost=%d\n", effective_cost);
1030 /* Adjust the priority of NEXT and either put it on the ready
1031 list or queue it. */
1032 adjust_priority (next);
1033 if (effective_cost < 1)
1034 ready_add (ready, next);
1036 queue_insn (next, effective_cost);
1040 /* Annotate the instruction with issue information -- TImode
1041 indicates that the instruction is expected not to be able
1042 to issue on the same cycle as the previous insn. A machine
1043 may use this information to decide how the instruction should
1045 if (reload_completed && issue_rate > 1)
1047 PUT_MODE (insn, clock > last_clock_var ? TImode : VOIDmode);
1048 last_clock_var = clock;
1052 /* Functions for handling of notes. */
1054 /* Delete notes beginning with INSN and put them in the chain
1055 of notes ended by NOTE_LIST.
1056 Returns the insn following the notes. */
1059 unlink_other_notes (insn, tail)
1062 rtx prev = PREV_INSN (insn);
1064 while (insn != tail && GET_CODE (insn) == NOTE)
1066 rtx next = NEXT_INSN (insn);
1067 /* Delete the note from its current position. */
1069 NEXT_INSN (prev) = next;
1071 PREV_INSN (next) = prev;
1073 /* See sched_analyze to see how these are handled. */
1074 if (NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG
1075 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_END
1076 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_RANGE_BEG
1077 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_RANGE_END
1078 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_BEG
1079 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_END)
1081 /* Insert the note at the end of the notes list. */
1082 PREV_INSN (insn) = note_list;
1084 NEXT_INSN (note_list) = insn;
1093 /* Delete line notes beginning with INSN. Record line-number notes so
1094 they can be reused. Returns the insn following the notes. */
1097 unlink_line_notes (insn, tail)
1100 rtx prev = PREV_INSN (insn);
1102 while (insn != tail && GET_CODE (insn) == NOTE)
1104 rtx next = NEXT_INSN (insn);
1106 if (write_symbols != NO_DEBUG && NOTE_LINE_NUMBER (insn) > 0)
1108 /* Delete the note from its current position. */
1110 NEXT_INSN (prev) = next;
1112 PREV_INSN (next) = prev;
1114 /* Record line-number notes so they can be reused. */
1115 LINE_NOTE (insn) = insn;
1125 /* Return the head and tail pointers of BB. */
1128 get_block_head_tail (b, headp, tailp)
1133 /* HEAD and TAIL delimit the basic block being scheduled. */
1134 rtx head = BLOCK_HEAD (b);
1135 rtx tail = BLOCK_END (b);
1137 /* Don't include any notes or labels at the beginning of the
1138 basic block, or notes at the ends of basic blocks. */
1139 while (head != tail)
1141 if (GET_CODE (head) == NOTE)
1142 head = NEXT_INSN (head);
1143 else if (GET_CODE (tail) == NOTE)
1144 tail = PREV_INSN (tail);
1145 else if (GET_CODE (head) == CODE_LABEL)
1146 head = NEXT_INSN (head);
1155 /* Return nonzero if there are no real insns in the range [ HEAD, TAIL ]. */
1158 no_real_insns_p (head, tail)
1161 while (head != NEXT_INSN (tail))
1163 if (GET_CODE (head) != NOTE && GET_CODE (head) != CODE_LABEL)
1165 head = NEXT_INSN (head);
1170 /* Delete line notes from one block. Save them so they can be later restored
1171 (in restore_line_notes). HEAD and TAIL are the boundaries of the
1172 block in which notes should be processed. */
1175 rm_line_notes (head, tail)
1181 next_tail = NEXT_INSN (tail);
1182 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
1186 /* Farm out notes, and maybe save them in NOTE_LIST.
1187 This is needed to keep the debugger from
1188 getting completely deranged. */
1189 if (GET_CODE (insn) == NOTE)
1192 insn = unlink_line_notes (insn, next_tail);
1198 if (insn == next_tail)
1204 /* Save line number notes for each insn in block B. HEAD and TAIL are
1205 the boundaries of the block in which notes should be processed.*/
1208 save_line_notes (b, head, tail)
1214 /* We must use the true line number for the first insn in the block
1215 that was computed and saved at the start of this pass. We can't
1216 use the current line number, because scheduling of the previous
1217 block may have changed the current line number. */
1219 rtx line = line_note_head[b];
1222 next_tail = NEXT_INSN (tail);
1224 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
1225 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
1228 LINE_NOTE (insn) = line;
1231 /* After a block was scheduled, insert line notes into the insns list.
1232 HEAD and TAIL are the boundaries of the block in which notes should
1236 restore_line_notes (head, tail)
1239 rtx line, note, prev, new;
1240 int added_notes = 0;
1241 rtx next_tail, insn;
1244 next_tail = NEXT_INSN (tail);
1246 /* Determine the current line-number. We want to know the current
1247 line number of the first insn of the block here, in case it is
1248 different from the true line number that was saved earlier. If
1249 different, then we need a line number note before the first insn
1250 of this block. If it happens to be the same, then we don't want to
1251 emit another line number note here. */
1252 for (line = head; line; line = PREV_INSN (line))
1253 if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
1256 /* Walk the insns keeping track of the current line-number and inserting
1257 the line-number notes as needed. */
1258 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
1259 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
1261 /* This used to emit line number notes before every non-deleted note.
1262 However, this confuses a debugger, because line notes not separated
1263 by real instructions all end up at the same address. I can find no
1264 use for line number notes before other notes, so none are emitted. */
1265 else if (GET_CODE (insn) != NOTE
1266 && INSN_UID (insn) < old_max_uid
1267 && (note = LINE_NOTE (insn)) != 0
1270 || NOTE_LINE_NUMBER (note) != NOTE_LINE_NUMBER (line)
1271 || NOTE_SOURCE_FILE (note) != NOTE_SOURCE_FILE (line)))
1274 prev = PREV_INSN (insn);
1275 if (LINE_NOTE (note))
1277 /* Re-use the original line-number note. */
1278 LINE_NOTE (note) = 0;
1279 PREV_INSN (note) = prev;
1280 NEXT_INSN (prev) = note;
1281 PREV_INSN (insn) = note;
1282 NEXT_INSN (note) = insn;
1287 new = emit_note_after (NOTE_LINE_NUMBER (note), prev);
1288 NOTE_SOURCE_FILE (new) = NOTE_SOURCE_FILE (note);
1289 RTX_INTEGRATED_P (new) = RTX_INTEGRATED_P (note);
1292 if (sched_verbose && added_notes)
1293 fprintf (sched_dump, ";; added %d line-number notes\n", added_notes);
1296 /* After scheduling the function, delete redundant line notes from the
1300 rm_redundant_line_notes ()
1303 rtx insn = get_insns ();
1304 int active_insn = 0;
1307 /* Walk the insns deleting redundant line-number notes. Many of these
1308 are already present. The remainder tend to occur at basic
1309 block boundaries. */
1310 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
1311 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
1313 /* If there are no active insns following, INSN is redundant. */
1314 if (active_insn == 0)
1317 NOTE_SOURCE_FILE (insn) = 0;
1318 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
1320 /* If the line number is unchanged, LINE is redundant. */
1322 && NOTE_LINE_NUMBER (line) == NOTE_LINE_NUMBER (insn)
1323 && NOTE_SOURCE_FILE (line) == NOTE_SOURCE_FILE (insn))
1326 NOTE_SOURCE_FILE (line) = 0;
1327 NOTE_LINE_NUMBER (line) = NOTE_INSN_DELETED;
1334 else if (!((GET_CODE (insn) == NOTE
1335 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED)
1336 || (GET_CODE (insn) == INSN
1337 && (GET_CODE (PATTERN (insn)) == USE
1338 || GET_CODE (PATTERN (insn)) == CLOBBER))))
1341 if (sched_verbose && notes)
1342 fprintf (sched_dump, ";; deleted %d line-number notes\n", notes);
1345 /* Delete notes between HEAD and TAIL and put them in the chain
1346 of notes ended by NOTE_LIST. */
1349 rm_other_notes (head, tail)
1357 if (head == tail && (! INSN_P (head)))
1360 next_tail = NEXT_INSN (tail);
1361 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
1365 /* Farm out notes, and maybe save them in NOTE_LIST.
1366 This is needed to keep the debugger from
1367 getting completely deranged. */
1368 if (GET_CODE (insn) == NOTE)
1372 insn = unlink_other_notes (insn, next_tail);
1378 if (insn == next_tail)
1384 /* Functions for computation of registers live/usage info. */
1386 /* Calculate INSN_REG_WEIGHT for all insns of a block. */
1389 find_insn_reg_weight (b)
1392 rtx insn, next_tail, head, tail;
1394 get_block_head_tail (b, &head, &tail);
1395 next_tail = NEXT_INSN (tail);
1397 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
1402 /* Handle register life information. */
1403 if (! INSN_P (insn))
1406 /* Increment weight for each register born here. */
1408 if ((GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
1409 && register_operand (SET_DEST (x), VOIDmode))
1411 else if (GET_CODE (x) == PARALLEL)
1414 for (j = XVECLEN (x, 0) - 1; j >= 0; j--)
1416 x = XVECEXP (PATTERN (insn), 0, j);
1417 if ((GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
1418 && register_operand (SET_DEST (x), VOIDmode))
1423 /* Decrement weight for each register that dies here. */
1424 for (x = REG_NOTES (insn); x; x = XEXP (x, 1))
1426 if (REG_NOTE_KIND (x) == REG_DEAD
1427 || REG_NOTE_KIND (x) == REG_UNUSED)
1431 INSN_REG_WEIGHT (insn) = reg_weight;
1435 /* Scheduling clock, modified in schedule_block() and queue_to_ready (). */
1436 static int clock_var;
1438 /* Move insns that became ready to fire from queue to ready list. */
1441 queue_to_ready (ready)
1442 struct ready_list *ready;
1447 q_ptr = NEXT_Q (q_ptr);
1449 /* Add all pending insns that can be scheduled without stalls to the
1451 for (link = insn_queue[q_ptr]; link; link = XEXP (link, 1))
1453 insn = XEXP (link, 0);
1456 if (sched_verbose >= 2)
1457 fprintf (sched_dump, ";;\t\tQ-->Ready: insn %s: ",
1458 (*current_sched_info->print_insn) (insn, 0));
1460 ready_add (ready, insn);
1461 if (sched_verbose >= 2)
1462 fprintf (sched_dump, "moving to ready without stalls\n");
1464 insn_queue[q_ptr] = 0;
1466 /* If there are no ready insns, stall until one is ready and add all
1467 of the pending insns at that point to the ready list. */
1468 if (ready->n_ready == 0)
1470 register int stalls;
1472 for (stalls = 1; stalls < INSN_QUEUE_SIZE; stalls++)
1474 if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
1476 for (; link; link = XEXP (link, 1))
1478 insn = XEXP (link, 0);
1481 if (sched_verbose >= 2)
1482 fprintf (sched_dump, ";;\t\tQ-->Ready: insn %s: ",
1483 (*current_sched_info->print_insn) (insn, 0));
1485 ready_add (ready, insn);
1486 if (sched_verbose >= 2)
1487 fprintf (sched_dump, "moving to ready with %d stalls\n", stalls);
1489 insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = 0;
1496 if (sched_verbose && stalls)
1497 visualize_stall_cycles (stalls);
1498 q_ptr = NEXT_Q_AFTER (q_ptr, stalls);
1499 clock_var += stalls;
1503 /* Print the ready list for debugging purposes. Callable from debugger. */
1506 debug_ready_list (ready)
1507 struct ready_list *ready;
1512 if (ready->n_ready == 0)
1515 p = ready_lastpos (ready);
1516 for (i = 0; i < ready->n_ready; i++)
1517 fprintf (sched_dump, " %s", (*current_sched_info->print_insn) (p[i], 0));
1518 fprintf (sched_dump, "\n");
1521 /* move_insn1: Remove INSN from insn chain, and link it after LAST insn. */
1524 move_insn1 (insn, last)
1527 NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
1528 PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
1530 NEXT_INSN (insn) = NEXT_INSN (last);
1531 PREV_INSN (NEXT_INSN (last)) = insn;
1533 NEXT_INSN (last) = insn;
1534 PREV_INSN (insn) = last;
1539 /* Search INSN for REG_SAVE_NOTE note pairs for
1540 NOTE_INSN_{LOOP,EHREGION}_{BEG,END}; and convert them back into
1541 NOTEs. The REG_SAVE_NOTE note following first one is contains the
1542 saved value for NOTE_BLOCK_NUMBER which is useful for
1543 NOTE_INSN_EH_REGION_{BEG,END} NOTEs. LAST is the last instruction
1544 output by the instruction scheduler. Return the new value of LAST. */
1547 reemit_notes (insn, last)
1554 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1556 if (REG_NOTE_KIND (note) == REG_SAVE_NOTE)
1558 enum insn_note note_type = INTVAL (XEXP (note, 0));
1560 if (note_type == NOTE_INSN_RANGE_BEG
1561 || note_type == NOTE_INSN_RANGE_END)
1563 last = emit_note_before (note_type, last);
1564 remove_note (insn, note);
1565 note = XEXP (note, 1);
1566 NOTE_RANGE_INFO (last) = XEXP (note, 0);
1570 last = emit_note_before (note_type, last);
1571 remove_note (insn, note);
1572 note = XEXP (note, 1);
1573 if (note_type == NOTE_INSN_EH_REGION_BEG
1574 || note_type == NOTE_INSN_EH_REGION_END)
1575 NOTE_EH_HANDLER (last) = INTVAL (XEXP (note, 0));
1577 remove_note (insn, note);
1583 /* Move INSN, and all insns which should be issued before it,
1584 due to SCHED_GROUP_P flag. Reemit notes if needed.
1586 Return the last insn emitted by the scheduler, which is the
1587 return value from the first call to reemit_notes. */
1590 move_insn (insn, last)
1595 /* If INSN has SCHED_GROUP_P set, then issue it and any other
1596 insns with SCHED_GROUP_P set first. */
1597 while (SCHED_GROUP_P (insn))
1599 rtx prev = PREV_INSN (insn);
1601 /* Move a SCHED_GROUP_P insn. */
1602 move_insn1 (insn, last);
1603 /* If this is the first call to reemit_notes, then record
1604 its return value. */
1605 if (retval == NULL_RTX)
1606 retval = reemit_notes (insn, insn);
1608 reemit_notes (insn, insn);
1612 /* Now move the first non SCHED_GROUP_P insn. */
1613 move_insn1 (insn, last);
1615 /* If this is the first call to reemit_notes, then record
1616 its return value. */
1617 if (retval == NULL_RTX)
1618 retval = reemit_notes (insn, insn);
1620 reemit_notes (insn, insn);
1625 /* Use forward list scheduling to rearrange insns of block B in region RGN,
1626 possibly bringing insns from subsequent blocks in the same region. */
1629 schedule_block (b, rgn_n_insns)
1634 struct ready_list ready;
1637 /* Head/tail info for this block. */
1638 rtx prev_head = current_sched_info->prev_head;
1639 rtx next_tail = current_sched_info->next_tail;
1640 rtx head = NEXT_INSN (prev_head);
1641 rtx tail = PREV_INSN (next_tail);
1643 /* We used to have code to avoid getting parameters moved from hard
1644 argument registers into pseudos.
1646 However, it was removed when it proved to be of marginal benefit
1647 and caused problems because schedule_block and compute_forward_dependences
1648 had different notions of what the "head" insn was. */
1650 if (head == tail && (! INSN_P (head)))
1656 fprintf (sched_dump, ";; ======================================================\n");
1657 fprintf (sched_dump,
1658 ";; -- basic block %d from %d to %d -- %s reload\n",
1659 b, INSN_UID (head), INSN_UID (tail),
1660 (reload_completed ? "after" : "before"));
1661 fprintf (sched_dump, ";; ======================================================\n");
1662 fprintf (sched_dump, "\n");
1665 init_block_visualization ();
1670 /* Allocate the ready list. */
1671 ready.veclen = rgn_n_insns + 1 + ISSUE_RATE;
1672 ready.first = ready.veclen - 1;
1673 ready.vec = (rtx *) xmalloc (ready.veclen * sizeof (rtx));
1676 (*current_sched_info->init_ready_list) (&ready);
1678 #ifdef MD_SCHED_INIT
1679 MD_SCHED_INIT (sched_dump, sched_verbose, ready.veclen);
1682 /* No insns scheduled in this block yet. */
1683 last_scheduled_insn = 0;
1685 /* Initialize INSN_QUEUE. Q_SIZE is the total number of insns in the
1690 memset ((char *) insn_queue, 0, sizeof (insn_queue));
1692 /* Start just before the beginning of time. */
1695 /* We start inserting insns after PREV_HEAD. */
1698 /* Loop until all the insns in BB are scheduled. */
1699 while ((*current_sched_info->schedule_more_p) ())
1703 /* Add to the ready list all pending insns that can be issued now.
1704 If there are no ready insns, increment clock until one
1705 is ready and add all pending insns at that point to the ready
1707 queue_to_ready (&ready);
1709 #ifdef HAVE_cycle_display
1710 if (HAVE_cycle_display)
1711 last = emit_insn_after (gen_cycle_display (GEN_INT (clock_var)), last);
1714 if (ready.n_ready == 0)
1717 if (sched_verbose >= 2)
1719 fprintf (sched_dump, ";;\t\tReady list after queue_to_ready: ");
1720 debug_ready_list (&ready);
1723 /* Sort the ready list based on priority. */
1724 ready_sort (&ready);
1726 /* Allow the target to reorder the list, typically for
1727 better instruction bundling. */
1728 #ifdef MD_SCHED_REORDER
1729 MD_SCHED_REORDER (sched_dump, sched_verbose, ready_lastpos (&ready),
1730 ready.n_ready, clock_var, can_issue_more);
1732 can_issue_more = issue_rate;
1737 fprintf (sched_dump, "\n;;\tReady list (t =%3d): ", clock_var);
1738 debug_ready_list (&ready);
1741 /* Issue insns from ready list. */
1742 while (ready.n_ready != 0
1744 && (*current_sched_info->schedule_more_p) ())
1746 /* Select and remove the insn from the ready list. */
1747 rtx insn = ready_remove_first (&ready);
1748 int cost = actual_hazard (insn_unit (insn), insn, clock_var, 0);
1752 queue_insn (insn, cost);
1756 if (! (*current_sched_info->can_schedule_ready_p) (insn))
1759 last_scheduled_insn = insn;
1760 last = move_insn (insn, last);
1762 #ifdef MD_SCHED_VARIABLE_ISSUE
1763 MD_SCHED_VARIABLE_ISSUE (sched_dump, sched_verbose, insn,
1769 schedule_insn (insn, &ready, clock_var);
1773 #ifdef MD_SCHED_REORDER2
1774 /* Sort the ready list based on priority. */
1775 if (ready.n_ready > 0)
1776 ready_sort (&ready);
1777 MD_SCHED_REORDER2 (sched_dump, sched_verbose,
1778 ready.n_ready ? ready_lastpos (&ready) : NULL,
1779 ready.n_ready, clock_var, can_issue_more);
1785 visualize_scheduled_insns (clock_var);
1788 #ifdef MD_SCHED_FINISH
1789 MD_SCHED_FINISH (sched_dump, sched_verbose);
1795 fprintf (sched_dump, ";;\tReady list (final): ");
1796 debug_ready_list (&ready);
1797 print_block_visualization ("");
1800 /* Sanity check -- queue must be empty now. Meaningless if region has
1802 if (current_sched_info->queue_must_finish_empty && q_size != 0)
1805 /* Update head/tail boundaries. */
1806 head = NEXT_INSN (prev_head);
1809 /* Restore-other-notes: NOTE_LIST is the end of a chain of notes
1810 previously found among the insns. Insert them at the beginning
1814 rtx note_head = note_list;
1816 while (PREV_INSN (note_head))
1818 note_head = PREV_INSN (note_head);
1821 PREV_INSN (note_head) = PREV_INSN (head);
1822 NEXT_INSN (PREV_INSN (head)) = note_head;
1823 PREV_INSN (head) = note_list;
1824 NEXT_INSN (note_list) = head;
1831 fprintf (sched_dump, ";; total time = %d\n;; new head = %d\n",
1832 clock_var, INSN_UID (head));
1833 fprintf (sched_dump, ";; new tail = %d\n\n",
1838 current_sched_info->head = head;
1839 current_sched_info->tail = tail;
1844 /* Set_priorities: compute priority of each insn in the block. */
1847 set_priorities (head, tail)
1855 prev_head = PREV_INSN (head);
1857 if (head == tail && (! INSN_P (head)))
1861 for (insn = tail; insn != prev_head; insn = PREV_INSN (insn))
1863 if (GET_CODE (insn) == NOTE)
1866 if (!(SCHED_GROUP_P (insn)))
1868 (void) priority (insn);
1874 /* Initialize some global state for the scheduler. DUMP_FILE is to be used
1875 for debugging output. */
1878 sched_init (dump_file)
1884 /* Disable speculative loads in their presence if cc0 defined. */
1886 flag_schedule_speculative_load = 0;
1889 /* Set dump and sched_verbose for the desired debugging output. If no
1890 dump-file was specified, but -fsched-verbose=N (any N), print to stderr.
1891 For -fsched-verbose=N, N>=10, print everything to stderr. */
1892 sched_verbose = sched_verbose_param;
1893 if (sched_verbose_param == 0 && dump_file)
1895 sched_dump = ((sched_verbose_param >= 10 || !dump_file)
1896 ? stderr : dump_file);
1898 /* Initialize issue_rate. */
1899 issue_rate = ISSUE_RATE;
1901 /* We use LUID 0 for the fake insn (UID 0) which holds dependencies for
1902 pseudos which do not cross calls. */
1903 old_max_uid = get_max_uid () + 1;
1905 h_i_d = (struct haifa_insn_data *) xcalloc (old_max_uid, sizeof (*h_i_d));
1909 for (b = 0; b < n_basic_blocks; b++)
1910 for (insn = BLOCK_HEAD (b);; insn = NEXT_INSN (insn))
1912 INSN_LUID (insn) = luid;
1914 /* Increment the next luid, unless this is a note. We don't
1915 really need separate IDs for notes and we don't want to
1916 schedule differently depending on whether or not there are
1917 line-number notes, i.e., depending on whether or not we're
1918 generating debugging information. */
1919 if (GET_CODE (insn) != NOTE)
1922 if (insn == BLOCK_END (b))
1926 init_dependency_caches (luid);
1928 compute_bb_for_insn (old_max_uid);
1930 init_alias_analysis ();
1932 if (write_symbols != NO_DEBUG)
1936 line_note_head = (rtx *) xcalloc (n_basic_blocks, sizeof (rtx));
1938 /* Save-line-note-head:
1939 Determine the line-number at the start of each basic block.
1940 This must be computed and saved now, because after a basic block's
1941 predecessor has been scheduled, it is impossible to accurately
1942 determine the correct line number for the first insn of the block. */
1944 for (b = 0; b < n_basic_blocks; b++)
1946 for (line = BLOCK_HEAD (b); line; line = PREV_INSN (line))
1947 if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
1949 line_note_head[b] = line;
1952 /* Do a forward search as well, since we won't get to see the first
1953 notes in a basic block. */
1954 for (line = BLOCK_HEAD (b); line; line = NEXT_INSN (line))
1958 if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
1959 line_note_head[b] = line;
1964 /* Find units used in this fuction, for visualization. */
1966 init_target_units ();
1968 /* ??? Add a NOTE after the last insn of the last basic block. It is not
1969 known why this is done. */
1971 insn = BLOCK_END (n_basic_blocks - 1);
1972 if (NEXT_INSN (insn) == 0
1973 || (GET_CODE (insn) != NOTE
1974 && GET_CODE (insn) != CODE_LABEL
1975 /* Don't emit a NOTE if it would end up before a BARRIER. */
1976 && GET_CODE (NEXT_INSN (insn)) != BARRIER))
1977 emit_note_after (NOTE_INSN_DELETED, BLOCK_END (n_basic_blocks - 1));
1979 /* Compute INSN_REG_WEIGHT for all blocks. We must do this before
1980 removing death notes. */
1981 for (b = n_basic_blocks - 1; b >= 0; b--)
1982 find_insn_reg_weight (b);
1985 /* Free global data used during insn scheduling. */
1991 free_dependency_caches ();
1992 end_alias_analysis ();
1993 if (write_symbols != NO_DEBUG)
1994 free (line_note_head);
1996 #endif /* INSN_SCHEDULING */