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. */
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"
153 #ifdef INSN_SCHEDULING
155 /* issue_rate is the number of insns that can be scheduled in the same
156 machine cycle. It can be defined in the config/mach/mach.h file,
157 otherwise we set it to 1. */
159 static int issue_rate
;
161 /* If the following variable value is nonzero, the scheduler inserts
162 bubbles (nop insns). The value of variable affects on scheduler
163 behavior only if automaton pipeline interface with multipass
164 scheduling is used and hook dfa_bubble is defined. */
165 int insert_schedule_bubbles_p
= 0;
167 /* sched-verbose controls the amount of debugging output the
168 scheduler prints. It is controlled by -fsched-verbose=N:
169 N>0 and no -DSR : the output is directed to stderr.
170 N>=10 will direct the printouts to stderr (regardless of -dSR).
172 N=2: bb's probabilities, detailed ready list info, unit/insn info.
173 N=3: rtl at abort point, control-flow, regions info.
174 N=5: dependences info. */
176 static int sched_verbose_param
= 0;
177 int sched_verbose
= 0;
179 /* Debugging file. All printouts are sent to dump, which is always set,
180 either to stderr, or to the dump listing file (-dRS). */
181 FILE *sched_dump
= 0;
183 /* Highest uid before scheduling. */
184 static int old_max_uid
;
186 /* fix_sched_param() is called from toplev.c upon detection
187 of the -fsched-verbose=N option. */
190 fix_sched_param (param
, val
)
191 const char *param
, *val
;
193 if (!strcmp (param
, "verbose"))
194 sched_verbose_param
= atoi (val
);
196 warning ("fix_sched_param: unknown param: %s", param
);
199 struct haifa_insn_data
*h_i_d
;
201 #define LINE_NOTE(INSN) (h_i_d[INSN_UID (INSN)].line_note)
202 #define INSN_TICK(INSN) (h_i_d[INSN_UID (INSN)].tick)
204 /* Vector indexed by basic block number giving the starting line-number
205 for each basic block. */
206 static rtx
*line_note_head
;
208 /* List of important notes we must keep around. This is a pointer to the
209 last element in the list. */
210 static rtx note_list
;
214 /* An instruction is ready to be scheduled when all insns preceding it
215 have already been scheduled. It is important to ensure that all
216 insns which use its result will not be executed until its result
217 has been computed. An insn is maintained in one of four structures:
219 (P) the "Pending" set of insns which cannot be scheduled until
220 their dependencies have been satisfied.
221 (Q) the "Queued" set of insns that can be scheduled when sufficient
223 (R) the "Ready" list of unscheduled, uncommitted insns.
224 (S) the "Scheduled" list of insns.
226 Initially, all insns are either "Pending" or "Ready" depending on
227 whether their dependencies are satisfied.
229 Insns move from the "Ready" list to the "Scheduled" list as they
230 are committed to the schedule. As this occurs, the insns in the
231 "Pending" list have their dependencies satisfied and move to either
232 the "Ready" list or the "Queued" set depending on whether
233 sufficient time has passed to make them ready. As time passes,
234 insns move from the "Queued" set to the "Ready" list. Insns may
235 move from the "Ready" list to the "Queued" set if they are blocked
236 due to a function unit conflict.
238 The "Pending" list (P) are the insns in the INSN_DEPEND of the unscheduled
239 insns, i.e., those that are ready, queued, and pending.
240 The "Queued" set (Q) is implemented by the variable `insn_queue'.
241 The "Ready" list (R) is implemented by the variables `ready' and
243 The "Scheduled" list (S) is the new insn chain built by this pass.
245 The transition (R->S) is implemented in the scheduling loop in
246 `schedule_block' when the best insn to schedule is chosen.
247 The transition (R->Q) is implemented in `queue_insn' when an
248 insn is found to have a function unit conflict with the already
250 The transitions (P->R and P->Q) are implemented in `schedule_insn' as
251 insns move from the ready list to the scheduled list.
252 The transition (Q->R) is implemented in 'queue_to_insn' as time
253 passes or stalls are introduced. */
255 /* Implement a circular buffer to delay instructions until sufficient
256 time has passed. For the old pipeline description interface,
257 INSN_QUEUE_SIZE is a power of two larger than MAX_BLOCKAGE and
258 MAX_READY_COST computed by genattr.c. For the new pipeline
259 description interface, MAX_INSN_QUEUE_INDEX is a power of two minus
260 one which is larger than maximal time of instruction execution
261 computed by genattr.c on the base maximal time of functional unit
262 reservations and geting a result. This is the longest time an
263 insn may be queued. */
265 #define MAX_INSN_QUEUE_INDEX max_insn_queue_index_macro_value
267 static rtx
*insn_queue
;
268 static int q_ptr
= 0;
269 static int q_size
= 0;
270 #define NEXT_Q(X) (((X)+1) & MAX_INSN_QUEUE_INDEX)
271 #define NEXT_Q_AFTER(X, C) (((X)+C) & MAX_INSN_QUEUE_INDEX)
273 /* The following variable defines value for macro
274 MAX_INSN_QUEUE_INDEX. */
275 static int max_insn_queue_index_macro_value
;
277 /* The following variable value refers for all current and future
278 reservations of the processor units. */
281 /* The following variable value is size of memory representing all
282 current and future reservations of the processor units. It is used
283 only by DFA based scheduler. */
284 static size_t dfa_state_size
;
286 /* The following array is used to find the best insn from ready when
287 the automaton pipeline interface is used. */
288 static char *ready_try
;
290 /* Describe the ready list of the scheduler.
291 VEC holds space enough for all insns in the current region. VECLEN
292 says how many exactly.
293 FIRST is the index of the element with the highest priority; i.e. the
294 last one in the ready list, since elements are ordered by ascending
296 N_READY determines how many insns are on the ready list. */
306 /* Forward declarations. */
308 /* The scheduler using only DFA description should never use the
309 following five functions: */
310 static unsigned int blockage_range
PARAMS ((int, rtx
));
311 static void clear_units
PARAMS ((void));
312 static void schedule_unit
PARAMS ((int, rtx
, int));
313 static int actual_hazard
PARAMS ((int, rtx
, int, int));
314 static int potential_hazard
PARAMS ((int, rtx
, int));
316 static int priority
PARAMS ((rtx
));
317 static int rank_for_schedule
PARAMS ((const PTR
, const PTR
));
318 static void swap_sort
PARAMS ((rtx
*, int));
319 static void queue_insn
PARAMS ((rtx
, int));
320 static void schedule_insn
PARAMS ((rtx
, struct ready_list
*, int));
321 static void find_insn_reg_weight
PARAMS ((int));
322 static void adjust_priority
PARAMS ((rtx
));
323 static void advance_one_cycle
PARAMS ((void));
325 /* Notes handling mechanism:
326 =========================
327 Generally, NOTES are saved before scheduling and restored after scheduling.
328 The scheduler distinguishes between three types of notes:
330 (1) LINE_NUMBER notes, generated and used for debugging. Here,
331 before scheduling a region, a pointer to the LINE_NUMBER note is
332 added to the insn following it (in save_line_notes()), and the note
333 is removed (in rm_line_notes() and unlink_line_notes()). After
334 scheduling the region, this pointer is used for regeneration of
335 the LINE_NUMBER note (in restore_line_notes()).
337 (2) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes:
338 Before scheduling a region, a pointer to the note is added to the insn
339 that follows or precedes it. (This happens as part of the data dependence
340 computation). After scheduling an insn, the pointer contained in it is
341 used for regenerating the corresponding note (in reemit_notes).
343 (3) All other notes (e.g. INSN_DELETED): Before scheduling a block,
344 these notes are put in a list (in rm_other_notes() and
345 unlink_other_notes ()). After scheduling the block, these notes are
346 inserted at the beginning of the block (in schedule_block()). */
348 static rtx unlink_other_notes
PARAMS ((rtx
, rtx
));
349 static rtx unlink_line_notes
PARAMS ((rtx
, rtx
));
350 static rtx reemit_notes
PARAMS ((rtx
, rtx
));
352 static rtx
*ready_lastpos
PARAMS ((struct ready_list
*));
353 static void ready_sort
PARAMS ((struct ready_list
*));
354 static rtx ready_remove_first
PARAMS ((struct ready_list
*));
356 static void queue_to_ready
PARAMS ((struct ready_list
*));
358 static void debug_ready_list
PARAMS ((struct ready_list
*));
360 static rtx move_insn1
PARAMS ((rtx
, rtx
));
361 static rtx move_insn
PARAMS ((rtx
, rtx
));
363 /* The following functions are used to implement multi-pass scheduling
364 on the first cycle. It is used only for DFA based scheduler. */
365 static rtx ready_element
PARAMS ((struct ready_list
*, int));
366 static rtx ready_remove
PARAMS ((struct ready_list
*, int));
367 static int max_issue
PARAMS ((struct ready_list
*, state_t
, int *));
369 static rtx choose_ready
PARAMS ((struct ready_list
*));
371 #endif /* INSN_SCHEDULING */
373 /* Point to state used for the current scheduling pass. */
374 struct sched_info
*current_sched_info
;
376 #ifndef INSN_SCHEDULING
378 schedule_insns (dump_file
)
379 FILE *dump_file ATTRIBUTE_UNUSED
;
384 /* Pointer to the last instruction scheduled. Used by rank_for_schedule,
385 so that insns independent of the last scheduled insn will be preferred
386 over dependent instructions. */
388 static rtx last_scheduled_insn
;
390 /* Compute the function units used by INSN. This caches the value
391 returned by function_units_used. A function unit is encoded as the
392 unit number if the value is non-negative and the compliment of a
393 mask if the value is negative. A function unit index is the
394 non-negative encoding. The scheduler using only DFA description
395 should never use the following function. */
401 int unit
= INSN_UNIT (insn
);
405 recog_memoized (insn
);
407 /* A USE insn, or something else we don't need to understand.
408 We can't pass these directly to function_units_used because it will
409 trigger a fatal error for unrecognizable insns. */
410 if (INSN_CODE (insn
) < 0)
414 unit
= function_units_used (insn
);
415 /* Increment non-negative values so we can cache zero. */
419 /* We only cache 16 bits of the result, so if the value is out of
420 range, don't cache it. */
421 if (FUNCTION_UNITS_SIZE
< HOST_BITS_PER_SHORT
423 || (unit
& ~((1 << (HOST_BITS_PER_SHORT
- 1)) - 1)) == 0)
424 INSN_UNIT (insn
) = unit
;
426 return (unit
> 0 ? unit
- 1 : unit
);
429 /* Compute the blockage range for executing INSN on UNIT. This caches
430 the value returned by the blockage_range_function for the unit.
431 These values are encoded in an int where the upper half gives the
432 minimum value and the lower half gives the maximum value. The
433 scheduler using only DFA description should never use the following
436 HAIFA_INLINE
static unsigned int
437 blockage_range (unit
, insn
)
441 unsigned int blockage
= INSN_BLOCKAGE (insn
);
444 if ((int) UNIT_BLOCKED (blockage
) != unit
+ 1)
446 range
= function_units
[unit
].blockage_range_function (insn
);
447 /* We only cache the blockage range for one unit and then only if
449 if (HOST_BITS_PER_INT
>= UNIT_BITS
+ 2 * BLOCKAGE_BITS
)
450 INSN_BLOCKAGE (insn
) = ENCODE_BLOCKAGE (unit
+ 1, range
);
453 range
= BLOCKAGE_RANGE (blockage
);
458 /* A vector indexed by function unit instance giving the last insn to
459 use the unit. The value of the function unit instance index for
460 unit U instance I is (U + I * FUNCTION_UNITS_SIZE). The scheduler
461 using only DFA description should never use the following variable. */
462 #if FUNCTION_UNITS_SIZE
463 static rtx unit_last_insn
[FUNCTION_UNITS_SIZE
* MAX_MULTIPLICITY
];
465 static rtx unit_last_insn
[1];
468 /* A vector indexed by function unit instance giving the minimum time
469 when the unit will unblock based on the maximum blockage cost. The
470 scheduler using only DFA description should never use the following
472 #if FUNCTION_UNITS_SIZE
473 static int unit_tick
[FUNCTION_UNITS_SIZE
* MAX_MULTIPLICITY
];
475 static int unit_tick
[1];
478 /* A vector indexed by function unit number giving the number of insns
479 that remain to use the unit. The scheduler using only DFA
480 description should never use the following variable. */
481 #if FUNCTION_UNITS_SIZE
482 static int unit_n_insns
[FUNCTION_UNITS_SIZE
];
484 static int unit_n_insns
[1];
487 /* Access the unit_last_insn array. Used by the visualization code.
488 The scheduler using only DFA description should never use the
489 following function. */
492 get_unit_last_insn (instance
)
495 return unit_last_insn
[instance
];
498 /* Reset the function unit state to the null state. */
503 memset ((char *) unit_last_insn
, 0, sizeof (unit_last_insn
));
504 memset ((char *) unit_tick
, 0, sizeof (unit_tick
));
505 memset ((char *) unit_n_insns
, 0, sizeof (unit_n_insns
));
508 /* Return the issue-delay of an insn. The scheduler using only DFA
509 description should never use the following function. */
512 insn_issue_delay (insn
)
516 int unit
= insn_unit (insn
);
518 /* Efficiency note: in fact, we are working 'hard' to compute a
519 value that was available in md file, and is not available in
520 function_units[] structure. It would be nice to have this
524 if (function_units
[unit
].blockage_range_function
&&
525 function_units
[unit
].blockage_function
)
526 delay
= function_units
[unit
].blockage_function (insn
, insn
);
529 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
530 if ((unit
& 1) != 0 && function_units
[i
].blockage_range_function
531 && function_units
[i
].blockage_function
)
532 delay
= MAX (delay
, function_units
[i
].blockage_function (insn
, insn
));
537 /* Return the actual hazard cost of executing INSN on the unit UNIT,
538 instance INSTANCE at time CLOCK if the previous actual hazard cost
539 was COST. The scheduler using only DFA description should never
540 use the following function. */
543 actual_hazard_this_instance (unit
, instance
, insn
, clock
, cost
)
544 int unit
, instance
, clock
, cost
;
547 int tick
= unit_tick
[instance
]; /* Issue time of the last issued insn. */
549 if (tick
- clock
> cost
)
551 /* The scheduler is operating forward, so unit's last insn is the
552 executing insn and INSN is the candidate insn. We want a
553 more exact measure of the blockage if we execute INSN at CLOCK
554 given when we committed the execution of the unit's last insn.
556 The blockage value is given by either the unit's max blockage
557 constant, blockage range function, or blockage function. Use
558 the most exact form for the given unit. */
560 if (function_units
[unit
].blockage_range_function
)
562 if (function_units
[unit
].blockage_function
)
563 tick
+= (function_units
[unit
].blockage_function
564 (unit_last_insn
[instance
], insn
)
565 - function_units
[unit
].max_blockage
);
567 tick
+= ((int) MAX_BLOCKAGE_COST (blockage_range (unit
, insn
))
568 - function_units
[unit
].max_blockage
);
570 if (tick
- clock
> cost
)
576 /* Record INSN as having begun execution on the units encoded by UNIT
577 at time CLOCK. The scheduler using only DFA description should
578 never use the following function. */
580 HAIFA_INLINE
static void
581 schedule_unit (unit
, insn
, clock
)
590 #if MAX_MULTIPLICITY > 1
591 /* Find the first free instance of the function unit and use that
592 one. We assume that one is free. */
593 for (i
= function_units
[unit
].multiplicity
- 1; i
> 0; i
--)
595 if (!actual_hazard_this_instance (unit
, instance
, insn
, clock
, 0))
597 instance
+= FUNCTION_UNITS_SIZE
;
600 unit_last_insn
[instance
] = insn
;
601 unit_tick
[instance
] = (clock
+ function_units
[unit
].max_blockage
);
604 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
606 schedule_unit (i
, insn
, clock
);
609 /* Return the actual hazard cost of executing INSN on the units
610 encoded by UNIT at time CLOCK if the previous actual hazard cost
611 was COST. The scheduler using only DFA description should never
612 use the following function. */
614 HAIFA_INLINE
static int
615 actual_hazard (unit
, insn
, clock
, cost
)
616 int unit
, clock
, cost
;
623 /* Find the instance of the function unit with the minimum hazard. */
625 int best_cost
= actual_hazard_this_instance (unit
, instance
, insn
,
627 #if MAX_MULTIPLICITY > 1
630 if (best_cost
> cost
)
632 for (i
= function_units
[unit
].multiplicity
- 1; i
> 0; i
--)
634 instance
+= FUNCTION_UNITS_SIZE
;
635 this_cost
= actual_hazard_this_instance (unit
, instance
, insn
,
637 if (this_cost
< best_cost
)
639 best_cost
= this_cost
;
640 if (this_cost
<= cost
)
646 cost
= MAX (cost
, best_cost
);
649 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
651 cost
= actual_hazard (i
, insn
, clock
, cost
);
656 /* Return the potential hazard cost of executing an instruction on the
657 units encoded by UNIT if the previous potential hazard cost was
658 COST. An insn with a large blockage time is chosen in preference
659 to one with a smaller time; an insn that uses a unit that is more
660 likely to be used is chosen in preference to one with a unit that
661 is less used. We are trying to minimize a subsequent actual
662 hazard. The scheduler using only DFA description should never use
663 the following function. */
665 HAIFA_INLINE
static int
666 potential_hazard (unit
, insn
, cost
)
671 unsigned int minb
, maxb
;
675 minb
= maxb
= function_units
[unit
].max_blockage
;
678 if (function_units
[unit
].blockage_range_function
)
680 maxb
= minb
= blockage_range (unit
, insn
);
681 maxb
= MAX_BLOCKAGE_COST (maxb
);
682 minb
= MIN_BLOCKAGE_COST (minb
);
687 /* Make the number of instructions left dominate. Make the
688 minimum delay dominate the maximum delay. If all these
689 are the same, use the unit number to add an arbitrary
690 ordering. Other terms can be added. */
691 ncost
= minb
* 0x40 + maxb
;
692 ncost
*= (unit_n_insns
[unit
] - 1) * 0x1000 + unit
;
699 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
701 cost
= potential_hazard (i
, insn
, cost
);
706 /* Compute cost of executing INSN given the dependence LINK on the insn USED.
707 This is the number of cycles between instruction issue and
708 instruction results. */
711 insn_cost (insn
, link
, used
)
712 rtx insn
, link
, used
;
714 int cost
= INSN_COST (insn
);
718 /* A USE insn, or something else we don't need to
719 understand. We can't pass these directly to
720 result_ready_cost or insn_default_latency because it will
721 trigger a fatal error for unrecognizable insns. */
722 if (recog_memoized (insn
) < 0)
724 INSN_COST (insn
) = 0;
729 if (targetm
.sched
.use_dfa_pipeline_interface
730 && (*targetm
.sched
.use_dfa_pipeline_interface
) ())
731 cost
= insn_default_latency (insn
);
733 cost
= result_ready_cost (insn
);
738 INSN_COST (insn
) = cost
;
742 /* In this case estimate cost without caring how insn is used. */
743 if (link
== 0 || used
== 0)
746 /* A USE insn should never require the value used to be computed.
747 This allows the computation of a function's result and parameter
748 values to overlap the return and call. */
749 if (recog_memoized (used
) < 0)
753 if (targetm
.sched
.use_dfa_pipeline_interface
754 && (*targetm
.sched
.use_dfa_pipeline_interface
) ())
756 if (INSN_CODE (insn
) >= 0)
758 if (REG_NOTE_KIND (link
) == REG_DEP_ANTI
)
760 else if (REG_NOTE_KIND (link
) == REG_DEP_OUTPUT
)
762 cost
= (insn_default_latency (insn
)
763 - insn_default_latency (used
));
767 else if (bypass_p (insn
))
768 cost
= insn_latency (insn
, used
);
772 if (targetm
.sched
.adjust_cost
)
773 cost
= (*targetm
.sched
.adjust_cost
) (used
, link
, insn
, cost
);
782 /* Compute the priority number for INSN. */
793 if (! INSN_PRIORITY_KNOWN (insn
))
795 int this_priority
= 0;
797 if (INSN_DEPEND (insn
) == 0)
798 this_priority
= insn_cost (insn
, 0, 0);
801 for (link
= INSN_DEPEND (insn
); link
; link
= XEXP (link
, 1))
806 if (RTX_INTEGRATED_P (link
))
809 next
= XEXP (link
, 0);
811 /* Critical path is meaningful in block boundaries only. */
812 if (! (*current_sched_info
->contributes_to_priority
) (next
, insn
))
815 next_priority
= insn_cost (insn
, link
, next
) + priority (next
);
816 if (next_priority
> this_priority
)
817 this_priority
= next_priority
;
820 INSN_PRIORITY (insn
) = this_priority
;
821 INSN_PRIORITY_KNOWN (insn
) = 1;
824 return INSN_PRIORITY (insn
);
827 /* Macros and functions for keeping the priority queue sorted, and
828 dealing with queueing and dequeueing of instructions. */
830 #define SCHED_SORT(READY, N_READY) \
831 do { if ((N_READY) == 2) \
832 swap_sort (READY, N_READY); \
833 else if ((N_READY) > 2) \
834 qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \
837 /* Returns a positive value if x is preferred; returns a negative value if
838 y is preferred. Should never return 0, since that will make the sort
842 rank_for_schedule (x
, y
)
846 rtx tmp
= *(const rtx
*) y
;
847 rtx tmp2
= *(const rtx
*) x
;
849 int tmp_class
, tmp2_class
, depend_count1
, depend_count2
;
850 int val
, priority_val
, weight_val
, info_val
;
852 /* Prefer insn with higher priority. */
853 priority_val
= INSN_PRIORITY (tmp2
) - INSN_PRIORITY (tmp
);
857 /* Prefer an insn with smaller contribution to registers-pressure. */
858 if (!reload_completed
&&
859 (weight_val
= INSN_REG_WEIGHT (tmp
) - INSN_REG_WEIGHT (tmp2
)))
862 info_val
= (*current_sched_info
->rank
) (tmp
, tmp2
);
866 /* Compare insns based on their relation to the last-scheduled-insn. */
867 if (last_scheduled_insn
)
869 /* Classify the instructions into three classes:
870 1) Data dependent on last schedule insn.
871 2) Anti/Output dependent on last scheduled insn.
872 3) Independent of last scheduled insn, or has latency of one.
873 Choose the insn from the highest numbered class if different. */
874 link
= find_insn_list (tmp
, INSN_DEPEND (last_scheduled_insn
));
875 if (link
== 0 || insn_cost (last_scheduled_insn
, link
, tmp
) == 1)
877 else if (REG_NOTE_KIND (link
) == 0) /* Data dependence. */
882 link
= find_insn_list (tmp2
, INSN_DEPEND (last_scheduled_insn
));
883 if (link
== 0 || insn_cost (last_scheduled_insn
, link
, tmp2
) == 1)
885 else if (REG_NOTE_KIND (link
) == 0) /* Data dependence. */
890 if ((val
= tmp2_class
- tmp_class
))
894 /* Prefer the insn which has more later insns that depend on it.
895 This gives the scheduler more freedom when scheduling later
896 instructions at the expense of added register pressure. */
898 for (link
= INSN_DEPEND (tmp
); link
; link
= XEXP (link
, 1))
902 for (link
= INSN_DEPEND (tmp2
); link
; link
= XEXP (link
, 1))
905 val
= depend_count2
- depend_count1
;
909 /* If insns are equally good, sort by INSN_LUID (original insn order),
910 so that we make the sort stable. This minimizes instruction movement,
911 thus minimizing sched's effect on debugging and cross-jumping. */
912 return INSN_LUID (tmp
) - INSN_LUID (tmp2
);
915 /* Resort the array A in which only element at index N may be out of order. */
917 HAIFA_INLINE
static void
925 while (i
>= 0 && rank_for_schedule (a
+ i
, &insn
) >= 0)
933 /* Add INSN to the insn queue so that it can be executed at least
934 N_CYCLES after the currently executing insn. Preserve insns
935 chain for debugging purposes. */
937 HAIFA_INLINE
static void
938 queue_insn (insn
, n_cycles
)
942 int next_q
= NEXT_Q_AFTER (q_ptr
, n_cycles
);
943 rtx link
= alloc_INSN_LIST (insn
, insn_queue
[next_q
]);
944 insn_queue
[next_q
] = link
;
947 if (sched_verbose
>= 2)
949 fprintf (sched_dump
, ";;\t\tReady-->Q: insn %s: ",
950 (*current_sched_info
->print_insn
) (insn
, 0));
952 fprintf (sched_dump
, "queued for %d cycles.\n", n_cycles
);
956 /* Return a pointer to the bottom of the ready list, i.e. the insn
957 with the lowest priority. */
959 HAIFA_INLINE
static rtx
*
960 ready_lastpos (ready
)
961 struct ready_list
*ready
;
963 if (ready
->n_ready
== 0)
965 return ready
->vec
+ ready
->first
- ready
->n_ready
+ 1;
968 /* Add an element INSN to the ready list so that it ends up with the lowest
972 ready_add (ready
, insn
)
973 struct ready_list
*ready
;
976 if (ready
->first
== ready
->n_ready
)
978 memmove (ready
->vec
+ ready
->veclen
- ready
->n_ready
,
979 ready_lastpos (ready
),
980 ready
->n_ready
* sizeof (rtx
));
981 ready
->first
= ready
->veclen
- 1;
983 ready
->vec
[ready
->first
- ready
->n_ready
] = insn
;
987 /* Remove the element with the highest priority from the ready list and
990 HAIFA_INLINE
static rtx
991 ready_remove_first (ready
)
992 struct ready_list
*ready
;
995 if (ready
->n_ready
== 0)
997 t
= ready
->vec
[ready
->first
--];
999 /* If the queue becomes empty, reset it. */
1000 if (ready
->n_ready
== 0)
1001 ready
->first
= ready
->veclen
- 1;
1005 /* The following code implements multi-pass scheduling for the first
1006 cycle. In other words, we will try to choose ready insn which
1007 permits to start maximum number of insns on the same cycle. */
1009 /* Return a pointer to the element INDEX from the ready. INDEX for
1010 insn with the highest priority is 0, and the lowest priority has
1013 HAIFA_INLINE
static rtx
1014 ready_element (ready
, index
)
1015 struct ready_list
*ready
;
1018 if (ready
->n_ready
== 0 || index
>= ready
->n_ready
)
1020 return ready
->vec
[ready
->first
- index
];
1023 /* Remove the element INDEX from the ready list and return it. INDEX
1024 for insn with the highest priority is 0, and the lowest priority
1027 HAIFA_INLINE
static rtx
1028 ready_remove (ready
, index
)
1029 struct ready_list
*ready
;
1036 return ready_remove_first (ready
);
1037 if (ready
->n_ready
== 0 || index
>= ready
->n_ready
)
1039 t
= ready
->vec
[ready
->first
- index
];
1041 for (i
= index
; i
< ready
->n_ready
; i
++)
1042 ready
->vec
[ready
->first
- i
] = ready
->vec
[ready
->first
- i
- 1];
1047 /* Sort the ready list READY by ascending priority, using the SCHED_SORT
1050 HAIFA_INLINE
static void
1052 struct ready_list
*ready
;
1054 rtx
*first
= ready_lastpos (ready
);
1055 SCHED_SORT (first
, ready
->n_ready
);
1058 /* PREV is an insn that is ready to execute. Adjust its priority if that
1059 will help shorten or lengthen register lifetimes as appropriate. Also
1060 provide a hook for the target to tweek itself. */
1062 HAIFA_INLINE
static void
1063 adjust_priority (prev
)
1066 /* ??? There used to be code here to try and estimate how an insn
1067 affected register lifetimes, but it did it by looking at REG_DEAD
1068 notes, which we removed in schedule_region. Nor did it try to
1069 take into account register pressure or anything useful like that.
1071 Revisit when we have a machine model to work with and not before. */
1073 if (targetm
.sched
.adjust_priority
)
1074 INSN_PRIORITY (prev
) =
1075 (*targetm
.sched
.adjust_priority
) (prev
, INSN_PRIORITY (prev
));
1078 /* Advance time on one cycle. */
1079 HAIFA_INLINE
static void
1080 advance_one_cycle ()
1082 if (targetm
.sched
.use_dfa_pipeline_interface
1083 && (*targetm
.sched
.use_dfa_pipeline_interface
) ())
1085 if (targetm
.sched
.dfa_pre_cycle_insn
)
1086 state_transition (curr_state
,
1087 (*targetm
.sched
.dfa_pre_cycle_insn
) ());
1089 state_transition (curr_state
, NULL
);
1091 if (targetm
.sched
.dfa_post_cycle_insn
)
1092 state_transition (curr_state
,
1093 (*targetm
.sched
.dfa_post_cycle_insn
) ());
1097 /* Clock at which the previous instruction was issued. */
1098 static int last_clock_var
;
1100 /* INSN is the "currently executing insn". Launch each insn which was
1101 waiting on INSN. READY is the ready list which contains the insns
1102 that are ready to fire. CLOCK is the current cycle.
1106 schedule_insn (insn
, ready
, clock
)
1108 struct ready_list
*ready
;
1114 if (!targetm
.sched
.use_dfa_pipeline_interface
1115 || !(*targetm
.sched
.use_dfa_pipeline_interface
) ())
1116 unit
= insn_unit (insn
);
1118 if (targetm
.sched
.use_dfa_pipeline_interface
1119 && (*targetm
.sched
.use_dfa_pipeline_interface
) ()
1120 && sched_verbose
>= 1)
1124 print_insn (buf
, insn
, 0);
1126 fprintf (sched_dump
, ";;\t%3i--> %-40s:", clock
, buf
);
1128 if (recog_memoized (insn
) < 0)
1129 fprintf (sched_dump
, "nothing");
1131 print_reservation (sched_dump
, insn
);
1132 fputc ('\n', sched_dump
);
1134 else if (sched_verbose
>= 2)
1136 fprintf (sched_dump
, ";;\t\t--> scheduling insn <<<%d>>> on unit ",
1138 insn_print_units (insn
);
1139 fputc ('\n', sched_dump
);
1142 if (!targetm
.sched
.use_dfa_pipeline_interface
1143 || !(*targetm
.sched
.use_dfa_pipeline_interface
) ())
1145 if (sched_verbose
&& unit
== -1)
1146 visualize_no_unit (insn
);
1149 if (MAX_BLOCKAGE
> 1 || issue_rate
> 1 || sched_verbose
)
1150 schedule_unit (unit
, insn
, clock
);
1152 if (INSN_DEPEND (insn
) == 0)
1156 for (link
= INSN_DEPEND (insn
); link
!= 0; link
= XEXP (link
, 1))
1158 rtx next
= XEXP (link
, 0);
1159 int cost
= insn_cost (insn
, link
, next
);
1161 INSN_TICK (next
) = MAX (INSN_TICK (next
), clock
+ cost
);
1163 if ((INSN_DEP_COUNT (next
) -= 1) == 0)
1165 int effective_cost
= INSN_TICK (next
) - clock
;
1167 if (! (*current_sched_info
->new_ready
) (next
))
1170 if (sched_verbose
>= 2)
1172 fprintf (sched_dump
, ";;\t\tdependences resolved: insn %s ",
1173 (*current_sched_info
->print_insn
) (next
, 0));
1175 if (effective_cost
< 1)
1176 fprintf (sched_dump
, "into ready\n");
1178 fprintf (sched_dump
, "into queue with cost=%d\n", effective_cost
);
1181 /* Adjust the priority of NEXT and either put it on the ready
1182 list or queue it. */
1183 adjust_priority (next
);
1184 if (effective_cost
< 1)
1185 ready_add (ready
, next
);
1187 queue_insn (next
, effective_cost
);
1191 /* Annotate the instruction with issue information -- TImode
1192 indicates that the instruction is expected not to be able
1193 to issue on the same cycle as the previous insn. A machine
1194 may use this information to decide how the instruction should
1196 if (reload_completed
&& issue_rate
> 1
1197 && GET_CODE (PATTERN (insn
)) != USE
1198 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
1200 PUT_MODE (insn
, clock
> last_clock_var
? TImode
: VOIDmode
);
1201 last_clock_var
= clock
;
1205 /* Functions for handling of notes. */
1207 /* Delete notes beginning with INSN and put them in the chain
1208 of notes ended by NOTE_LIST.
1209 Returns the insn following the notes. */
1212 unlink_other_notes (insn
, tail
)
1215 rtx prev
= PREV_INSN (insn
);
1217 while (insn
!= tail
&& GET_CODE (insn
) == NOTE
)
1219 rtx next
= NEXT_INSN (insn
);
1220 /* Delete the note from its current position. */
1222 NEXT_INSN (prev
) = next
;
1224 PREV_INSN (next
) = prev
;
1226 /* See sched_analyze to see how these are handled. */
1227 if (NOTE_LINE_NUMBER (insn
) != NOTE_INSN_LOOP_BEG
1228 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_LOOP_END
1229 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_EH_REGION_BEG
1230 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_EH_REGION_END
)
1232 /* Insert the note at the end of the notes list. */
1233 PREV_INSN (insn
) = note_list
;
1235 NEXT_INSN (note_list
) = insn
;
1244 /* Delete line notes beginning with INSN. Record line-number notes so
1245 they can be reused. Returns the insn following the notes. */
1248 unlink_line_notes (insn
, tail
)
1251 rtx prev
= PREV_INSN (insn
);
1253 while (insn
!= tail
&& GET_CODE (insn
) == NOTE
)
1255 rtx next
= NEXT_INSN (insn
);
1257 if (write_symbols
!= NO_DEBUG
&& NOTE_LINE_NUMBER (insn
) > 0)
1259 /* Delete the note from its current position. */
1261 NEXT_INSN (prev
) = next
;
1263 PREV_INSN (next
) = prev
;
1265 /* Record line-number notes so they can be reused. */
1266 LINE_NOTE (insn
) = insn
;
1276 /* Return the head and tail pointers of BB. */
1279 get_block_head_tail (b
, headp
, tailp
)
1284 /* HEAD and TAIL delimit the basic block being scheduled. */
1285 rtx head
= BLOCK_HEAD (b
);
1286 rtx tail
= BLOCK_END (b
);
1288 /* Don't include any notes or labels at the beginning of the
1289 basic block, or notes at the ends of basic blocks. */
1290 while (head
!= tail
)
1292 if (GET_CODE (head
) == NOTE
)
1293 head
= NEXT_INSN (head
);
1294 else if (GET_CODE (tail
) == NOTE
)
1295 tail
= PREV_INSN (tail
);
1296 else if (GET_CODE (head
) == CODE_LABEL
)
1297 head
= NEXT_INSN (head
);
1306 /* Return nonzero if there are no real insns in the range [ HEAD, TAIL ]. */
1309 no_real_insns_p (head
, tail
)
1312 while (head
!= NEXT_INSN (tail
))
1314 if (GET_CODE (head
) != NOTE
&& GET_CODE (head
) != CODE_LABEL
)
1316 head
= NEXT_INSN (head
);
1321 /* Delete line notes from one block. Save them so they can be later restored
1322 (in restore_line_notes). HEAD and TAIL are the boundaries of the
1323 block in which notes should be processed. */
1326 rm_line_notes (head
, tail
)
1332 next_tail
= NEXT_INSN (tail
);
1333 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
1337 /* Farm out notes, and maybe save them in NOTE_LIST.
1338 This is needed to keep the debugger from
1339 getting completely deranged. */
1340 if (GET_CODE (insn
) == NOTE
)
1343 insn
= unlink_line_notes (insn
, next_tail
);
1349 if (insn
== next_tail
)
1355 /* Save line number notes for each insn in block B. HEAD and TAIL are
1356 the boundaries of the block in which notes should be processed. */
1359 save_line_notes (b
, head
, tail
)
1365 /* We must use the true line number for the first insn in the block
1366 that was computed and saved at the start of this pass. We can't
1367 use the current line number, because scheduling of the previous
1368 block may have changed the current line number. */
1370 rtx line
= line_note_head
[b
];
1373 next_tail
= NEXT_INSN (tail
);
1375 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
1376 if (GET_CODE (insn
) == NOTE
&& NOTE_LINE_NUMBER (insn
) > 0)
1379 LINE_NOTE (insn
) = line
;
1382 /* After a block was scheduled, insert line notes into the insns list.
1383 HEAD and TAIL are the boundaries of the block in which notes should
1387 restore_line_notes (head
, tail
)
1390 rtx line
, note
, prev
, new;
1391 int added_notes
= 0;
1392 rtx next_tail
, insn
;
1395 next_tail
= NEXT_INSN (tail
);
1397 /* Determine the current line-number. We want to know the current
1398 line number of the first insn of the block here, in case it is
1399 different from the true line number that was saved earlier. If
1400 different, then we need a line number note before the first insn
1401 of this block. If it happens to be the same, then we don't want to
1402 emit another line number note here. */
1403 for (line
= head
; line
; line
= PREV_INSN (line
))
1404 if (GET_CODE (line
) == NOTE
&& NOTE_LINE_NUMBER (line
) > 0)
1407 /* Walk the insns keeping track of the current line-number and inserting
1408 the line-number notes as needed. */
1409 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
1410 if (GET_CODE (insn
) == NOTE
&& NOTE_LINE_NUMBER (insn
) > 0)
1412 /* This used to emit line number notes before every non-deleted note.
1413 However, this confuses a debugger, because line notes not separated
1414 by real instructions all end up at the same address. I can find no
1415 use for line number notes before other notes, so none are emitted. */
1416 else if (GET_CODE (insn
) != NOTE
1417 && INSN_UID (insn
) < old_max_uid
1418 && (note
= LINE_NOTE (insn
)) != 0
1421 || NOTE_LINE_NUMBER (note
) != NOTE_LINE_NUMBER (line
)
1422 || NOTE_SOURCE_FILE (note
) != NOTE_SOURCE_FILE (line
)))
1425 prev
= PREV_INSN (insn
);
1426 if (LINE_NOTE (note
))
1428 /* Re-use the original line-number note. */
1429 LINE_NOTE (note
) = 0;
1430 PREV_INSN (note
) = prev
;
1431 NEXT_INSN (prev
) = note
;
1432 PREV_INSN (insn
) = note
;
1433 NEXT_INSN (note
) = insn
;
1438 new = emit_note_after (NOTE_LINE_NUMBER (note
), prev
);
1439 NOTE_SOURCE_FILE (new) = NOTE_SOURCE_FILE (note
);
1440 RTX_INTEGRATED_P (new) = RTX_INTEGRATED_P (note
);
1443 if (sched_verbose
&& added_notes
)
1444 fprintf (sched_dump
, ";; added %d line-number notes\n", added_notes
);
1447 /* After scheduling the function, delete redundant line notes from the
1451 rm_redundant_line_notes ()
1454 rtx insn
= get_insns ();
1455 int active_insn
= 0;
1458 /* Walk the insns deleting redundant line-number notes. Many of these
1459 are already present. The remainder tend to occur at basic
1460 block boundaries. */
1461 for (insn
= get_last_insn (); insn
; insn
= PREV_INSN (insn
))
1462 if (GET_CODE (insn
) == NOTE
&& NOTE_LINE_NUMBER (insn
) > 0)
1464 /* If there are no active insns following, INSN is redundant. */
1465 if (active_insn
== 0)
1468 NOTE_SOURCE_FILE (insn
) = 0;
1469 NOTE_LINE_NUMBER (insn
) = NOTE_INSN_DELETED
;
1471 /* If the line number is unchanged, LINE is redundant. */
1473 && NOTE_LINE_NUMBER (line
) == NOTE_LINE_NUMBER (insn
)
1474 && NOTE_SOURCE_FILE (line
) == NOTE_SOURCE_FILE (insn
))
1477 NOTE_SOURCE_FILE (line
) = 0;
1478 NOTE_LINE_NUMBER (line
) = NOTE_INSN_DELETED
;
1485 else if (!((GET_CODE (insn
) == NOTE
1486 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_DELETED
)
1487 || (GET_CODE (insn
) == INSN
1488 && (GET_CODE (PATTERN (insn
)) == USE
1489 || GET_CODE (PATTERN (insn
)) == CLOBBER
))))
1492 if (sched_verbose
&& notes
)
1493 fprintf (sched_dump
, ";; deleted %d line-number notes\n", notes
);
1496 /* Delete notes between HEAD and TAIL and put them in the chain
1497 of notes ended by NOTE_LIST. */
1500 rm_other_notes (head
, tail
)
1508 if (head
== tail
&& (! INSN_P (head
)))
1511 next_tail
= NEXT_INSN (tail
);
1512 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
1516 /* Farm out notes, and maybe save them in NOTE_LIST.
1517 This is needed to keep the debugger from
1518 getting completely deranged. */
1519 if (GET_CODE (insn
) == NOTE
)
1523 insn
= unlink_other_notes (insn
, next_tail
);
1529 if (insn
== next_tail
)
1535 /* Functions for computation of registers live/usage info. */
1537 /* Calculate INSN_REG_WEIGHT for all insns of a block. */
1540 find_insn_reg_weight (b
)
1543 rtx insn
, next_tail
, head
, tail
;
1545 get_block_head_tail (b
, &head
, &tail
);
1546 next_tail
= NEXT_INSN (tail
);
1548 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
1553 /* Handle register life information. */
1554 if (! INSN_P (insn
))
1557 /* Increment weight for each register born here. */
1559 if ((GET_CODE (x
) == SET
|| GET_CODE (x
) == CLOBBER
)
1560 && register_operand (SET_DEST (x
), VOIDmode
))
1562 else if (GET_CODE (x
) == PARALLEL
)
1565 for (j
= XVECLEN (x
, 0) - 1; j
>= 0; j
--)
1567 x
= XVECEXP (PATTERN (insn
), 0, j
);
1568 if ((GET_CODE (x
) == SET
|| GET_CODE (x
) == CLOBBER
)
1569 && register_operand (SET_DEST (x
), VOIDmode
))
1574 /* Decrement weight for each register that dies here. */
1575 for (x
= REG_NOTES (insn
); x
; x
= XEXP (x
, 1))
1577 if (REG_NOTE_KIND (x
) == REG_DEAD
1578 || REG_NOTE_KIND (x
) == REG_UNUSED
)
1582 INSN_REG_WEIGHT (insn
) = reg_weight
;
1586 /* Scheduling clock, modified in schedule_block() and queue_to_ready (). */
1587 static int clock_var
;
1589 /* Move insns that became ready to fire from queue to ready list. */
1592 queue_to_ready (ready
)
1593 struct ready_list
*ready
;
1598 q_ptr
= NEXT_Q (q_ptr
);
1600 /* Add all pending insns that can be scheduled without stalls to the
1602 for (link
= insn_queue
[q_ptr
]; link
; link
= XEXP (link
, 1))
1604 insn
= XEXP (link
, 0);
1607 if (sched_verbose
>= 2)
1608 fprintf (sched_dump
, ";;\t\tQ-->Ready: insn %s: ",
1609 (*current_sched_info
->print_insn
) (insn
, 0));
1611 ready_add (ready
, insn
);
1612 if (sched_verbose
>= 2)
1613 fprintf (sched_dump
, "moving to ready without stalls\n");
1615 insn_queue
[q_ptr
] = 0;
1617 /* If there are no ready insns, stall until one is ready and add all
1618 of the pending insns at that point to the ready list. */
1619 if (ready
->n_ready
== 0)
1623 for (stalls
= 1; stalls
<= MAX_INSN_QUEUE_INDEX
; stalls
++)
1625 if ((link
= insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)]))
1627 for (; link
; link
= XEXP (link
, 1))
1629 insn
= XEXP (link
, 0);
1632 if (sched_verbose
>= 2)
1633 fprintf (sched_dump
, ";;\t\tQ-->Ready: insn %s: ",
1634 (*current_sched_info
->print_insn
) (insn
, 0));
1636 ready_add (ready
, insn
);
1637 if (sched_verbose
>= 2)
1638 fprintf (sched_dump
, "moving to ready with %d stalls\n", stalls
);
1640 insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)] = 0;
1642 advance_one_cycle ();
1647 advance_one_cycle ();
1650 if ((!targetm
.sched
.use_dfa_pipeline_interface
1651 || !(*targetm
.sched
.use_dfa_pipeline_interface
) ())
1652 && sched_verbose
&& stalls
)
1653 visualize_stall_cycles (stalls
);
1655 q_ptr
= NEXT_Q_AFTER (q_ptr
, stalls
);
1656 clock_var
+= stalls
;
1660 /* Print the ready list for debugging purposes. Callable from debugger. */
1663 debug_ready_list (ready
)
1664 struct ready_list
*ready
;
1669 if (ready
->n_ready
== 0)
1671 fprintf (sched_dump
, "\n");
1675 p
= ready_lastpos (ready
);
1676 for (i
= 0; i
< ready
->n_ready
; i
++)
1677 fprintf (sched_dump
, " %s", (*current_sched_info
->print_insn
) (p
[i
], 0));
1678 fprintf (sched_dump
, "\n");
1681 /* move_insn1: Remove INSN from insn chain, and link it after LAST insn. */
1684 move_insn1 (insn
, last
)
1687 NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
1688 PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
1690 NEXT_INSN (insn
) = NEXT_INSN (last
);
1691 PREV_INSN (NEXT_INSN (last
)) = insn
;
1693 NEXT_INSN (last
) = insn
;
1694 PREV_INSN (insn
) = last
;
1699 /* Search INSN for REG_SAVE_NOTE note pairs for
1700 NOTE_INSN_{LOOP,EHREGION}_{BEG,END}; and convert them back into
1701 NOTEs. The REG_SAVE_NOTE note following first one is contains the
1702 saved value for NOTE_BLOCK_NUMBER which is useful for
1703 NOTE_INSN_EH_REGION_{BEG,END} NOTEs. LAST is the last instruction
1704 output by the instruction scheduler. Return the new value of LAST. */
1707 reemit_notes (insn
, last
)
1714 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1716 if (REG_NOTE_KIND (note
) == REG_SAVE_NOTE
)
1718 enum insn_note note_type
= INTVAL (XEXP (note
, 0));
1720 last
= emit_note_before (note_type
, last
);
1721 remove_note (insn
, note
);
1722 note
= XEXP (note
, 1);
1723 if (note_type
== NOTE_INSN_EH_REGION_BEG
1724 || note_type
== NOTE_INSN_EH_REGION_END
)
1725 NOTE_EH_HANDLER (last
) = INTVAL (XEXP (note
, 0));
1726 remove_note (insn
, note
);
1732 /* Move INSN, and all insns which should be issued before it,
1733 due to SCHED_GROUP_P flag. Reemit notes if needed.
1735 Return the last insn emitted by the scheduler, which is the
1736 return value from the first call to reemit_notes. */
1739 move_insn (insn
, last
)
1744 /* If INSN has SCHED_GROUP_P set, then issue it and any other
1745 insns with SCHED_GROUP_P set first. */
1746 while (SCHED_GROUP_P (insn
))
1748 rtx prev
= PREV_INSN (insn
);
1750 /* Move a SCHED_GROUP_P insn. */
1751 move_insn1 (insn
, last
);
1752 /* If this is the first call to reemit_notes, then record
1753 its return value. */
1754 if (retval
== NULL_RTX
)
1755 retval
= reemit_notes (insn
, insn
);
1757 reemit_notes (insn
, insn
);
1758 /* Consume SCHED_GROUP_P flag. */
1759 SCHED_GROUP_P (insn
) = 0;
1763 /* Now move the first non SCHED_GROUP_P insn. */
1764 move_insn1 (insn
, last
);
1766 /* If this is the first call to reemit_notes, then record
1767 its return value. */
1768 if (retval
== NULL_RTX
)
1769 retval
= reemit_notes (insn
, insn
);
1771 reemit_notes (insn
, insn
);
1776 /* The following function returns maximal (or close to maximal) number
1777 of insns which can be issued on the same cycle and one of which
1778 insns is insns with the best rank (the last insn in READY). To
1779 make this function tries different samples of ready insns. READY
1780 is current queue `ready'. Global array READY_TRY reflects what
1781 insns are already issued in this try. STATE is current processor
1782 state. If the function returns nonzero, INDEX will contain index
1783 of the best insn in READY. The following function is used only for
1784 first cycle multipass scheduling. */
1787 max_issue (ready
, state
, index
)
1788 struct ready_list
*ready
;
1792 int i
, best
, n
, temp_index
, delay
;
1795 int max_lookahead
= (*targetm
.sched
.first_cycle_multipass_dfa_lookahead
) ();
1797 if (state_dead_lock_p (state
))
1800 temp_state
= alloca (dfa_state_size
);
1803 for (i
= 0; i
< ready
->n_ready
; i
++)
1806 insn
= ready_element (ready
, i
);
1808 if (INSN_CODE (insn
) < 0)
1811 memcpy (temp_state
, state
, dfa_state_size
);
1813 delay
= state_transition (temp_state
, insn
);
1817 if (!targetm
.sched
.dfa_bubble
)
1825 (bubble
= (*targetm
.sched
.dfa_bubble
) (j
)) != NULL_RTX
;
1827 if (state_transition (temp_state
, bubble
) < 0
1828 && state_transition (temp_state
, insn
) < 0)
1831 if (bubble
== NULL_RTX
)
1840 if (max_lookahead
< 0)
1845 n
= max_issue (ready
, temp_state
, &temp_index
);
1846 if (n
> 0 || ready_try
[0])
1860 /* The following function chooses insn from READY and modifies
1861 *N_READY and READY. The following function is used only for first
1862 cycle multipass scheduling. */
1865 choose_ready (ready
)
1866 struct ready_list
*ready
;
1868 if (!targetm
.sched
.first_cycle_multipass_dfa_lookahead
1869 || (*targetm
.sched
.first_cycle_multipass_dfa_lookahead
) () <= 0)
1870 return ready_remove_first (ready
);
1873 /* Try to choose the better insn. */
1876 if (max_issue (ready
, curr_state
, &index
) == 0)
1877 return ready_remove_first (ready
);
1879 return ready_remove (ready
, index
);
1883 /* Called from backends from targetm.sched.reorder to emit stuff into
1884 the instruction stream. */
1887 sched_emit_insn (pat
)
1890 rtx insn
= emit_insn_after (pat
, last_scheduled_insn
);
1891 last_scheduled_insn
= insn
;
1895 /* Use forward list scheduling to rearrange insns of block B in region RGN,
1896 possibly bringing insns from subsequent blocks in the same region. */
1899 schedule_block (b
, rgn_n_insns
)
1903 struct ready_list ready
;
1904 int first_cycle_insn_p
;
1906 state_t temp_state
= NULL
; /* It is used for multipass scheduling. */
1908 /* Head/tail info for this block. */
1909 rtx prev_head
= current_sched_info
->prev_head
;
1910 rtx next_tail
= current_sched_info
->next_tail
;
1911 rtx head
= NEXT_INSN (prev_head
);
1912 rtx tail
= PREV_INSN (next_tail
);
1914 /* We used to have code to avoid getting parameters moved from hard
1915 argument registers into pseudos.
1917 However, it was removed when it proved to be of marginal benefit
1918 and caused problems because schedule_block and compute_forward_dependences
1919 had different notions of what the "head" insn was. */
1921 if (head
== tail
&& (! INSN_P (head
)))
1927 fprintf (sched_dump
, ";; ======================================================\n");
1928 fprintf (sched_dump
,
1929 ";; -- basic block %d from %d to %d -- %s reload\n",
1930 b
, INSN_UID (head
), INSN_UID (tail
),
1931 (reload_completed
? "after" : "before"));
1932 fprintf (sched_dump
, ";; ======================================================\n");
1933 fprintf (sched_dump
, "\n");
1936 init_block_visualization ();
1939 if (targetm
.sched
.use_dfa_pipeline_interface
1940 && (*targetm
.sched
.use_dfa_pipeline_interface
) ())
1941 state_reset (curr_state
);
1945 /* Allocate the ready list. */
1946 ready
.veclen
= rgn_n_insns
+ 1 + issue_rate
;
1947 ready
.first
= ready
.veclen
- 1;
1948 ready
.vec
= (rtx
*) xmalloc (ready
.veclen
* sizeof (rtx
));
1951 if (targetm
.sched
.use_dfa_pipeline_interface
1952 && (*targetm
.sched
.use_dfa_pipeline_interface
) ())
1954 /* It is used for first cycle multipass scheduling. */
1955 temp_state
= alloca (dfa_state_size
);
1956 ready_try
= (char *) xmalloc ((rgn_n_insns
+ 1) * sizeof (char));
1957 memset (ready_try
, 0, (rgn_n_insns
+ 1) * sizeof (char));
1960 (*current_sched_info
->init_ready_list
) (&ready
);
1962 if (targetm
.sched
.md_init
)
1963 (*targetm
.sched
.md_init
) (sched_dump
, sched_verbose
, ready
.veclen
);
1965 /* We start inserting insns after PREV_HEAD. */
1966 last_scheduled_insn
= prev_head
;
1968 /* Initialize INSN_QUEUE. Q_SIZE is the total number of insns in the
1973 if (!targetm
.sched
.use_dfa_pipeline_interface
1974 || !(*targetm
.sched
.use_dfa_pipeline_interface
) ())
1975 max_insn_queue_index_macro_value
= INSN_QUEUE_SIZE
- 1;
1977 max_insn_queue_index_macro_value
= max_insn_queue_index
;
1979 insn_queue
= (rtx
*) alloca ((MAX_INSN_QUEUE_INDEX
+ 1) * sizeof (rtx
));
1980 memset ((char *) insn_queue
, 0, (MAX_INSN_QUEUE_INDEX
+ 1) * sizeof (rtx
));
1981 last_clock_var
= -1;
1983 /* Start just before the beginning of time. */
1986 /* Loop until all the insns in BB are scheduled. */
1987 while ((*current_sched_info
->schedule_more_p
) ())
1991 advance_one_cycle ();
1993 /* Add to the ready list all pending insns that can be issued now.
1994 If there are no ready insns, increment clock until one
1995 is ready and add all pending insns at that point to the ready
1997 queue_to_ready (&ready
);
1999 if (ready
.n_ready
== 0)
2002 if (sched_verbose
>= 2)
2004 fprintf (sched_dump
, ";;\t\tReady list after queue_to_ready: ");
2005 debug_ready_list (&ready
);
2008 /* Sort the ready list based on priority. */
2009 ready_sort (&ready
);
2011 /* Allow the target to reorder the list, typically for
2012 better instruction bundling. */
2013 if (targetm
.sched
.reorder
)
2015 (*targetm
.sched
.reorder
) (sched_dump
, sched_verbose
,
2016 ready_lastpos (&ready
),
2017 &ready
.n_ready
, clock_var
);
2019 can_issue_more
= issue_rate
;
2021 first_cycle_insn_p
= 1;
2027 if (sched_verbose
>= 2)
2029 fprintf (sched_dump
, ";;\tReady list (t =%3d): ",
2031 debug_ready_list (&ready
);
2034 if (!targetm
.sched
.use_dfa_pipeline_interface
2035 || !(*targetm
.sched
.use_dfa_pipeline_interface
) ())
2037 if (ready
.n_ready
== 0 || !can_issue_more
2038 || !(*current_sched_info
->schedule_more_p
) ())
2040 insn
= choose_ready (&ready
);
2041 cost
= actual_hazard (insn_unit (insn
), insn
, clock_var
, 0);
2045 if (ready
.n_ready
== 0 || !can_issue_more
2046 || state_dead_lock_p (curr_state
)
2047 || !(*current_sched_info
->schedule_more_p
) ())
2050 /* Select and remove the insn from the ready list. */
2051 insn
= choose_ready (&ready
);
2053 memcpy (temp_state
, curr_state
, dfa_state_size
);
2054 if (recog_memoized (insn
) < 0)
2056 if (!first_cycle_insn_p
2057 && (GET_CODE (PATTERN (insn
)) == ASM_INPUT
2058 || asm_noperands (PATTERN (insn
)) >= 0))
2059 /* This is asm insn which is tryed to be issued on the
2060 cycle not first. Issue it on the next cycle. */
2063 /* A USE insn, or something else we don't need to
2064 understand. We can't pass these directly to
2065 state_transition because it will trigger a
2066 fatal error for unrecognizable insns. */
2071 cost
= state_transition (temp_state
, insn
);
2073 if (targetm
.sched
.first_cycle_multipass_dfa_lookahead
2074 && targetm
.sched
.dfa_bubble
)
2082 (bubble
= (*targetm
.sched
.dfa_bubble
) (j
))
2086 memcpy (temp_state
, curr_state
, dfa_state_size
);
2088 if (state_transition (temp_state
, bubble
) < 0
2089 && state_transition (temp_state
, insn
) < 0)
2093 if (bubble
!= NULL_RTX
)
2095 if (insert_schedule_bubbles_p
)
2099 copy
= copy_rtx (PATTERN (bubble
));
2100 emit_insn_after (copy
, last_scheduled_insn
);
2102 = NEXT_INSN (last_scheduled_insn
);
2103 INSN_CODE (last_scheduled_insn
)
2104 = INSN_CODE (bubble
);
2106 /* Annotate the same for the first insns
2107 scheduling by using mode. */
2108 PUT_MODE (last_scheduled_insn
,
2109 (clock_var
> last_clock_var
2110 ? clock_var
- last_clock_var
2112 last_clock_var
= clock_var
;
2114 if (sched_verbose
>= 2)
2116 fprintf (sched_dump
,
2117 ";;\t\t--> scheduling bubble insn <<<%d>>>:reservation ",
2118 INSN_UID (last_scheduled_insn
));
2120 if (recog_memoized (last_scheduled_insn
)
2122 fprintf (sched_dump
, "nothing");
2125 (sched_dump
, last_scheduled_insn
);
2127 fprintf (sched_dump
, "\n");
2145 queue_insn (insn
, cost
);
2149 if (! (*current_sched_info
->can_schedule_ready_p
) (insn
))
2152 last_scheduled_insn
= move_insn (insn
, last_scheduled_insn
);
2154 if (targetm
.sched
.use_dfa_pipeline_interface
2155 && (*targetm
.sched
.use_dfa_pipeline_interface
) ())
2156 memcpy (curr_state
, temp_state
, dfa_state_size
);
2158 if (targetm
.sched
.variable_issue
)
2160 (*targetm
.sched
.variable_issue
) (sched_dump
, sched_verbose
,
2161 insn
, can_issue_more
);
2162 /* A naked CLOBBER or USE generates no instruction, so do
2163 not count them against the issue rate. */
2164 else if (GET_CODE (PATTERN (insn
)) != USE
2165 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
2168 schedule_insn (insn
, &ready
, clock_var
);
2171 first_cycle_insn_p
= 0;
2173 if (targetm
.sched
.reorder2
)
2175 /* Sort the ready list based on priority. */
2176 if (ready
.n_ready
> 0)
2177 ready_sort (&ready
);
2179 (*targetm
.sched
.reorder2
) (sched_dump
,sched_verbose
,
2181 ? ready_lastpos (&ready
) : NULL
,
2182 &ready
.n_ready
, clock_var
);
2186 if ((!targetm
.sched
.use_dfa_pipeline_interface
2187 || !(*targetm
.sched
.use_dfa_pipeline_interface
) ())
2190 visualize_scheduled_insns (clock_var
);
2193 if (targetm
.sched
.md_finish
)
2194 (*targetm
.sched
.md_finish
) (sched_dump
, sched_verbose
);
2199 fprintf (sched_dump
, ";;\tReady list (final): ");
2200 debug_ready_list (&ready
);
2201 if (!targetm
.sched
.use_dfa_pipeline_interface
2202 || !(*targetm
.sched
.use_dfa_pipeline_interface
) ())
2203 print_block_visualization ("");
2206 /* Sanity check -- queue must be empty now. Meaningless if region has
2208 if (current_sched_info
->queue_must_finish_empty
&& q_size
!= 0)
2211 /* Update head/tail boundaries. */
2212 head
= NEXT_INSN (prev_head
);
2213 tail
= last_scheduled_insn
;
2215 /* Restore-other-notes: NOTE_LIST is the end of a chain of notes
2216 previously found among the insns. Insert them at the beginning
2220 rtx note_head
= note_list
;
2222 while (PREV_INSN (note_head
))
2224 note_head
= PREV_INSN (note_head
);
2227 PREV_INSN (note_head
) = PREV_INSN (head
);
2228 NEXT_INSN (PREV_INSN (head
)) = note_head
;
2229 PREV_INSN (head
) = note_list
;
2230 NEXT_INSN (note_list
) = head
;
2237 fprintf (sched_dump
, ";; total time = %d\n;; new head = %d\n",
2238 clock_var
, INSN_UID (head
));
2239 fprintf (sched_dump
, ";; new tail = %d\n\n",
2244 current_sched_info
->head
= head
;
2245 current_sched_info
->tail
= tail
;
2249 if (targetm
.sched
.use_dfa_pipeline_interface
2250 && (*targetm
.sched
.use_dfa_pipeline_interface
) ())
2254 /* Set_priorities: compute priority of each insn in the block. */
2257 set_priorities (head
, tail
)
2265 prev_head
= PREV_INSN (head
);
2267 if (head
== tail
&& (! INSN_P (head
)))
2271 for (insn
= tail
; insn
!= prev_head
; insn
= PREV_INSN (insn
))
2273 if (GET_CODE (insn
) == NOTE
)
2276 if (!(SCHED_GROUP_P (insn
)))
2278 (void) priority (insn
);
2284 /* Initialize some global state for the scheduler. DUMP_FILE is to be used
2285 for debugging output. */
2288 sched_init (dump_file
)
2296 /* Disable speculative loads in their presence if cc0 defined. */
2298 flag_schedule_speculative_load
= 0;
2301 /* Set dump and sched_verbose for the desired debugging output. If no
2302 dump-file was specified, but -fsched-verbose=N (any N), print to stderr.
2303 For -fsched-verbose=N, N>=10, print everything to stderr. */
2304 sched_verbose
= sched_verbose_param
;
2305 if (sched_verbose_param
== 0 && dump_file
)
2307 sched_dump
= ((sched_verbose_param
>= 10 || !dump_file
)
2308 ? stderr
: dump_file
);
2310 /* Initialize issue_rate. */
2311 if (targetm
.sched
.issue_rate
)
2312 issue_rate
= (*targetm
.sched
.issue_rate
) ();
2316 /* We use LUID 0 for the fake insn (UID 0) which holds dependencies for
2317 pseudos which do not cross calls. */
2318 old_max_uid
= get_max_uid () + 1;
2320 h_i_d
= (struct haifa_insn_data
*) xcalloc (old_max_uid
, sizeof (*h_i_d
));
2322 for (i
= 0; i
< old_max_uid
; i
++)
2323 h_i_d
[i
].cost
= -1;
2325 if (targetm
.sched
.use_dfa_pipeline_interface
2326 && (*targetm
.sched
.use_dfa_pipeline_interface
) ())
2328 if (targetm
.sched
.init_dfa_pre_cycle_insn
)
2329 (*targetm
.sched
.init_dfa_pre_cycle_insn
) ();
2331 if (targetm
.sched
.init_dfa_post_cycle_insn
)
2332 (*targetm
.sched
.init_dfa_post_cycle_insn
) ();
2334 if (targetm
.sched
.first_cycle_multipass_dfa_lookahead
2335 && targetm
.sched
.init_dfa_bubbles
)
2336 (*targetm
.sched
.init_dfa_bubbles
) ();
2339 dfa_state_size
= state_size ();
2340 curr_state
= xmalloc (dfa_state_size
);
2346 for (insn
= b
->head
;; insn
= NEXT_INSN (insn
))
2348 INSN_LUID (insn
) = luid
;
2350 /* Increment the next luid, unless this is a note. We don't
2351 really need separate IDs for notes and we don't want to
2352 schedule differently depending on whether or not there are
2353 line-number notes, i.e., depending on whether or not we're
2354 generating debugging information. */
2355 if (GET_CODE (insn
) != NOTE
)
2362 init_dependency_caches (luid
);
2364 init_alias_analysis ();
2366 if (write_symbols
!= NO_DEBUG
)
2370 line_note_head
= (rtx
*) xcalloc (last_basic_block
, sizeof (rtx
));
2372 /* Save-line-note-head:
2373 Determine the line-number at the start of each basic block.
2374 This must be computed and saved now, because after a basic block's
2375 predecessor has been scheduled, it is impossible to accurately
2376 determine the correct line number for the first insn of the block. */
2380 for (line
= b
->head
; line
; line
= PREV_INSN (line
))
2381 if (GET_CODE (line
) == NOTE
&& NOTE_LINE_NUMBER (line
) > 0)
2383 line_note_head
[b
->index
] = line
;
2386 /* Do a forward search as well, since we won't get to see the first
2387 notes in a basic block. */
2388 for (line
= b
->head
; line
; line
= NEXT_INSN (line
))
2392 if (GET_CODE (line
) == NOTE
&& NOTE_LINE_NUMBER (line
) > 0)
2393 line_note_head
[b
->index
] = line
;
2398 if ((!targetm
.sched
.use_dfa_pipeline_interface
2399 || !(*targetm
.sched
.use_dfa_pipeline_interface
) ())
2401 /* Find units used in this function, for visualization. */
2402 init_target_units ();
2404 /* ??? Add a NOTE after the last insn of the last basic block. It is not
2405 known why this is done. */
2407 insn
= EXIT_BLOCK_PTR
->prev_bb
->end
;
2408 if (NEXT_INSN (insn
) == 0
2409 || (GET_CODE (insn
) != NOTE
2410 && GET_CODE (insn
) != CODE_LABEL
2411 /* Don't emit a NOTE if it would end up before a BARRIER. */
2412 && GET_CODE (NEXT_INSN (insn
)) != BARRIER
))
2414 emit_note_after (NOTE_INSN_DELETED
, EXIT_BLOCK_PTR
->prev_bb
->end
);
2415 /* Make insn to appear outside BB. */
2416 EXIT_BLOCK_PTR
->prev_bb
->end
= PREV_INSN (EXIT_BLOCK_PTR
->prev_bb
->end
);
2419 /* Compute INSN_REG_WEIGHT for all blocks. We must do this before
2420 removing death notes. */
2421 FOR_EACH_BB_REVERSE (b
)
2422 find_insn_reg_weight (b
->index
);
2425 /* Free global data used during insn scheduling. */
2432 if (targetm
.sched
.use_dfa_pipeline_interface
2433 && (*targetm
.sched
.use_dfa_pipeline_interface
) ())
2438 free_dependency_caches ();
2439 end_alias_analysis ();
2440 if (write_symbols
!= NO_DEBUG
)
2441 free (line_note_head
);
2443 #endif /* INSN_SCHEDULING */