1 /* Instruction scheduling pass.
2 Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000, 2001, 2002 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, 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. */
137 #include "coretypes.h"
142 #include "hard-reg-set.h"
143 #include "basic-block.h"
145 #include "function.h"
147 #include "insn-config.h"
148 #include "insn-attr.h"
152 #include "sched-int.h"
155 #ifdef INSN_SCHEDULING
157 /* issue_rate is the number of insns that can be scheduled in the same
158 machine cycle. It can be defined in the config/mach/mach.h file,
159 otherwise we set it to 1. */
161 static int issue_rate;
163 /* If the following variable value is nonzero, the scheduler inserts
164 bubbles (nop insns). The value of variable affects on scheduler
165 behavior only if automaton pipeline interface with multipass
166 scheduling is used and hook dfa_bubble is defined. */
167 int insert_schedule_bubbles_p = 0;
169 /* sched-verbose controls the amount of debugging output the
170 scheduler prints. It is controlled by -fsched-verbose=N:
171 N>0 and no -DSR : the output is directed to stderr.
172 N>=10 will direct the printouts to stderr (regardless of -dSR).
174 N=2: bb's probabilities, detailed ready list info, unit/insn info.
175 N=3: rtl at abort point, control-flow, regions info.
176 N=5: dependences info. */
178 static int sched_verbose_param = 0;
179 int sched_verbose = 0;
181 /* Debugging file. All printouts are sent to dump, which is always set,
182 either to stderr, or to the dump listing file (-dRS). */
183 FILE *sched_dump = 0;
185 /* Highest uid before scheduling. */
186 static int old_max_uid;
188 /* fix_sched_param() is called from toplev.c upon detection
189 of the -fsched-verbose=N option. */
192 fix_sched_param (param, val)
193 const char *param, *val;
195 if (!strcmp (param, "verbose"))
196 sched_verbose_param = atoi (val);
198 warning ("fix_sched_param: unknown param: %s", param);
201 struct haifa_insn_data *h_i_d;
203 #define LINE_NOTE(INSN) (h_i_d[INSN_UID (INSN)].line_note)
204 #define INSN_TICK(INSN) (h_i_d[INSN_UID (INSN)].tick)
206 /* Vector indexed by basic block number giving the starting line-number
207 for each basic block. */
208 static rtx *line_note_head;
210 /* List of important notes we must keep around. This is a pointer to the
211 last element in the list. */
212 static rtx note_list;
216 /* An instruction is ready to be scheduled when all insns preceding it
217 have already been scheduled. It is important to ensure that all
218 insns which use its result will not be executed until its result
219 has been computed. An insn is maintained in one of four structures:
221 (P) the "Pending" set of insns which cannot be scheduled until
222 their dependencies have been satisfied.
223 (Q) the "Queued" set of insns that can be scheduled when sufficient
225 (R) the "Ready" list of unscheduled, uncommitted insns.
226 (S) the "Scheduled" list of insns.
228 Initially, all insns are either "Pending" or "Ready" depending on
229 whether their dependencies are satisfied.
231 Insns move from the "Ready" list to the "Scheduled" list as they
232 are committed to the schedule. As this occurs, the insns in the
233 "Pending" list have their dependencies satisfied and move to either
234 the "Ready" list or the "Queued" set depending on whether
235 sufficient time has passed to make them ready. As time passes,
236 insns move from the "Queued" set to the "Ready" list. Insns may
237 move from the "Ready" list to the "Queued" set if they are blocked
238 due to a function unit conflict.
240 The "Pending" list (P) are the insns in the INSN_DEPEND of the unscheduled
241 insns, i.e., those that are ready, queued, and pending.
242 The "Queued" set (Q) is implemented by the variable `insn_queue'.
243 The "Ready" list (R) is implemented by the variables `ready' and
245 The "Scheduled" list (S) is the new insn chain built by this pass.
247 The transition (R->S) is implemented in the scheduling loop in
248 `schedule_block' when the best insn to schedule is chosen.
249 The transition (R->Q) is implemented in `queue_insn' when an
250 insn is found to have a function unit conflict with the already
252 The transitions (P->R and P->Q) are implemented in `schedule_insn' as
253 insns move from the ready list to the scheduled list.
254 The transition (Q->R) is implemented in 'queue_to_insn' as time
255 passes or stalls are introduced. */
257 /* Implement a circular buffer to delay instructions until sufficient
258 time has passed. For the old pipeline description interface,
259 INSN_QUEUE_SIZE is a power of two larger than MAX_BLOCKAGE and
260 MAX_READY_COST computed by genattr.c. For the new pipeline
261 description interface, MAX_INSN_QUEUE_INDEX is a power of two minus
262 one which is larger than maximal time of instruction execution
263 computed by genattr.c on the base maximal time of functional unit
264 reservations and geting a result. This is the longest time an
265 insn may be queued. */
267 #define MAX_INSN_QUEUE_INDEX max_insn_queue_index_macro_value
269 static rtx *insn_queue;
270 static int q_ptr = 0;
271 static int q_size = 0;
272 #define NEXT_Q(X) (((X)+1) & MAX_INSN_QUEUE_INDEX)
273 #define NEXT_Q_AFTER(X, C) (((X)+C) & MAX_INSN_QUEUE_INDEX)
275 /* The following variable defines value for macro
276 MAX_INSN_QUEUE_INDEX. */
277 static int max_insn_queue_index_macro_value;
279 /* The following variable value refers for all current and future
280 reservations of the processor units. */
283 /* The following variable value is size of memory representing all
284 current and future reservations of the processor units. It is used
285 only by DFA based scheduler. */
286 static size_t dfa_state_size;
288 /* The following array is used to find the best insn from ready when
289 the automaton pipeline interface is used. */
290 static char *ready_try;
292 /* Describe the ready list of the scheduler.
293 VEC holds space enough for all insns in the current region. VECLEN
294 says how many exactly.
295 FIRST is the index of the element with the highest priority; i.e. the
296 last one in the ready list, since elements are ordered by ascending
298 N_READY determines how many insns are on the ready list. */
308 /* Forward declarations. */
310 /* The scheduler using only DFA description should never use the
311 following five functions: */
312 static unsigned int blockage_range PARAMS ((int, rtx));
313 static void clear_units PARAMS ((void));
314 static void schedule_unit PARAMS ((int, rtx, int));
315 static int actual_hazard PARAMS ((int, rtx, int, int));
316 static int potential_hazard PARAMS ((int, rtx, int));
318 static int priority PARAMS ((rtx));
319 static int rank_for_schedule PARAMS ((const PTR, const PTR));
320 static void swap_sort PARAMS ((rtx *, int));
321 static void queue_insn PARAMS ((rtx, int));
322 static void schedule_insn PARAMS ((rtx, struct ready_list *, int));
323 static void find_insn_reg_weight PARAMS ((int));
324 static void adjust_priority PARAMS ((rtx));
325 static void advance_one_cycle PARAMS ((void));
327 /* Notes handling mechanism:
328 =========================
329 Generally, NOTES are saved before scheduling and restored after scheduling.
330 The scheduler distinguishes between three types of notes:
332 (1) LINE_NUMBER notes, generated and used for debugging. Here,
333 before scheduling a region, a pointer to the LINE_NUMBER note is
334 added to the insn following it (in save_line_notes()), and the note
335 is removed (in rm_line_notes() and unlink_line_notes()). After
336 scheduling the region, this pointer is used for regeneration of
337 the LINE_NUMBER note (in restore_line_notes()).
339 (2) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes:
340 Before scheduling a region, a pointer to the note is added to the insn
341 that follows or precedes it. (This happens as part of the data dependence
342 computation). After scheduling an insn, the pointer contained in it is
343 used for regenerating the corresponding note (in reemit_notes).
345 (3) All other notes (e.g. INSN_DELETED): Before scheduling a block,
346 these notes are put in a list (in rm_other_notes() and
347 unlink_other_notes ()). After scheduling the block, these notes are
348 inserted at the beginning of the block (in schedule_block()). */
350 static rtx unlink_other_notes PARAMS ((rtx, rtx));
351 static rtx unlink_line_notes PARAMS ((rtx, rtx));
352 static rtx reemit_notes PARAMS ((rtx, rtx));
354 static rtx *ready_lastpos PARAMS ((struct ready_list *));
355 static void ready_sort PARAMS ((struct ready_list *));
356 static rtx ready_remove_first PARAMS ((struct ready_list *));
358 static void queue_to_ready PARAMS ((struct ready_list *));
360 static void debug_ready_list PARAMS ((struct ready_list *));
362 static rtx move_insn1 PARAMS ((rtx, rtx));
363 static rtx move_insn PARAMS ((rtx, rtx));
365 /* The following functions are used to implement multi-pass scheduling
366 on the first cycle. It is used only for DFA based scheduler. */
367 static rtx ready_element PARAMS ((struct ready_list *, int));
368 static rtx ready_remove PARAMS ((struct ready_list *, int));
369 static int max_issue PARAMS ((struct ready_list *, state_t, int *));
371 static rtx choose_ready PARAMS ((struct ready_list *));
373 #endif /* INSN_SCHEDULING */
375 /* Point to state used for the current scheduling pass. */
376 struct sched_info *current_sched_info;
378 #ifndef INSN_SCHEDULING
380 schedule_insns (dump_file)
381 FILE *dump_file ATTRIBUTE_UNUSED;
386 /* Pointer to the last instruction scheduled. Used by rank_for_schedule,
387 so that insns independent of the last scheduled insn will be preferred
388 over dependent instructions. */
390 static rtx last_scheduled_insn;
392 /* Compute the function units used by INSN. This caches the value
393 returned by function_units_used. A function unit is encoded as the
394 unit number if the value is non-negative and the complement of a
395 mask if the value is negative. A function unit index is the
396 non-negative encoding. The scheduler using only DFA description
397 should never use the following function. */
403 int unit = INSN_UNIT (insn);
407 recog_memoized (insn);
409 /* A USE insn, or something else we don't need to understand.
410 We can't pass these directly to function_units_used because it will
411 trigger a fatal error for unrecognizable insns. */
412 if (INSN_CODE (insn) < 0)
416 unit = function_units_used (insn);
417 /* Increment non-negative values so we can cache zero. */
421 /* We only cache 16 bits of the result, so if the value is out of
422 range, don't cache it. */
423 if (FUNCTION_UNITS_SIZE < HOST_BITS_PER_SHORT
425 || (unit & ~((1 << (HOST_BITS_PER_SHORT - 1)) - 1)) == 0)
426 INSN_UNIT (insn) = unit;
428 return (unit > 0 ? unit - 1 : unit);
431 /* Compute the blockage range for executing INSN on UNIT. This caches
432 the value returned by the blockage_range_function for the unit.
433 These values are encoded in an int where the upper half gives the
434 minimum value and the lower half gives the maximum value. The
435 scheduler using only DFA description should never use the following
438 HAIFA_INLINE static unsigned int
439 blockage_range (unit, insn)
443 unsigned int blockage = INSN_BLOCKAGE (insn);
446 if ((int) UNIT_BLOCKED (blockage) != unit + 1)
448 range = function_units[unit].blockage_range_function (insn);
449 /* We only cache the blockage range for one unit and then only if
451 if (HOST_BITS_PER_INT >= UNIT_BITS + 2 * BLOCKAGE_BITS)
452 INSN_BLOCKAGE (insn) = ENCODE_BLOCKAGE (unit + 1, range);
455 range = BLOCKAGE_RANGE (blockage);
460 /* A vector indexed by function unit instance giving the last insn to
461 use the unit. The value of the function unit instance index for
462 unit U instance I is (U + I * FUNCTION_UNITS_SIZE). The scheduler
463 using only DFA description should never use the following variable. */
464 #if FUNCTION_UNITS_SIZE
465 static rtx unit_last_insn[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY];
467 static rtx unit_last_insn[1];
470 /* A vector indexed by function unit instance giving the minimum time
471 when the unit will unblock based on the maximum blockage cost. The
472 scheduler using only DFA description should never use the following
474 #if FUNCTION_UNITS_SIZE
475 static int unit_tick[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY];
477 static int unit_tick[1];
480 /* A vector indexed by function unit number giving the number of insns
481 that remain to use the unit. The scheduler using only DFA
482 description should never use the following variable. */
483 #if FUNCTION_UNITS_SIZE
484 static int unit_n_insns[FUNCTION_UNITS_SIZE];
486 static int unit_n_insns[1];
489 /* Access the unit_last_insn array. Used by the visualization code.
490 The scheduler using only DFA description should never use the
491 following function. */
494 get_unit_last_insn (instance)
497 return unit_last_insn[instance];
500 /* Reset the function unit state to the null state. */
505 memset ((char *) unit_last_insn, 0, sizeof (unit_last_insn));
506 memset ((char *) unit_tick, 0, sizeof (unit_tick));
507 memset ((char *) unit_n_insns, 0, sizeof (unit_n_insns));
510 /* Return the issue-delay of an insn. The scheduler using only DFA
511 description should never use the following function. */
514 insn_issue_delay (insn)
518 int unit = insn_unit (insn);
520 /* Efficiency note: in fact, we are working 'hard' to compute a
521 value that was available in md file, and is not available in
522 function_units[] structure. It would be nice to have this
526 if (function_units[unit].blockage_range_function &&
527 function_units[unit].blockage_function)
528 delay = function_units[unit].blockage_function (insn, insn);
531 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
532 if ((unit & 1) != 0 && function_units[i].blockage_range_function
533 && function_units[i].blockage_function)
534 delay = MAX (delay, function_units[i].blockage_function (insn, insn));
539 /* Return the actual hazard cost of executing INSN on the unit UNIT,
540 instance INSTANCE at time CLOCK if the previous actual hazard cost
541 was COST. The scheduler using only DFA description should never
542 use the following function. */
545 actual_hazard_this_instance (unit, instance, insn, clock, cost)
546 int unit, instance, clock, cost;
549 int tick = unit_tick[instance]; /* Issue time of the last issued insn. */
551 if (tick - clock > cost)
553 /* The scheduler is operating forward, so unit's last insn is the
554 executing insn and INSN is the candidate insn. We want a
555 more exact measure of the blockage if we execute INSN at CLOCK
556 given when we committed the execution of the unit's last insn.
558 The blockage value is given by either the unit's max blockage
559 constant, blockage range function, or blockage function. Use
560 the most exact form for the given unit. */
562 if (function_units[unit].blockage_range_function)
564 if (function_units[unit].blockage_function)
565 tick += (function_units[unit].blockage_function
566 (unit_last_insn[instance], insn)
567 - function_units[unit].max_blockage);
569 tick += ((int) MAX_BLOCKAGE_COST (blockage_range (unit, insn))
570 - function_units[unit].max_blockage);
572 if (tick - clock > cost)
578 /* Record INSN as having begun execution on the units encoded by UNIT
579 at time CLOCK. The scheduler using only DFA description should
580 never use the following function. */
582 HAIFA_INLINE static void
583 schedule_unit (unit, insn, clock)
592 #if MAX_MULTIPLICITY > 1
593 /* Find the first free instance of the function unit and use that
594 one. We assume that one is free. */
595 for (i = function_units[unit].multiplicity - 1; i > 0; i--)
597 if (!actual_hazard_this_instance (unit, instance, insn, clock, 0))
599 instance += FUNCTION_UNITS_SIZE;
602 unit_last_insn[instance] = insn;
603 unit_tick[instance] = (clock + function_units[unit].max_blockage);
606 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
608 schedule_unit (i, insn, clock);
611 /* Return the actual hazard cost of executing INSN on the units
612 encoded by UNIT at time CLOCK if the previous actual hazard cost
613 was COST. The scheduler using only DFA description should never
614 use the following function. */
616 HAIFA_INLINE static int
617 actual_hazard (unit, insn, clock, cost)
618 int unit, clock, cost;
625 /* Find the instance of the function unit with the minimum hazard. */
627 int best_cost = actual_hazard_this_instance (unit, instance, insn,
629 #if MAX_MULTIPLICITY > 1
632 if (best_cost > cost)
634 for (i = function_units[unit].multiplicity - 1; i > 0; i--)
636 instance += FUNCTION_UNITS_SIZE;
637 this_cost = actual_hazard_this_instance (unit, instance, insn,
639 if (this_cost < best_cost)
641 best_cost = this_cost;
642 if (this_cost <= cost)
648 cost = MAX (cost, best_cost);
651 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
653 cost = actual_hazard (i, insn, clock, cost);
658 /* Return the potential hazard cost of executing an instruction on the
659 units encoded by UNIT if the previous potential hazard cost was
660 COST. An insn with a large blockage time is chosen in preference
661 to one with a smaller time; an insn that uses a unit that is more
662 likely to be used is chosen in preference to one with a unit that
663 is less used. We are trying to minimize a subsequent actual
664 hazard. The scheduler using only DFA description should never use
665 the following function. */
667 HAIFA_INLINE static int
668 potential_hazard (unit, insn, cost)
673 unsigned int minb, maxb;
677 minb = maxb = function_units[unit].max_blockage;
680 if (function_units[unit].blockage_range_function)
682 maxb = minb = blockage_range (unit, insn);
683 maxb = MAX_BLOCKAGE_COST (maxb);
684 minb = MIN_BLOCKAGE_COST (minb);
689 /* Make the number of instructions left dominate. Make the
690 minimum delay dominate the maximum delay. If all these
691 are the same, use the unit number to add an arbitrary
692 ordering. Other terms can be added. */
693 ncost = minb * 0x40 + maxb;
694 ncost *= (unit_n_insns[unit] - 1) * 0x1000 + unit;
701 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
703 cost = potential_hazard (i, insn, cost);
708 /* Compute cost of executing INSN given the dependence LINK on the insn USED.
709 This is the number of cycles between instruction issue and
710 instruction results. */
713 insn_cost (insn, link, used)
714 rtx insn, link, used;
716 int cost = INSN_COST (insn);
720 /* A USE insn, or something else we don't need to
721 understand. We can't pass these directly to
722 result_ready_cost or insn_default_latency because it will
723 trigger a fatal error for unrecognizable insns. */
724 if (recog_memoized (insn) < 0)
726 INSN_COST (insn) = 0;
731 if (targetm.sched.use_dfa_pipeline_interface
732 && (*targetm.sched.use_dfa_pipeline_interface) ())
733 cost = insn_default_latency (insn);
735 cost = result_ready_cost (insn);
740 INSN_COST (insn) = cost;
744 /* In this case estimate cost without caring how insn is used. */
745 if (link == 0 || used == 0)
748 /* A USE insn should never require the value used to be computed.
749 This allows the computation of a function's result and parameter
750 values to overlap the return and call. */
751 if (recog_memoized (used) < 0)
755 if (targetm.sched.use_dfa_pipeline_interface
756 && (*targetm.sched.use_dfa_pipeline_interface) ())
758 if (INSN_CODE (insn) >= 0)
760 if (REG_NOTE_KIND (link) == REG_DEP_ANTI)
762 else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT)
764 cost = (insn_default_latency (insn)
765 - insn_default_latency (used));
769 else if (bypass_p (insn))
770 cost = insn_latency (insn, used);
774 if (targetm.sched.adjust_cost)
775 cost = (*targetm.sched.adjust_cost) (used, link, insn, cost);
784 /* Compute the priority number for INSN. */
795 if (! INSN_PRIORITY_KNOWN (insn))
797 int this_priority = 0;
799 if (INSN_DEPEND (insn) == 0)
800 this_priority = insn_cost (insn, 0, 0);
803 for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
808 if (RTX_INTEGRATED_P (link))
811 next = XEXP (link, 0);
813 /* Critical path is meaningful in block boundaries only. */
814 if (! (*current_sched_info->contributes_to_priority) (next, insn))
817 next_priority = insn_cost (insn, link, next) + priority (next);
818 if (next_priority > this_priority)
819 this_priority = next_priority;
822 INSN_PRIORITY (insn) = this_priority;
823 INSN_PRIORITY_KNOWN (insn) = 1;
826 return INSN_PRIORITY (insn);
829 /* Macros and functions for keeping the priority queue sorted, and
830 dealing with queueing and dequeueing of instructions. */
832 #define SCHED_SORT(READY, N_READY) \
833 do { if ((N_READY) == 2) \
834 swap_sort (READY, N_READY); \
835 else if ((N_READY) > 2) \
836 qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \
839 /* Returns a positive value if x is preferred; returns a negative value if
840 y is preferred. Should never return 0, since that will make the sort
844 rank_for_schedule (x, y)
848 rtx tmp = *(const rtx *) y;
849 rtx tmp2 = *(const rtx *) x;
851 int tmp_class, tmp2_class, depend_count1, depend_count2;
852 int val, priority_val, weight_val, info_val;
854 /* Prefer insn with higher priority. */
855 priority_val = INSN_PRIORITY (tmp2) - INSN_PRIORITY (tmp);
859 /* Prefer an insn with smaller contribution to registers-pressure. */
860 if (!reload_completed &&
861 (weight_val = INSN_REG_WEIGHT (tmp) - INSN_REG_WEIGHT (tmp2)))
864 info_val = (*current_sched_info->rank) (tmp, tmp2);
868 /* Compare insns based on their relation to the last-scheduled-insn. */
869 if (last_scheduled_insn)
871 /* Classify the instructions into three classes:
872 1) Data dependent on last schedule insn.
873 2) Anti/Output dependent on last scheduled insn.
874 3) Independent of last scheduled insn, or has latency of one.
875 Choose the insn from the highest numbered class if different. */
876 link = find_insn_list (tmp, INSN_DEPEND (last_scheduled_insn));
877 if (link == 0 || insn_cost (last_scheduled_insn, link, tmp) == 1)
879 else if (REG_NOTE_KIND (link) == 0) /* Data dependence. */
884 link = find_insn_list (tmp2, INSN_DEPEND (last_scheduled_insn));
885 if (link == 0 || insn_cost (last_scheduled_insn, link, tmp2) == 1)
887 else if (REG_NOTE_KIND (link) == 0) /* Data dependence. */
892 if ((val = tmp2_class - tmp_class))
896 /* Prefer the insn which has more later insns that depend on it.
897 This gives the scheduler more freedom when scheduling later
898 instructions at the expense of added register pressure. */
900 for (link = INSN_DEPEND (tmp); link; link = XEXP (link, 1))
904 for (link = INSN_DEPEND (tmp2); link; link = XEXP (link, 1))
907 val = depend_count2 - depend_count1;
911 /* If insns are equally good, sort by INSN_LUID (original insn order),
912 so that we make the sort stable. This minimizes instruction movement,
913 thus minimizing sched's effect on debugging and cross-jumping. */
914 return INSN_LUID (tmp) - INSN_LUID (tmp2);
917 /* Resort the array A in which only element at index N may be out of order. */
919 HAIFA_INLINE static void
927 while (i >= 0 && rank_for_schedule (a + i, &insn) >= 0)
935 /* Add INSN to the insn queue so that it can be executed at least
936 N_CYCLES after the currently executing insn. Preserve insns
937 chain for debugging purposes. */
939 HAIFA_INLINE static void
940 queue_insn (insn, n_cycles)
944 int next_q = NEXT_Q_AFTER (q_ptr, n_cycles);
945 rtx link = alloc_INSN_LIST (insn, insn_queue[next_q]);
946 insn_queue[next_q] = link;
949 if (sched_verbose >= 2)
951 fprintf (sched_dump, ";;\t\tReady-->Q: insn %s: ",
952 (*current_sched_info->print_insn) (insn, 0));
954 fprintf (sched_dump, "queued for %d cycles.\n", n_cycles);
958 /* Return a pointer to the bottom of the ready list, i.e. the insn
959 with the lowest priority. */
961 HAIFA_INLINE static rtx *
962 ready_lastpos (ready)
963 struct ready_list *ready;
965 if (ready->n_ready == 0)
967 return ready->vec + ready->first - ready->n_ready + 1;
970 /* Add an element INSN to the ready list so that it ends up with the lowest
974 ready_add (ready, insn)
975 struct ready_list *ready;
978 if (ready->first == ready->n_ready)
980 memmove (ready->vec + ready->veclen - ready->n_ready,
981 ready_lastpos (ready),
982 ready->n_ready * sizeof (rtx));
983 ready->first = ready->veclen - 1;
985 ready->vec[ready->first - ready->n_ready] = insn;
989 /* Remove the element with the highest priority from the ready list and
992 HAIFA_INLINE static rtx
993 ready_remove_first (ready)
994 struct ready_list *ready;
997 if (ready->n_ready == 0)
999 t = ready->vec[ready->first--];
1001 /* If the queue becomes empty, reset it. */
1002 if (ready->n_ready == 0)
1003 ready->first = ready->veclen - 1;
1007 /* The following code implements multi-pass scheduling for the first
1008 cycle. In other words, we will try to choose ready insn which
1009 permits to start maximum number of insns on the same cycle. */
1011 /* Return a pointer to the element INDEX from the ready. INDEX for
1012 insn with the highest priority is 0, and the lowest priority has
1015 HAIFA_INLINE static rtx
1016 ready_element (ready, index)
1017 struct ready_list *ready;
1020 if (ready->n_ready == 0 || index >= ready->n_ready)
1022 return ready->vec[ready->first - index];
1025 /* Remove the element INDEX from the ready list and return it. INDEX
1026 for insn with the highest priority is 0, and the lowest priority
1029 HAIFA_INLINE static rtx
1030 ready_remove (ready, index)
1031 struct ready_list *ready;
1038 return ready_remove_first (ready);
1039 if (ready->n_ready == 0 || index >= ready->n_ready)
1041 t = ready->vec[ready->first - index];
1043 for (i = index; i < ready->n_ready; i++)
1044 ready->vec[ready->first - i] = ready->vec[ready->first - i - 1];
1049 /* Sort the ready list READY by ascending priority, using the SCHED_SORT
1052 HAIFA_INLINE static void
1054 struct ready_list *ready;
1056 rtx *first = ready_lastpos (ready);
1057 SCHED_SORT (first, ready->n_ready);
1060 /* PREV is an insn that is ready to execute. Adjust its priority if that
1061 will help shorten or lengthen register lifetimes as appropriate. Also
1062 provide a hook for the target to tweek itself. */
1064 HAIFA_INLINE static void
1065 adjust_priority (prev)
1068 /* ??? There used to be code here to try and estimate how an insn
1069 affected register lifetimes, but it did it by looking at REG_DEAD
1070 notes, which we removed in schedule_region. Nor did it try to
1071 take into account register pressure or anything useful like that.
1073 Revisit when we have a machine model to work with and not before. */
1075 if (targetm.sched.adjust_priority)
1076 INSN_PRIORITY (prev) =
1077 (*targetm.sched.adjust_priority) (prev, INSN_PRIORITY (prev));
1080 /* Advance time on one cycle. */
1081 HAIFA_INLINE static void
1082 advance_one_cycle ()
1084 if (targetm.sched.use_dfa_pipeline_interface
1085 && (*targetm.sched.use_dfa_pipeline_interface) ())
1087 if (targetm.sched.dfa_pre_cycle_insn)
1088 state_transition (curr_state,
1089 (*targetm.sched.dfa_pre_cycle_insn) ());
1091 state_transition (curr_state, NULL);
1093 if (targetm.sched.dfa_post_cycle_insn)
1094 state_transition (curr_state,
1095 (*targetm.sched.dfa_post_cycle_insn) ());
1099 /* Clock at which the previous instruction was issued. */
1100 static int last_clock_var;
1102 /* INSN is the "currently executing insn". Launch each insn which was
1103 waiting on INSN. READY is the ready list which contains the insns
1104 that are ready to fire. CLOCK is the current cycle.
1108 schedule_insn (insn, ready, clock)
1110 struct ready_list *ready;
1116 if (!targetm.sched.use_dfa_pipeline_interface
1117 || !(*targetm.sched.use_dfa_pipeline_interface) ())
1118 unit = insn_unit (insn);
1120 if (targetm.sched.use_dfa_pipeline_interface
1121 && (*targetm.sched.use_dfa_pipeline_interface) ()
1122 && sched_verbose >= 1)
1126 print_insn (buf, insn, 0);
1128 fprintf (sched_dump, ";;\t%3i--> %-40s:", clock, buf);
1130 if (recog_memoized (insn) < 0)
1131 fprintf (sched_dump, "nothing");
1133 print_reservation (sched_dump, insn);
1134 fputc ('\n', sched_dump);
1136 else if (sched_verbose >= 2)
1138 fprintf (sched_dump, ";;\t\t--> scheduling insn <<<%d>>> on unit ",
1140 insn_print_units (insn);
1141 fputc ('\n', sched_dump);
1144 if (!targetm.sched.use_dfa_pipeline_interface
1145 || !(*targetm.sched.use_dfa_pipeline_interface) ())
1147 if (sched_verbose && unit == -1)
1148 visualize_no_unit (insn);
1151 if (MAX_BLOCKAGE > 1 || issue_rate > 1 || sched_verbose)
1152 schedule_unit (unit, insn, clock);
1154 if (INSN_DEPEND (insn) == 0)
1158 for (link = INSN_DEPEND (insn); link != 0; link = XEXP (link, 1))
1160 rtx next = XEXP (link, 0);
1161 int cost = insn_cost (insn, link, next);
1163 INSN_TICK (next) = MAX (INSN_TICK (next), clock + cost);
1165 if ((INSN_DEP_COUNT (next) -= 1) == 0)
1167 int effective_cost = INSN_TICK (next) - clock;
1169 if (! (*current_sched_info->new_ready) (next))
1172 if (sched_verbose >= 2)
1174 fprintf (sched_dump, ";;\t\tdependences resolved: insn %s ",
1175 (*current_sched_info->print_insn) (next, 0));
1177 if (effective_cost < 1)
1178 fprintf (sched_dump, "into ready\n");
1180 fprintf (sched_dump, "into queue with cost=%d\n", effective_cost);
1183 /* Adjust the priority of NEXT and either put it on the ready
1184 list or queue it. */
1185 adjust_priority (next);
1186 if (effective_cost < 1)
1187 ready_add (ready, next);
1189 queue_insn (next, effective_cost);
1193 /* Annotate the instruction with issue information -- TImode
1194 indicates that the instruction is expected not to be able
1195 to issue on the same cycle as the previous insn. A machine
1196 may use this information to decide how the instruction should
1198 if (reload_completed && issue_rate > 1
1199 && GET_CODE (PATTERN (insn)) != USE
1200 && GET_CODE (PATTERN (insn)) != CLOBBER)
1202 PUT_MODE (insn, clock > last_clock_var ? TImode : VOIDmode);
1203 last_clock_var = clock;
1207 /* Functions for handling of notes. */
1209 /* Delete notes beginning with INSN and put them in the chain
1210 of notes ended by NOTE_LIST.
1211 Returns the insn following the notes. */
1214 unlink_other_notes (insn, tail)
1217 rtx prev = PREV_INSN (insn);
1219 while (insn != tail && GET_CODE (insn) == NOTE)
1221 rtx next = NEXT_INSN (insn);
1222 /* Delete the note from its current position. */
1224 NEXT_INSN (prev) = next;
1226 PREV_INSN (next) = prev;
1228 /* See sched_analyze to see how these are handled. */
1229 if (NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG
1230 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_END
1231 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_BEG
1232 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_END)
1234 /* Insert the note at the end of the notes list. */
1235 PREV_INSN (insn) = note_list;
1237 NEXT_INSN (note_list) = insn;
1246 /* Delete line notes beginning with INSN. Record line-number notes so
1247 they can be reused. Returns the insn following the notes. */
1250 unlink_line_notes (insn, tail)
1253 rtx prev = PREV_INSN (insn);
1255 while (insn != tail && GET_CODE (insn) == NOTE)
1257 rtx next = NEXT_INSN (insn);
1259 if (write_symbols != NO_DEBUG && NOTE_LINE_NUMBER (insn) > 0)
1261 /* Delete the note from its current position. */
1263 NEXT_INSN (prev) = next;
1265 PREV_INSN (next) = prev;
1267 /* Record line-number notes so they can be reused. */
1268 LINE_NOTE (insn) = insn;
1278 /* Return the head and tail pointers of BB. */
1281 get_block_head_tail (b, headp, tailp)
1286 /* HEAD and TAIL delimit the basic block being scheduled. */
1287 rtx head = BLOCK_HEAD (b);
1288 rtx tail = BLOCK_END (b);
1290 /* Don't include any notes or labels at the beginning of the
1291 basic block, or notes at the ends of basic blocks. */
1292 while (head != tail)
1294 if (GET_CODE (head) == NOTE)
1295 head = NEXT_INSN (head);
1296 else if (GET_CODE (tail) == NOTE)
1297 tail = PREV_INSN (tail);
1298 else if (GET_CODE (head) == CODE_LABEL)
1299 head = NEXT_INSN (head);
1308 /* Return nonzero if there are no real insns in the range [ HEAD, TAIL ]. */
1311 no_real_insns_p (head, tail)
1314 while (head != NEXT_INSN (tail))
1316 if (GET_CODE (head) != NOTE && GET_CODE (head) != CODE_LABEL)
1318 head = NEXT_INSN (head);
1323 /* Delete line notes from one block. Save them so they can be later restored
1324 (in restore_line_notes). HEAD and TAIL are the boundaries of the
1325 block in which notes should be processed. */
1328 rm_line_notes (head, tail)
1334 next_tail = NEXT_INSN (tail);
1335 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
1339 /* Farm out notes, and maybe save them in NOTE_LIST.
1340 This is needed to keep the debugger from
1341 getting completely deranged. */
1342 if (GET_CODE (insn) == NOTE)
1345 insn = unlink_line_notes (insn, next_tail);
1351 if (insn == next_tail)
1357 /* Save line number notes for each insn in block B. HEAD and TAIL are
1358 the boundaries of the block in which notes should be processed. */
1361 save_line_notes (b, head, tail)
1367 /* We must use the true line number for the first insn in the block
1368 that was computed and saved at the start of this pass. We can't
1369 use the current line number, because scheduling of the previous
1370 block may have changed the current line number. */
1372 rtx line = line_note_head[b];
1375 next_tail = NEXT_INSN (tail);
1377 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
1378 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
1381 LINE_NOTE (insn) = line;
1384 /* After a block was scheduled, insert line notes into the insns list.
1385 HEAD and TAIL are the boundaries of the block in which notes should
1389 restore_line_notes (head, tail)
1392 rtx line, note, prev, new;
1393 int added_notes = 0;
1394 rtx next_tail, insn;
1397 next_tail = NEXT_INSN (tail);
1399 /* Determine the current line-number. We want to know the current
1400 line number of the first insn of the block here, in case it is
1401 different from the true line number that was saved earlier. If
1402 different, then we need a line number note before the first insn
1403 of this block. If it happens to be the same, then we don't want to
1404 emit another line number note here. */
1405 for (line = head; line; line = PREV_INSN (line))
1406 if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
1409 /* Walk the insns keeping track of the current line-number and inserting
1410 the line-number notes as needed. */
1411 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
1412 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
1414 /* This used to emit line number notes before every non-deleted note.
1415 However, this confuses a debugger, because line notes not separated
1416 by real instructions all end up at the same address. I can find no
1417 use for line number notes before other notes, so none are emitted. */
1418 else if (GET_CODE (insn) != NOTE
1419 && INSN_UID (insn) < old_max_uid
1420 && (note = LINE_NOTE (insn)) != 0
1423 || NOTE_LINE_NUMBER (note) != NOTE_LINE_NUMBER (line)
1424 || NOTE_SOURCE_FILE (note) != NOTE_SOURCE_FILE (line)))
1427 prev = PREV_INSN (insn);
1428 if (LINE_NOTE (note))
1430 /* Re-use the original line-number note. */
1431 LINE_NOTE (note) = 0;
1432 PREV_INSN (note) = prev;
1433 NEXT_INSN (prev) = note;
1434 PREV_INSN (insn) = note;
1435 NEXT_INSN (note) = insn;
1440 new = emit_note_after (NOTE_LINE_NUMBER (note), prev);
1441 NOTE_SOURCE_FILE (new) = NOTE_SOURCE_FILE (note);
1442 RTX_INTEGRATED_P (new) = RTX_INTEGRATED_P (note);
1445 if (sched_verbose && added_notes)
1446 fprintf (sched_dump, ";; added %d line-number notes\n", added_notes);
1449 /* After scheduling the function, delete redundant line notes from the
1453 rm_redundant_line_notes ()
1456 rtx insn = get_insns ();
1457 int active_insn = 0;
1460 /* Walk the insns deleting redundant line-number notes. Many of these
1461 are already present. The remainder tend to occur at basic
1462 block boundaries. */
1463 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
1464 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
1466 /* If there are no active insns following, INSN is redundant. */
1467 if (active_insn == 0)
1470 NOTE_SOURCE_FILE (insn) = 0;
1471 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
1473 /* If the line number is unchanged, LINE is redundant. */
1475 && NOTE_LINE_NUMBER (line) == NOTE_LINE_NUMBER (insn)
1476 && NOTE_SOURCE_FILE (line) == NOTE_SOURCE_FILE (insn))
1479 NOTE_SOURCE_FILE (line) = 0;
1480 NOTE_LINE_NUMBER (line) = NOTE_INSN_DELETED;
1487 else if (!((GET_CODE (insn) == NOTE
1488 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED)
1489 || (GET_CODE (insn) == INSN
1490 && (GET_CODE (PATTERN (insn)) == USE
1491 || GET_CODE (PATTERN (insn)) == CLOBBER))))
1494 if (sched_verbose && notes)
1495 fprintf (sched_dump, ";; deleted %d line-number notes\n", notes);
1498 /* Delete notes between HEAD and TAIL and put them in the chain
1499 of notes ended by NOTE_LIST. */
1502 rm_other_notes (head, tail)
1510 if (head == tail && (! INSN_P (head)))
1513 next_tail = NEXT_INSN (tail);
1514 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
1518 /* Farm out notes, and maybe save them in NOTE_LIST.
1519 This is needed to keep the debugger from
1520 getting completely deranged. */
1521 if (GET_CODE (insn) == NOTE)
1525 insn = unlink_other_notes (insn, next_tail);
1531 if (insn == next_tail)
1537 /* Functions for computation of registers live/usage info. */
1539 /* Calculate INSN_REG_WEIGHT for all insns of a block. */
1542 find_insn_reg_weight (b)
1545 rtx insn, next_tail, head, tail;
1547 get_block_head_tail (b, &head, &tail);
1548 next_tail = NEXT_INSN (tail);
1550 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
1555 /* Handle register life information. */
1556 if (! INSN_P (insn))
1559 /* Increment weight for each register born here. */
1561 if ((GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
1562 && register_operand (SET_DEST (x), VOIDmode))
1564 else if (GET_CODE (x) == PARALLEL)
1567 for (j = XVECLEN (x, 0) - 1; j >= 0; j--)
1569 x = XVECEXP (PATTERN (insn), 0, j);
1570 if ((GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
1571 && register_operand (SET_DEST (x), VOIDmode))
1576 /* Decrement weight for each register that dies here. */
1577 for (x = REG_NOTES (insn); x; x = XEXP (x, 1))
1579 if (REG_NOTE_KIND (x) == REG_DEAD
1580 || REG_NOTE_KIND (x) == REG_UNUSED)
1584 INSN_REG_WEIGHT (insn) = reg_weight;
1588 /* Scheduling clock, modified in schedule_block() and queue_to_ready (). */
1589 static int clock_var;
1591 /* Move insns that became ready to fire from queue to ready list. */
1594 queue_to_ready (ready)
1595 struct ready_list *ready;
1600 q_ptr = NEXT_Q (q_ptr);
1602 /* Add all pending insns that can be scheduled without stalls to the
1604 for (link = insn_queue[q_ptr]; link; link = XEXP (link, 1))
1606 insn = XEXP (link, 0);
1609 if (sched_verbose >= 2)
1610 fprintf (sched_dump, ";;\t\tQ-->Ready: insn %s: ",
1611 (*current_sched_info->print_insn) (insn, 0));
1613 ready_add (ready, insn);
1614 if (sched_verbose >= 2)
1615 fprintf (sched_dump, "moving to ready without stalls\n");
1617 insn_queue[q_ptr] = 0;
1619 /* If there are no ready insns, stall until one is ready and add all
1620 of the pending insns at that point to the ready list. */
1621 if (ready->n_ready == 0)
1625 for (stalls = 1; stalls <= MAX_INSN_QUEUE_INDEX; stalls++)
1627 if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
1629 for (; link; link = XEXP (link, 1))
1631 insn = XEXP (link, 0);
1634 if (sched_verbose >= 2)
1635 fprintf (sched_dump, ";;\t\tQ-->Ready: insn %s: ",
1636 (*current_sched_info->print_insn) (insn, 0));
1638 ready_add (ready, insn);
1639 if (sched_verbose >= 2)
1640 fprintf (sched_dump, "moving to ready with %d stalls\n", stalls);
1642 insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = 0;
1644 advance_one_cycle ();
1649 advance_one_cycle ();
1652 if ((!targetm.sched.use_dfa_pipeline_interface
1653 || !(*targetm.sched.use_dfa_pipeline_interface) ())
1654 && sched_verbose && stalls)
1655 visualize_stall_cycles (stalls);
1657 q_ptr = NEXT_Q_AFTER (q_ptr, stalls);
1658 clock_var += stalls;
1662 /* Print the ready list for debugging purposes. Callable from debugger. */
1665 debug_ready_list (ready)
1666 struct ready_list *ready;
1671 if (ready->n_ready == 0)
1673 fprintf (sched_dump, "\n");
1677 p = ready_lastpos (ready);
1678 for (i = 0; i < ready->n_ready; i++)
1679 fprintf (sched_dump, " %s", (*current_sched_info->print_insn) (p[i], 0));
1680 fprintf (sched_dump, "\n");
1683 /* move_insn1: Remove INSN from insn chain, and link it after LAST insn. */
1686 move_insn1 (insn, last)
1689 NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
1690 PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
1692 NEXT_INSN (insn) = NEXT_INSN (last);
1693 PREV_INSN (NEXT_INSN (last)) = insn;
1695 NEXT_INSN (last) = insn;
1696 PREV_INSN (insn) = last;
1701 /* Search INSN for REG_SAVE_NOTE note pairs for
1702 NOTE_INSN_{LOOP,EHREGION}_{BEG,END}; and convert them back into
1703 NOTEs. The REG_SAVE_NOTE note following first one is contains the
1704 saved value for NOTE_BLOCK_NUMBER which is useful for
1705 NOTE_INSN_EH_REGION_{BEG,END} NOTEs. LAST is the last instruction
1706 output by the instruction scheduler. Return the new value of LAST. */
1709 reemit_notes (insn, last)
1716 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1718 if (REG_NOTE_KIND (note) == REG_SAVE_NOTE)
1720 enum insn_note note_type = INTVAL (XEXP (note, 0));
1722 last = emit_note_before (note_type, last);
1723 remove_note (insn, note);
1724 note = XEXP (note, 1);
1725 if (note_type == NOTE_INSN_EH_REGION_BEG
1726 || note_type == NOTE_INSN_EH_REGION_END)
1727 NOTE_EH_HANDLER (last) = INTVAL (XEXP (note, 0));
1728 remove_note (insn, note);
1734 /* Move INSN, and all insns which should be issued before it,
1735 due to SCHED_GROUP_P flag. Reemit notes if needed.
1737 Return the last insn emitted by the scheduler, which is the
1738 return value from the first call to reemit_notes. */
1741 move_insn (insn, last)
1746 /* If INSN has SCHED_GROUP_P set, then issue it and any other
1747 insns with SCHED_GROUP_P set first. */
1748 while (SCHED_GROUP_P (insn))
1750 rtx prev = PREV_INSN (insn);
1752 /* Move a SCHED_GROUP_P insn. */
1753 move_insn1 (insn, last);
1754 /* If this is the first call to reemit_notes, then record
1755 its return value. */
1756 if (retval == NULL_RTX)
1757 retval = reemit_notes (insn, insn);
1759 reemit_notes (insn, insn);
1760 /* Consume SCHED_GROUP_P flag. */
1761 SCHED_GROUP_P (insn) = 0;
1765 /* Now move the first non SCHED_GROUP_P insn. */
1766 move_insn1 (insn, last);
1768 /* If this is the first call to reemit_notes, then record
1769 its return value. */
1770 if (retval == NULL_RTX)
1771 retval = reemit_notes (insn, insn);
1773 reemit_notes (insn, insn);
1778 /* The following function returns maximal (or close to maximal) number
1779 of insns which can be issued on the same cycle and one of which
1780 insns is insns with the best rank (the last insn in READY). To
1781 make this function tries different samples of ready insns. READY
1782 is current queue `ready'. Global array READY_TRY reflects what
1783 insns are already issued in this try. STATE is current processor
1784 state. If the function returns nonzero, INDEX will contain index
1785 of the best insn in READY. The following function is used only for
1786 first cycle multipass scheduling. */
1789 max_issue (ready, state, index)
1790 struct ready_list *ready;
1794 int i, best, n, temp_index, delay;
1797 int max_lookahead = (*targetm.sched.first_cycle_multipass_dfa_lookahead) ();
1799 if (state_dead_lock_p (state))
1802 temp_state = alloca (dfa_state_size);
1805 for (i = 0; i < ready->n_ready; i++)
1808 insn = ready_element (ready, i);
1810 if (INSN_CODE (insn) < 0)
1813 memcpy (temp_state, state, dfa_state_size);
1815 delay = state_transition (temp_state, insn);
1819 if (!targetm.sched.dfa_bubble)
1827 (bubble = (*targetm.sched.dfa_bubble) (j)) != NULL_RTX;
1829 if (state_transition (temp_state, bubble) < 0
1830 && state_transition (temp_state, insn) < 0)
1833 if (bubble == NULL_RTX)
1842 if (max_lookahead < 0)
1847 n = max_issue (ready, temp_state, &temp_index);
1848 if (n > 0 || ready_try[0])
1862 /* The following function chooses insn from READY and modifies
1863 *N_READY and READY. The following function is used only for first
1864 cycle multipass scheduling. */
1867 choose_ready (ready)
1868 struct ready_list *ready;
1870 if (!targetm.sched.first_cycle_multipass_dfa_lookahead
1871 || (*targetm.sched.first_cycle_multipass_dfa_lookahead) () <= 0)
1872 return ready_remove_first (ready);
1875 /* Try to choose the better insn. */
1878 if (max_issue (ready, curr_state, &index) == 0)
1879 return ready_remove_first (ready);
1881 return ready_remove (ready, index);
1885 /* Called from backends from targetm.sched.reorder to emit stuff into
1886 the instruction stream. */
1889 sched_emit_insn (pat)
1892 rtx insn = emit_insn_after (pat, last_scheduled_insn);
1893 last_scheduled_insn = insn;
1897 /* Use forward list scheduling to rearrange insns of block B in region RGN,
1898 possibly bringing insns from subsequent blocks in the same region. */
1901 schedule_block (b, rgn_n_insns)
1905 struct ready_list ready;
1906 int first_cycle_insn_p;
1908 state_t temp_state = NULL; /* It is used for multipass scheduling. */
1910 /* Head/tail info for this block. */
1911 rtx prev_head = current_sched_info->prev_head;
1912 rtx next_tail = current_sched_info->next_tail;
1913 rtx head = NEXT_INSN (prev_head);
1914 rtx tail = PREV_INSN (next_tail);
1916 /* We used to have code to avoid getting parameters moved from hard
1917 argument registers into pseudos.
1919 However, it was removed when it proved to be of marginal benefit
1920 and caused problems because schedule_block and compute_forward_dependences
1921 had different notions of what the "head" insn was. */
1923 if (head == tail && (! INSN_P (head)))
1929 fprintf (sched_dump, ";; ======================================================\n");
1930 fprintf (sched_dump,
1931 ";; -- basic block %d from %d to %d -- %s reload\n",
1932 b, INSN_UID (head), INSN_UID (tail),
1933 (reload_completed ? "after" : "before"));
1934 fprintf (sched_dump, ";; ======================================================\n");
1935 fprintf (sched_dump, "\n");
1938 init_block_visualization ();
1941 if (targetm.sched.use_dfa_pipeline_interface
1942 && (*targetm.sched.use_dfa_pipeline_interface) ())
1943 state_reset (curr_state);
1947 /* Allocate the ready list. */
1948 ready.veclen = rgn_n_insns + 1 + issue_rate;
1949 ready.first = ready.veclen - 1;
1950 ready.vec = (rtx *) xmalloc (ready.veclen * sizeof (rtx));
1953 if (targetm.sched.use_dfa_pipeline_interface
1954 && (*targetm.sched.use_dfa_pipeline_interface) ())
1956 /* It is used for first cycle multipass scheduling. */
1957 temp_state = alloca (dfa_state_size);
1958 ready_try = (char *) xmalloc ((rgn_n_insns + 1) * sizeof (char));
1959 memset (ready_try, 0, (rgn_n_insns + 1) * sizeof (char));
1962 (*current_sched_info->init_ready_list) (&ready);
1964 if (targetm.sched.md_init)
1965 (*targetm.sched.md_init) (sched_dump, sched_verbose, ready.veclen);
1967 /* We start inserting insns after PREV_HEAD. */
1968 last_scheduled_insn = prev_head;
1970 /* Initialize INSN_QUEUE. Q_SIZE is the total number of insns in the
1975 if (!targetm.sched.use_dfa_pipeline_interface
1976 || !(*targetm.sched.use_dfa_pipeline_interface) ())
1977 max_insn_queue_index_macro_value = INSN_QUEUE_SIZE - 1;
1979 max_insn_queue_index_macro_value = max_insn_queue_index;
1981 insn_queue = (rtx *) alloca ((MAX_INSN_QUEUE_INDEX + 1) * sizeof (rtx));
1982 memset ((char *) insn_queue, 0, (MAX_INSN_QUEUE_INDEX + 1) * sizeof (rtx));
1983 last_clock_var = -1;
1985 /* Start just before the beginning of time. */
1988 /* Loop until all the insns in BB are scheduled. */
1989 while ((*current_sched_info->schedule_more_p) ())
1993 advance_one_cycle ();
1995 /* Add to the ready list all pending insns that can be issued now.
1996 If there are no ready insns, increment clock until one
1997 is ready and add all pending insns at that point to the ready
1999 queue_to_ready (&ready);
2001 if (ready.n_ready == 0)
2004 if (sched_verbose >= 2)
2006 fprintf (sched_dump, ";;\t\tReady list after queue_to_ready: ");
2007 debug_ready_list (&ready);
2010 /* Sort the ready list based on priority. */
2011 ready_sort (&ready);
2013 /* Allow the target to reorder the list, typically for
2014 better instruction bundling. */
2015 if (targetm.sched.reorder)
2017 (*targetm.sched.reorder) (sched_dump, sched_verbose,
2018 ready_lastpos (&ready),
2019 &ready.n_ready, clock_var);
2021 can_issue_more = issue_rate;
2023 first_cycle_insn_p = 1;
2029 if (sched_verbose >= 2)
2031 fprintf (sched_dump, ";;\tReady list (t =%3d): ",
2033 debug_ready_list (&ready);
2036 if (!targetm.sched.use_dfa_pipeline_interface
2037 || !(*targetm.sched.use_dfa_pipeline_interface) ())
2039 if (ready.n_ready == 0 || !can_issue_more
2040 || !(*current_sched_info->schedule_more_p) ())
2042 insn = choose_ready (&ready);
2043 cost = actual_hazard (insn_unit (insn), insn, clock_var, 0);
2047 if (ready.n_ready == 0 || !can_issue_more
2048 || state_dead_lock_p (curr_state)
2049 || !(*current_sched_info->schedule_more_p) ())
2052 /* Select and remove the insn from the ready list. */
2053 insn = choose_ready (&ready);
2055 memcpy (temp_state, curr_state, dfa_state_size);
2056 if (recog_memoized (insn) < 0)
2058 if (!first_cycle_insn_p
2059 && (GET_CODE (PATTERN (insn)) == ASM_INPUT
2060 || asm_noperands (PATTERN (insn)) >= 0))
2061 /* This is asm insn which is tryed to be issued on the
2062 cycle not first. Issue it on the next cycle. */
2065 /* A USE insn, or something else we don't need to
2066 understand. We can't pass these directly to
2067 state_transition because it will trigger a
2068 fatal error for unrecognizable insns. */
2073 cost = state_transition (temp_state, insn);
2075 if (targetm.sched.first_cycle_multipass_dfa_lookahead
2076 && targetm.sched.dfa_bubble)
2084 (bubble = (*targetm.sched.dfa_bubble) (j))
2088 memcpy (temp_state, curr_state, dfa_state_size);
2090 if (state_transition (temp_state, bubble) < 0
2091 && state_transition (temp_state, insn) < 0)
2095 if (bubble != NULL_RTX)
2097 if (insert_schedule_bubbles_p)
2101 copy = copy_rtx (PATTERN (bubble));
2102 emit_insn_after (copy, last_scheduled_insn);
2104 = NEXT_INSN (last_scheduled_insn);
2105 INSN_CODE (last_scheduled_insn)
2106 = INSN_CODE (bubble);
2108 /* Annotate the same for the first insns
2109 scheduling by using mode. */
2110 PUT_MODE (last_scheduled_insn,
2111 (clock_var > last_clock_var
2112 ? clock_var - last_clock_var
2114 last_clock_var = clock_var;
2116 if (sched_verbose >= 2)
2118 fprintf (sched_dump,
2119 ";;\t\t--> scheduling bubble insn <<<%d>>>:reservation ",
2120 INSN_UID (last_scheduled_insn));
2122 if (recog_memoized (last_scheduled_insn)
2124 fprintf (sched_dump, "nothing");
2127 (sched_dump, last_scheduled_insn);
2129 fprintf (sched_dump, "\n");
2147 queue_insn (insn, cost);
2151 if (! (*current_sched_info->can_schedule_ready_p) (insn))
2154 last_scheduled_insn = move_insn (insn, last_scheduled_insn);
2156 if (targetm.sched.use_dfa_pipeline_interface
2157 && (*targetm.sched.use_dfa_pipeline_interface) ())
2158 memcpy (curr_state, temp_state, dfa_state_size);
2160 if (targetm.sched.variable_issue)
2162 (*targetm.sched.variable_issue) (sched_dump, sched_verbose,
2163 insn, can_issue_more);
2164 /* A naked CLOBBER or USE generates no instruction, so do
2165 not count them against the issue rate. */
2166 else if (GET_CODE (PATTERN (insn)) != USE
2167 && GET_CODE (PATTERN (insn)) != CLOBBER)
2170 schedule_insn (insn, &ready, clock_var);
2173 first_cycle_insn_p = 0;
2175 if (targetm.sched.reorder2)
2177 /* Sort the ready list based on priority. */
2178 if (ready.n_ready > 0)
2179 ready_sort (&ready);
2181 (*targetm.sched.reorder2) (sched_dump,sched_verbose,
2183 ? ready_lastpos (&ready) : NULL,
2184 &ready.n_ready, clock_var);
2188 if ((!targetm.sched.use_dfa_pipeline_interface
2189 || !(*targetm.sched.use_dfa_pipeline_interface) ())
2192 visualize_scheduled_insns (clock_var);
2195 if (targetm.sched.md_finish)
2196 (*targetm.sched.md_finish) (sched_dump, sched_verbose);
2201 fprintf (sched_dump, ";;\tReady list (final): ");
2202 debug_ready_list (&ready);
2203 if (!targetm.sched.use_dfa_pipeline_interface
2204 || !(*targetm.sched.use_dfa_pipeline_interface) ())
2205 print_block_visualization ("");
2208 /* Sanity check -- queue must be empty now. Meaningless if region has
2210 if (current_sched_info->queue_must_finish_empty && q_size != 0)
2213 /* Update head/tail boundaries. */
2214 head = NEXT_INSN (prev_head);
2215 tail = last_scheduled_insn;
2217 /* Restore-other-notes: NOTE_LIST is the end of a chain of notes
2218 previously found among the insns. Insert them at the beginning
2222 rtx note_head = note_list;
2224 while (PREV_INSN (note_head))
2226 note_head = PREV_INSN (note_head);
2229 PREV_INSN (note_head) = PREV_INSN (head);
2230 NEXT_INSN (PREV_INSN (head)) = note_head;
2231 PREV_INSN (head) = note_list;
2232 NEXT_INSN (note_list) = head;
2239 fprintf (sched_dump, ";; total time = %d\n;; new head = %d\n",
2240 clock_var, INSN_UID (head));
2241 fprintf (sched_dump, ";; new tail = %d\n\n",
2246 current_sched_info->head = head;
2247 current_sched_info->tail = tail;
2251 if (targetm.sched.use_dfa_pipeline_interface
2252 && (*targetm.sched.use_dfa_pipeline_interface) ())
2256 /* Set_priorities: compute priority of each insn in the block. */
2259 set_priorities (head, tail)
2267 prev_head = PREV_INSN (head);
2269 if (head == tail && (! INSN_P (head)))
2273 for (insn = tail; insn != prev_head; insn = PREV_INSN (insn))
2275 if (GET_CODE (insn) == NOTE)
2278 if (!(SCHED_GROUP_P (insn)))
2280 (void) priority (insn);
2286 /* Initialize some global state for the scheduler. DUMP_FILE is to be used
2287 for debugging output. */
2290 sched_init (dump_file)
2298 /* Disable speculative loads in their presence if cc0 defined. */
2300 flag_schedule_speculative_load = 0;
2303 /* Set dump and sched_verbose for the desired debugging output. If no
2304 dump-file was specified, but -fsched-verbose=N (any N), print to stderr.
2305 For -fsched-verbose=N, N>=10, print everything to stderr. */
2306 sched_verbose = sched_verbose_param;
2307 if (sched_verbose_param == 0 && dump_file)
2309 sched_dump = ((sched_verbose_param >= 10 || !dump_file)
2310 ? stderr : dump_file);
2312 /* Initialize issue_rate. */
2313 if (targetm.sched.issue_rate)
2314 issue_rate = (*targetm.sched.issue_rate) ();
2318 /* We use LUID 0 for the fake insn (UID 0) which holds dependencies for
2319 pseudos which do not cross calls. */
2320 old_max_uid = get_max_uid () + 1;
2322 h_i_d = (struct haifa_insn_data *) xcalloc (old_max_uid, sizeof (*h_i_d));
2324 for (i = 0; i < old_max_uid; i++)
2325 h_i_d [i].cost = -1;
2327 if (targetm.sched.use_dfa_pipeline_interface
2328 && (*targetm.sched.use_dfa_pipeline_interface) ())
2330 if (targetm.sched.init_dfa_pre_cycle_insn)
2331 (*targetm.sched.init_dfa_pre_cycle_insn) ();
2333 if (targetm.sched.init_dfa_post_cycle_insn)
2334 (*targetm.sched.init_dfa_post_cycle_insn) ();
2336 if (targetm.sched.first_cycle_multipass_dfa_lookahead
2337 && targetm.sched.init_dfa_bubbles)
2338 (*targetm.sched.init_dfa_bubbles) ();
2341 dfa_state_size = state_size ();
2342 curr_state = xmalloc (dfa_state_size);
2348 for (insn = b->head;; insn = NEXT_INSN (insn))
2350 INSN_LUID (insn) = luid;
2352 /* Increment the next luid, unless this is a note. We don't
2353 really need separate IDs for notes and we don't want to
2354 schedule differently depending on whether or not there are
2355 line-number notes, i.e., depending on whether or not we're
2356 generating debugging information. */
2357 if (GET_CODE (insn) != NOTE)
2364 init_dependency_caches (luid);
2366 init_alias_analysis ();
2368 if (write_symbols != NO_DEBUG)
2372 line_note_head = (rtx *) xcalloc (last_basic_block, sizeof (rtx));
2374 /* Save-line-note-head:
2375 Determine the line-number at the start of each basic block.
2376 This must be computed and saved now, because after a basic block's
2377 predecessor has been scheduled, it is impossible to accurately
2378 determine the correct line number for the first insn of the block. */
2382 for (line = b->head; line; line = PREV_INSN (line))
2383 if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
2385 line_note_head[b->index] = line;
2388 /* Do a forward search as well, since we won't get to see the first
2389 notes in a basic block. */
2390 for (line = b->head; line; line = NEXT_INSN (line))
2394 if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
2395 line_note_head[b->index] = line;
2400 if ((!targetm.sched.use_dfa_pipeline_interface
2401 || !(*targetm.sched.use_dfa_pipeline_interface) ())
2403 /* Find units used in this function, for visualization. */
2404 init_target_units ();
2406 /* ??? Add a NOTE after the last insn of the last basic block. It is not
2407 known why this is done. */
2409 insn = EXIT_BLOCK_PTR->prev_bb->end;
2410 if (NEXT_INSN (insn) == 0
2411 || (GET_CODE (insn) != NOTE
2412 && GET_CODE (insn) != CODE_LABEL
2413 /* Don't emit a NOTE if it would end up before a BARRIER. */
2414 && GET_CODE (NEXT_INSN (insn)) != BARRIER))
2416 emit_note_after (NOTE_INSN_DELETED, EXIT_BLOCK_PTR->prev_bb->end);
2417 /* Make insn to appear outside BB. */
2418 EXIT_BLOCK_PTR->prev_bb->end = PREV_INSN (EXIT_BLOCK_PTR->prev_bb->end);
2421 /* Compute INSN_REG_WEIGHT for all blocks. We must do this before
2422 removing death notes. */
2423 FOR_EACH_BB_REVERSE (b)
2424 find_insn_reg_weight (b->index);
2427 /* Free global data used during insn scheduling. */
2434 if (targetm.sched.use_dfa_pipeline_interface
2435 && (*targetm.sched.use_dfa_pipeline_interface) ())
2440 free_dependency_caches ();
2441 end_alias_analysis ();
2442 if (write_symbols != NO_DEBUG)
2443 free (line_note_head);
2445 #endif /* INSN_SCHEDULING */