1 /* Instruction scheduling pass.
2 Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000, 2001 Free Software Foundation, Inc.
4 Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
5 and currently maintained by, Jim Wilson (wilson@cygnus.com)
7 This file is part of 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 /* sched-verbose controls the amount of debugging output the
162 scheduler prints. It is controlled by -fsched-verbose=N:
163 N>0 and no -DSR : the output is directed to stderr.
164 N>=10 will direct the printouts to stderr (regardless of -dSR).
166 N=2: bb's probabilities, detailed ready list info, unit/insn info.
167 N=3: rtl at abort point, control-flow, regions info.
168 N=5: dependences info. */
170 static int sched_verbose_param
= 0;
171 int sched_verbose
= 0;
173 /* Debugging file. All printouts are sent to dump, which is always set,
174 either to stderr, or to the dump listing file (-dRS). */
175 FILE *sched_dump
= 0;
177 /* Highest uid before scheduling. */
178 static int old_max_uid
;
180 /* fix_sched_param() is called from toplev.c upon detection
181 of the -fsched-verbose=N option. */
184 fix_sched_param (param
, val
)
185 const char *param
, *val
;
187 if (!strcmp (param
, "verbose"))
188 sched_verbose_param
= atoi (val
);
190 warning ("fix_sched_param: unknown param: %s", param
);
193 struct haifa_insn_data
*h_i_d
;
195 #define DONE_PRIORITY -1
196 #define MAX_PRIORITY 0x7fffffff
197 #define TAIL_PRIORITY 0x7ffffffe
198 #define LAUNCH_PRIORITY 0x7f000001
199 #define DONE_PRIORITY_P(INSN) (INSN_PRIORITY (INSN) < 0)
200 #define LOW_PRIORITY_P(INSN) ((INSN_PRIORITY (INSN) & 0x7f000000) == 0)
202 #define LINE_NOTE(INSN) (h_i_d[INSN_UID (INSN)].line_note)
203 #define INSN_TICK(INSN) (h_i_d[INSN_UID (INSN)].tick)
205 /* Vector indexed by basic block number giving the starting line-number
206 for each basic block. */
207 static rtx
*line_note_head
;
209 /* List of important notes we must keep around. This is a pointer to the
210 last element in the list. */
211 static rtx note_list
;
215 /* An instruction is ready to be scheduled when all insns preceding it
216 have already been scheduled. It is important to ensure that all
217 insns which use its result will not be executed until its result
218 has been computed. An insn is maintained in one of four structures:
220 (P) the "Pending" set of insns which cannot be scheduled until
221 their dependencies have been satisfied.
222 (Q) the "Queued" set of insns that can be scheduled when sufficient
224 (R) the "Ready" list of unscheduled, uncommitted insns.
225 (S) the "Scheduled" list of insns.
227 Initially, all insns are either "Pending" or "Ready" depending on
228 whether their dependencies are satisfied.
230 Insns move from the "Ready" list to the "Scheduled" list as they
231 are committed to the schedule. As this occurs, the insns in the
232 "Pending" list have their dependencies satisfied and move to either
233 the "Ready" list or the "Queued" set depending on whether
234 sufficient time has passed to make them ready. As time passes,
235 insns move from the "Queued" set to the "Ready" list. Insns may
236 move from the "Ready" list to the "Queued" set if they are blocked
237 due to a function unit conflict.
239 The "Pending" list (P) are the insns in the INSN_DEPEND of the unscheduled
240 insns, i.e., those that are ready, queued, and pending.
241 The "Queued" set (Q) is implemented by the variable `insn_queue'.
242 The "Ready" list (R) is implemented by the variables `ready' and
244 The "Scheduled" list (S) is the new insn chain built by this pass.
246 The transition (R->S) is implemented in the scheduling loop in
247 `schedule_block' when the best insn to schedule is chosen.
248 The transition (R->Q) is implemented in `queue_insn' when an
249 insn is found to have a function unit conflict with the already
251 The transitions (P->R and P->Q) are implemented in `schedule_insn' as
252 insns move from the ready list to the scheduled list.
253 The transition (Q->R) is implemented in 'queue_to_insn' as time
254 passes or stalls are introduced. */
256 /* Implement a circular buffer to delay instructions until sufficient
257 time has passed. INSN_QUEUE_SIZE is a power of two larger than
258 MAX_BLOCKAGE and MAX_READY_COST computed by genattr.c. This is the
259 longest time an isnsn may be queued. */
260 static rtx insn_queue
[INSN_QUEUE_SIZE
];
261 static int q_ptr
= 0;
262 static int q_size
= 0;
263 #define NEXT_Q(X) (((X)+1) & (INSN_QUEUE_SIZE-1))
264 #define NEXT_Q_AFTER(X, C) (((X)+C) & (INSN_QUEUE_SIZE-1))
266 /* Describe the ready list of the scheduler.
267 VEC holds space enough for all insns in the current region. VECLEN
268 says how many exactly.
269 FIRST is the index of the element with the highest priority; i.e. the
270 last one in the ready list, since elements are ordered by ascending
272 N_READY determines how many insns are on the ready list. */
282 /* Forward declarations. */
283 static unsigned int blockage_range
PARAMS ((int, rtx
));
284 static void clear_units
PARAMS ((void));
285 static void schedule_unit
PARAMS ((int, rtx
, int));
286 static int actual_hazard
PARAMS ((int, rtx
, int, int));
287 static int potential_hazard
PARAMS ((int, rtx
, int));
288 static int priority
PARAMS ((rtx
));
289 static int rank_for_schedule
PARAMS ((const PTR
, const PTR
));
290 static void swap_sort
PARAMS ((rtx
*, int));
291 static void queue_insn
PARAMS ((rtx
, int));
292 static void schedule_insn
PARAMS ((rtx
, struct ready_list
*, int));
293 static void find_insn_reg_weight
PARAMS ((int));
294 static void adjust_priority
PARAMS ((rtx
));
296 /* Notes handling mechanism:
297 =========================
298 Generally, NOTES are saved before scheduling and restored after scheduling.
299 The scheduler distinguishes between three types of notes:
301 (1) LINE_NUMBER notes, generated and used for debugging. Here,
302 before scheduling a region, a pointer to the LINE_NUMBER note is
303 added to the insn following it (in save_line_notes()), and the note
304 is removed (in rm_line_notes() and unlink_line_notes()). After
305 scheduling the region, this pointer is used for regeneration of
306 the LINE_NUMBER note (in restore_line_notes()).
308 (2) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes:
309 Before scheduling a region, a pointer to the note is added to the insn
310 that follows or precedes it. (This happens as part of the data dependence
311 computation). After scheduling an insn, the pointer contained in it is
312 used for regenerating the corresponding note (in reemit_notes).
314 (3) All other notes (e.g. INSN_DELETED): Before scheduling a block,
315 these notes are put in a list (in rm_other_notes() and
316 unlink_other_notes ()). After scheduling the block, these notes are
317 inserted at the beginning of the block (in schedule_block()). */
319 static rtx unlink_other_notes
PARAMS ((rtx
, rtx
));
320 static rtx unlink_line_notes
PARAMS ((rtx
, rtx
));
321 static rtx reemit_notes
PARAMS ((rtx
, rtx
));
322 static rtx reemit_other_notes
PARAMS ((rtx
, rtx
));
324 static rtx
*ready_lastpos
PARAMS ((struct ready_list
*));
325 static void ready_sort
PARAMS ((struct ready_list
*));
326 static rtx ready_remove_first
PARAMS ((struct ready_list
*));
328 static void queue_to_ready
PARAMS ((struct ready_list
*));
330 static void debug_ready_list
PARAMS ((struct ready_list
*));
332 static rtx move_insn1
PARAMS ((rtx
, rtx
));
333 static rtx move_insn
PARAMS ((rtx
, rtx
));
335 #endif /* INSN_SCHEDULING */
337 /* Point to state used for the current scheduling pass. */
338 struct sched_info
*current_sched_info
;
340 #ifndef INSN_SCHEDULING
342 schedule_insns (dump_file
)
343 FILE *dump_file ATTRIBUTE_UNUSED
;
348 /* Pointer to the last instruction scheduled. Used by rank_for_schedule,
349 so that insns independent of the last scheduled insn will be preferred
350 over dependent instructions. */
352 static rtx last_scheduled_insn
;
354 /* Compute the function units used by INSN. This caches the value
355 returned by function_units_used. A function unit is encoded as the
356 unit number if the value is non-negative and the compliment of a
357 mask if the value is negative. A function unit index is the
358 non-negative encoding. */
364 int unit
= INSN_UNIT (insn
);
368 recog_memoized (insn
);
370 /* A USE insn, or something else we don't need to understand.
371 We can't pass these directly to function_units_used because it will
372 trigger a fatal error for unrecognizable insns. */
373 if (INSN_CODE (insn
) < 0)
377 unit
= function_units_used (insn
);
378 /* Increment non-negative values so we can cache zero. */
382 /* We only cache 16 bits of the result, so if the value is out of
383 range, don't cache it. */
384 if (FUNCTION_UNITS_SIZE
< HOST_BITS_PER_SHORT
386 || (unit
& ~((1 << (HOST_BITS_PER_SHORT
- 1)) - 1)) == 0)
387 INSN_UNIT (insn
) = unit
;
389 return (unit
> 0 ? unit
- 1 : unit
);
392 /* Compute the blockage range for executing INSN on UNIT. This caches
393 the value returned by the blockage_range_function for the unit.
394 These values are encoded in an int where the upper half gives the
395 minimum value and the lower half gives the maximum value. */
397 HAIFA_INLINE
static unsigned int
398 blockage_range (unit
, insn
)
402 unsigned int blockage
= INSN_BLOCKAGE (insn
);
405 if ((int) UNIT_BLOCKED (blockage
) != unit
+ 1)
407 range
= function_units
[unit
].blockage_range_function (insn
);
408 /* We only cache the blockage range for one unit and then only if
410 if (HOST_BITS_PER_INT
>= UNIT_BITS
+ 2 * BLOCKAGE_BITS
)
411 INSN_BLOCKAGE (insn
) = ENCODE_BLOCKAGE (unit
+ 1, range
);
414 range
= BLOCKAGE_RANGE (blockage
);
419 /* A vector indexed by function unit instance giving the last insn to use
420 the unit. The value of the function unit instance index for unit U
421 instance I is (U + I * FUNCTION_UNITS_SIZE). */
422 static rtx unit_last_insn
[FUNCTION_UNITS_SIZE
* MAX_MULTIPLICITY
];
424 /* A vector indexed by function unit instance giving the minimum time when
425 the unit will unblock based on the maximum blockage cost. */
426 static int unit_tick
[FUNCTION_UNITS_SIZE
* MAX_MULTIPLICITY
];
428 /* A vector indexed by function unit number giving the number of insns
429 that remain to use the unit. */
430 static int unit_n_insns
[FUNCTION_UNITS_SIZE
];
432 /* Access the unit_last_insn array. Used by the visualization code. */
435 get_unit_last_insn (instance
)
438 return unit_last_insn
[instance
];
441 /* Reset the function unit state to the null state. */
446 memset ((char *) unit_last_insn
, 0, sizeof (unit_last_insn
));
447 memset ((char *) unit_tick
, 0, sizeof (unit_tick
));
448 memset ((char *) unit_n_insns
, 0, sizeof (unit_n_insns
));
451 /* Return the issue-delay of an insn. */
454 insn_issue_delay (insn
)
458 int unit
= insn_unit (insn
);
460 /* Efficiency note: in fact, we are working 'hard' to compute a
461 value that was available in md file, and is not available in
462 function_units[] structure. It would be nice to have this
466 if (function_units
[unit
].blockage_range_function
&&
467 function_units
[unit
].blockage_function
)
468 delay
= function_units
[unit
].blockage_function (insn
, insn
);
471 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
472 if ((unit
& 1) != 0 && function_units
[i
].blockage_range_function
473 && function_units
[i
].blockage_function
)
474 delay
= MAX (delay
, function_units
[i
].blockage_function (insn
, insn
));
479 /* Return the actual hazard cost of executing INSN on the unit UNIT,
480 instance INSTANCE at time CLOCK if the previous actual hazard cost
484 actual_hazard_this_instance (unit
, instance
, insn
, clock
, cost
)
485 int unit
, instance
, clock
, cost
;
488 int tick
= unit_tick
[instance
]; /* Issue time of the last issued insn. */
490 if (tick
- clock
> cost
)
492 /* The scheduler is operating forward, so unit's last insn is the
493 executing insn and INSN is the candidate insn. We want a
494 more exact measure of the blockage if we execute INSN at CLOCK
495 given when we committed the execution of the unit's last insn.
497 The blockage value is given by either the unit's max blockage
498 constant, blockage range function, or blockage function. Use
499 the most exact form for the given unit. */
501 if (function_units
[unit
].blockage_range_function
)
503 if (function_units
[unit
].blockage_function
)
504 tick
+= (function_units
[unit
].blockage_function
505 (unit_last_insn
[instance
], insn
)
506 - function_units
[unit
].max_blockage
);
508 tick
+= ((int) MAX_BLOCKAGE_COST (blockage_range (unit
, insn
))
509 - function_units
[unit
].max_blockage
);
511 if (tick
- clock
> cost
)
517 /* Record INSN as having begun execution on the units encoded by UNIT at
520 HAIFA_INLINE
static void
521 schedule_unit (unit
, insn
, clock
)
530 #if MAX_MULTIPLICITY > 1
531 /* Find the first free instance of the function unit and use that
532 one. We assume that one is free. */
533 for (i
= function_units
[unit
].multiplicity
- 1; i
> 0; i
--)
535 if (!actual_hazard_this_instance (unit
, instance
, insn
, clock
, 0))
537 instance
+= FUNCTION_UNITS_SIZE
;
540 unit_last_insn
[instance
] = insn
;
541 unit_tick
[instance
] = (clock
+ function_units
[unit
].max_blockage
);
544 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
546 schedule_unit (i
, insn
, clock
);
549 /* Return the actual hazard cost of executing INSN on the units encoded by
550 UNIT at time CLOCK if the previous actual hazard cost was COST. */
552 HAIFA_INLINE
static int
553 actual_hazard (unit
, insn
, clock
, cost
)
554 int unit
, clock
, cost
;
561 /* Find the instance of the function unit with the minimum hazard. */
563 int best_cost
= actual_hazard_this_instance (unit
, instance
, insn
,
565 #if MAX_MULTIPLICITY > 1
568 if (best_cost
> cost
)
570 for (i
= function_units
[unit
].multiplicity
- 1; i
> 0; i
--)
572 instance
+= FUNCTION_UNITS_SIZE
;
573 this_cost
= actual_hazard_this_instance (unit
, instance
, insn
,
575 if (this_cost
< best_cost
)
577 best_cost
= this_cost
;
578 if (this_cost
<= cost
)
584 cost
= MAX (cost
, best_cost
);
587 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
589 cost
= actual_hazard (i
, insn
, clock
, cost
);
594 /* Return the potential hazard cost of executing an instruction on the
595 units encoded by UNIT if the previous potential hazard cost was COST.
596 An insn with a large blockage time is chosen in preference to one
597 with a smaller time; an insn that uses a unit that is more likely
598 to be used is chosen in preference to one with a unit that is less
599 used. We are trying to minimize a subsequent actual hazard. */
601 HAIFA_INLINE
static int
602 potential_hazard (unit
, insn
, cost
)
607 unsigned int minb
, maxb
;
611 minb
= maxb
= function_units
[unit
].max_blockage
;
614 if (function_units
[unit
].blockage_range_function
)
616 maxb
= minb
= blockage_range (unit
, insn
);
617 maxb
= MAX_BLOCKAGE_COST (maxb
);
618 minb
= MIN_BLOCKAGE_COST (minb
);
623 /* Make the number of instructions left dominate. Make the
624 minimum delay dominate the maximum delay. If all these
625 are the same, use the unit number to add an arbitrary
626 ordering. Other terms can be added. */
627 ncost
= minb
* 0x40 + maxb
;
628 ncost
*= (unit_n_insns
[unit
] - 1) * 0x1000 + unit
;
635 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
637 cost
= potential_hazard (i
, insn
, cost
);
642 /* Compute cost of executing INSN given the dependence LINK on the insn USED.
643 This is the number of cycles between instruction issue and
644 instruction results. */
647 insn_cost (insn
, link
, used
)
648 rtx insn
, link
, used
;
650 int cost
= INSN_COST (insn
);
654 recog_memoized (insn
);
656 /* A USE insn, or something else we don't need to understand.
657 We can't pass these directly to result_ready_cost because it will
658 trigger a fatal error for unrecognizable insns. */
659 if (INSN_CODE (insn
) < 0)
661 INSN_COST (insn
) = 1;
666 cost
= result_ready_cost (insn
);
671 INSN_COST (insn
) = cost
;
675 /* In this case estimate cost without caring how insn is used. */
676 if (link
== 0 && used
== 0)
679 /* A USE insn should never require the value used to be computed. This
680 allows the computation of a function's result and parameter values to
681 overlap the return and call. */
682 recog_memoized (used
);
683 if (INSN_CODE (used
) < 0)
684 LINK_COST_FREE (link
) = 1;
686 /* If some dependencies vary the cost, compute the adjustment. Most
687 commonly, the adjustment is complete: either the cost is ignored
688 (in the case of an output- or anti-dependence), or the cost is
689 unchanged. These values are cached in the link as LINK_COST_FREE
690 and LINK_COST_ZERO. */
692 if (LINK_COST_FREE (link
))
694 else if (!LINK_COST_ZERO (link
) && targetm
.sched
.adjust_cost
)
696 int ncost
= (*targetm
.sched
.adjust_cost
) (used
, link
, insn
, cost
);
700 LINK_COST_FREE (link
) = 1;
704 LINK_COST_ZERO (link
) = 1;
711 /* Compute the priority number for INSN. */
722 if (! INSN_PRIORITY_KNOWN (insn
))
724 int this_priority
= 0;
726 if (INSN_DEPEND (insn
) == 0)
727 this_priority
= insn_cost (insn
, 0, 0);
730 for (link
= INSN_DEPEND (insn
); link
; link
= XEXP (link
, 1))
735 if (RTX_INTEGRATED_P (link
))
738 next
= XEXP (link
, 0);
740 /* Critical path is meaningful in block boundaries only. */
741 if (! (*current_sched_info
->contributes_to_priority
) (next
, insn
))
744 next_priority
= insn_cost (insn
, link
, next
) + priority (next
);
745 if (next_priority
> this_priority
)
746 this_priority
= next_priority
;
749 INSN_PRIORITY (insn
) = this_priority
;
750 INSN_PRIORITY_KNOWN (insn
) = 1;
753 return INSN_PRIORITY (insn
);
756 /* Macros and functions for keeping the priority queue sorted, and
757 dealing with queueing and dequeueing of instructions. */
759 #define SCHED_SORT(READY, N_READY) \
760 do { if ((N_READY) == 2) \
761 swap_sort (READY, N_READY); \
762 else if ((N_READY) > 2) \
763 qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \
766 /* Returns a positive value if x is preferred; returns a negative value if
767 y is preferred. Should never return 0, since that will make the sort
771 rank_for_schedule (x
, y
)
775 rtx tmp
= *(const rtx
*) y
;
776 rtx tmp2
= *(const rtx
*) x
;
778 int tmp_class
, tmp2_class
, depend_count1
, depend_count2
;
779 int val
, priority_val
, weight_val
, info_val
;
781 /* Prefer insn with higher priority. */
782 priority_val
= INSN_PRIORITY (tmp2
) - INSN_PRIORITY (tmp
);
786 /* Prefer an insn with smaller contribution to registers-pressure. */
787 if (!reload_completed
&&
788 (weight_val
= INSN_REG_WEIGHT (tmp
) - INSN_REG_WEIGHT (tmp2
)))
791 info_val
= (*current_sched_info
->rank
) (tmp
, tmp2
);
795 /* Compare insns based on their relation to the last-scheduled-insn. */
796 if (last_scheduled_insn
)
798 /* Classify the instructions into three classes:
799 1) Data dependent on last schedule insn.
800 2) Anti/Output dependent on last scheduled insn.
801 3) Independent of last scheduled insn, or has latency of one.
802 Choose the insn from the highest numbered class if different. */
803 link
= find_insn_list (tmp
, INSN_DEPEND (last_scheduled_insn
));
804 if (link
== 0 || insn_cost (last_scheduled_insn
, link
, tmp
) == 1)
806 else if (REG_NOTE_KIND (link
) == 0) /* Data dependence. */
811 link
= find_insn_list (tmp2
, INSN_DEPEND (last_scheduled_insn
));
812 if (link
== 0 || insn_cost (last_scheduled_insn
, link
, tmp2
) == 1)
814 else if (REG_NOTE_KIND (link
) == 0) /* Data dependence. */
819 if ((val
= tmp2_class
- tmp_class
))
823 /* Prefer the insn which has more later insns that depend on it.
824 This gives the scheduler more freedom when scheduling later
825 instructions at the expense of added register pressure. */
827 for (link
= INSN_DEPEND (tmp
); link
; link
= XEXP (link
, 1))
831 for (link
= INSN_DEPEND (tmp2
); link
; link
= XEXP (link
, 1))
834 val
= depend_count2
- depend_count1
;
838 /* If insns are equally good, sort by INSN_LUID (original insn order),
839 so that we make the sort stable. This minimizes instruction movement,
840 thus minimizing sched's effect on debugging and cross-jumping. */
841 return INSN_LUID (tmp
) - INSN_LUID (tmp2
);
844 /* Resort the array A in which only element at index N may be out of order. */
846 HAIFA_INLINE
static void
854 while (i
>= 0 && rank_for_schedule (a
+ i
, &insn
) >= 0)
862 /* Add INSN to the insn queue so that it can be executed at least
863 N_CYCLES after the currently executing insn. Preserve insns
864 chain for debugging purposes. */
866 HAIFA_INLINE
static void
867 queue_insn (insn
, n_cycles
)
871 int next_q
= NEXT_Q_AFTER (q_ptr
, n_cycles
);
872 rtx link
= alloc_INSN_LIST (insn
, insn_queue
[next_q
]);
873 insn_queue
[next_q
] = link
;
876 if (sched_verbose
>= 2)
878 fprintf (sched_dump
, ";;\t\tReady-->Q: insn %s: ",
879 (*current_sched_info
->print_insn
) (insn
, 0));
881 fprintf (sched_dump
, "queued for %d cycles.\n", n_cycles
);
885 /* Return a pointer to the bottom of the ready list, i.e. the insn
886 with the lowest priority. */
888 HAIFA_INLINE
static rtx
*
889 ready_lastpos (ready
)
890 struct ready_list
*ready
;
892 if (ready
->n_ready
== 0)
894 return ready
->vec
+ ready
->first
- ready
->n_ready
+ 1;
897 /* Add an element INSN to the ready list so that it ends up with the lowest
901 ready_add (ready
, insn
)
902 struct ready_list
*ready
;
905 if (ready
->first
== ready
->n_ready
)
907 memmove (ready
->vec
+ ready
->veclen
- ready
->n_ready
,
908 ready_lastpos (ready
),
909 ready
->n_ready
* sizeof (rtx
));
910 ready
->first
= ready
->veclen
- 1;
912 ready
->vec
[ready
->first
- ready
->n_ready
] = insn
;
916 /* Remove the element with the highest priority from the ready list and
919 HAIFA_INLINE
static rtx
920 ready_remove_first (ready
)
921 struct ready_list
*ready
;
924 if (ready
->n_ready
== 0)
926 t
= ready
->vec
[ready
->first
--];
928 /* If the queue becomes empty, reset it. */
929 if (ready
->n_ready
== 0)
930 ready
->first
= ready
->veclen
- 1;
934 /* Sort the ready list READY by ascending priority, using the SCHED_SORT
937 HAIFA_INLINE
static void
939 struct ready_list
*ready
;
941 rtx
*first
= ready_lastpos (ready
);
942 SCHED_SORT (first
, ready
->n_ready
);
945 /* PREV is an insn that is ready to execute. Adjust its priority if that
946 will help shorten or lengthen register lifetimes as appropriate. Also
947 provide a hook for the target to tweek itself. */
949 HAIFA_INLINE
static void
950 adjust_priority (prev
)
953 /* ??? There used to be code here to try and estimate how an insn
954 affected register lifetimes, but it did it by looking at REG_DEAD
955 notes, which we removed in schedule_region. Nor did it try to
956 take into account register pressure or anything useful like that.
958 Revisit when we have a machine model to work with and not before. */
960 if (targetm
.sched
.adjust_priority
)
961 INSN_PRIORITY (prev
) =
962 (*targetm
.sched
.adjust_priority
) (prev
, INSN_PRIORITY (prev
));
965 /* Clock at which the previous instruction was issued. */
966 static int last_clock_var
;
968 /* INSN is the "currently executing insn". Launch each insn which was
969 waiting on INSN. READY is the ready list which contains the insns
970 that are ready to fire. CLOCK is the current cycle.
974 schedule_insn (insn
, ready
, clock
)
976 struct ready_list
*ready
;
982 unit
= insn_unit (insn
);
984 if (sched_verbose
>= 2)
986 fprintf (sched_dump
, ";;\t\t--> scheduling insn <<<%d>>> on unit ",
988 insn_print_units (insn
);
989 fprintf (sched_dump
, "\n");
992 if (sched_verbose
&& unit
== -1)
993 visualize_no_unit (insn
);
995 if (MAX_BLOCKAGE
> 1 || issue_rate
> 1 || sched_verbose
)
996 schedule_unit (unit
, insn
, clock
);
998 if (INSN_DEPEND (insn
) == 0)
1001 for (link
= INSN_DEPEND (insn
); link
!= 0; link
= XEXP (link
, 1))
1003 rtx next
= XEXP (link
, 0);
1004 int cost
= insn_cost (insn
, link
, next
);
1006 INSN_TICK (next
) = MAX (INSN_TICK (next
), clock
+ cost
);
1008 if ((INSN_DEP_COUNT (next
) -= 1) == 0)
1010 int effective_cost
= INSN_TICK (next
) - clock
;
1012 if (! (*current_sched_info
->new_ready
) (next
))
1015 if (sched_verbose
>= 2)
1017 fprintf (sched_dump
, ";;\t\tdependences resolved: insn %s ",
1018 (*current_sched_info
->print_insn
) (next
, 0));
1020 if (effective_cost
< 1)
1021 fprintf (sched_dump
, "into ready\n");
1023 fprintf (sched_dump
, "into queue with cost=%d\n", effective_cost
);
1026 /* Adjust the priority of NEXT and either put it on the ready
1027 list or queue it. */
1028 adjust_priority (next
);
1029 if (effective_cost
< 1)
1030 ready_add (ready
, next
);
1032 queue_insn (next
, effective_cost
);
1036 /* Annotate the instruction with issue information -- TImode
1037 indicates that the instruction is expected not to be able
1038 to issue on the same cycle as the previous insn. A machine
1039 may use this information to decide how the instruction should
1041 if (reload_completed
&& issue_rate
> 1)
1043 PUT_MODE (insn
, clock
> last_clock_var
? TImode
: VOIDmode
);
1044 last_clock_var
= clock
;
1048 /* Functions for handling of notes. */
1050 /* Delete notes beginning with INSN and put them in the chain
1051 of notes ended by NOTE_LIST.
1052 Returns the insn following the notes. */
1055 unlink_other_notes (insn
, tail
)
1058 rtx prev
= PREV_INSN (insn
);
1060 while (insn
!= tail
&& GET_CODE (insn
) == NOTE
)
1062 rtx next
= NEXT_INSN (insn
);
1063 /* Delete the note from its current position. */
1065 NEXT_INSN (prev
) = next
;
1067 PREV_INSN (next
) = prev
;
1069 /* See sched_analyze to see how these are handled. */
1070 if (NOTE_LINE_NUMBER (insn
) != NOTE_INSN_LOOP_BEG
1071 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_LOOP_END
1072 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_RANGE_BEG
1073 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_RANGE_END
1074 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_EH_REGION_BEG
1075 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_EH_REGION_END
)
1077 /* Insert the note at the end of the notes list. */
1078 PREV_INSN (insn
) = note_list
;
1080 NEXT_INSN (note_list
) = insn
;
1089 /* Delete line notes beginning with INSN. Record line-number notes so
1090 they can be reused. Returns the insn following the notes. */
1093 unlink_line_notes (insn
, tail
)
1096 rtx prev
= PREV_INSN (insn
);
1098 while (insn
!= tail
&& GET_CODE (insn
) == NOTE
)
1100 rtx next
= NEXT_INSN (insn
);
1102 if (write_symbols
!= NO_DEBUG
&& NOTE_LINE_NUMBER (insn
) > 0)
1104 /* Delete the note from its current position. */
1106 NEXT_INSN (prev
) = next
;
1108 PREV_INSN (next
) = prev
;
1110 /* Record line-number notes so they can be reused. */
1111 LINE_NOTE (insn
) = insn
;
1121 /* Return the head and tail pointers of BB. */
1124 get_block_head_tail (b
, headp
, tailp
)
1129 /* HEAD and TAIL delimit the basic block being scheduled. */
1130 rtx head
= BLOCK_HEAD (b
);
1131 rtx tail
= BLOCK_END (b
);
1133 /* Don't include any notes or labels at the beginning of the
1134 basic block, or notes at the ends of basic blocks. */
1135 while (head
!= tail
)
1137 if (GET_CODE (head
) == NOTE
)
1138 head
= NEXT_INSN (head
);
1139 else if (GET_CODE (tail
) == NOTE
)
1140 tail
= PREV_INSN (tail
);
1141 else if (GET_CODE (head
) == CODE_LABEL
)
1142 head
= NEXT_INSN (head
);
1151 /* Return nonzero if there are no real insns in the range [ HEAD, TAIL ]. */
1154 no_real_insns_p (head
, tail
)
1157 while (head
!= NEXT_INSN (tail
))
1159 if (GET_CODE (head
) != NOTE
&& GET_CODE (head
) != CODE_LABEL
)
1161 head
= NEXT_INSN (head
);
1166 /* Delete line notes from one block. Save them so they can be later restored
1167 (in restore_line_notes). HEAD and TAIL are the boundaries of the
1168 block in which notes should be processed. */
1171 rm_line_notes (head
, tail
)
1177 next_tail
= NEXT_INSN (tail
);
1178 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
1182 /* Farm out notes, and maybe save them in NOTE_LIST.
1183 This is needed to keep the debugger from
1184 getting completely deranged. */
1185 if (GET_CODE (insn
) == NOTE
)
1188 insn
= unlink_line_notes (insn
, next_tail
);
1194 if (insn
== next_tail
)
1200 /* Save line number notes for each insn in block B. HEAD and TAIL are
1201 the boundaries of the block in which notes should be processed.*/
1204 save_line_notes (b
, head
, tail
)
1210 /* We must use the true line number for the first insn in the block
1211 that was computed and saved at the start of this pass. We can't
1212 use the current line number, because scheduling of the previous
1213 block may have changed the current line number. */
1215 rtx line
= line_note_head
[b
];
1218 next_tail
= NEXT_INSN (tail
);
1220 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
1221 if (GET_CODE (insn
) == NOTE
&& NOTE_LINE_NUMBER (insn
) > 0)
1224 LINE_NOTE (insn
) = line
;
1227 /* After a block was scheduled, insert line notes into the insns list.
1228 HEAD and TAIL are the boundaries of the block in which notes should
1232 restore_line_notes (head
, tail
)
1235 rtx line
, note
, prev
, new;
1236 int added_notes
= 0;
1237 rtx next_tail
, insn
;
1240 next_tail
= NEXT_INSN (tail
);
1242 /* Determine the current line-number. We want to know the current
1243 line number of the first insn of the block here, in case it is
1244 different from the true line number that was saved earlier. If
1245 different, then we need a line number note before the first insn
1246 of this block. If it happens to be the same, then we don't want to
1247 emit another line number note here. */
1248 for (line
= head
; line
; line
= PREV_INSN (line
))
1249 if (GET_CODE (line
) == NOTE
&& NOTE_LINE_NUMBER (line
) > 0)
1252 /* Walk the insns keeping track of the current line-number and inserting
1253 the line-number notes as needed. */
1254 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
1255 if (GET_CODE (insn
) == NOTE
&& NOTE_LINE_NUMBER (insn
) > 0)
1257 /* This used to emit line number notes before every non-deleted note.
1258 However, this confuses a debugger, because line notes not separated
1259 by real instructions all end up at the same address. I can find no
1260 use for line number notes before other notes, so none are emitted. */
1261 else if (GET_CODE (insn
) != NOTE
1262 && INSN_UID (insn
) < old_max_uid
1263 && (note
= LINE_NOTE (insn
)) != 0
1266 || NOTE_LINE_NUMBER (note
) != NOTE_LINE_NUMBER (line
)
1267 || NOTE_SOURCE_FILE (note
) != NOTE_SOURCE_FILE (line
)))
1270 prev
= PREV_INSN (insn
);
1271 if (LINE_NOTE (note
))
1273 /* Re-use the original line-number note. */
1274 LINE_NOTE (note
) = 0;
1275 PREV_INSN (note
) = prev
;
1276 NEXT_INSN (prev
) = note
;
1277 PREV_INSN (insn
) = note
;
1278 NEXT_INSN (note
) = insn
;
1283 new = emit_note_after (NOTE_LINE_NUMBER (note
), prev
);
1284 NOTE_SOURCE_FILE (new) = NOTE_SOURCE_FILE (note
);
1285 RTX_INTEGRATED_P (new) = RTX_INTEGRATED_P (note
);
1288 if (sched_verbose
&& added_notes
)
1289 fprintf (sched_dump
, ";; added %d line-number notes\n", added_notes
);
1292 /* After scheduling the function, delete redundant line notes from the
1296 rm_redundant_line_notes ()
1299 rtx insn
= get_insns ();
1300 int active_insn
= 0;
1303 /* Walk the insns deleting redundant line-number notes. Many of these
1304 are already present. The remainder tend to occur at basic
1305 block boundaries. */
1306 for (insn
= get_last_insn (); insn
; insn
= PREV_INSN (insn
))
1307 if (GET_CODE (insn
) == NOTE
&& NOTE_LINE_NUMBER (insn
) > 0)
1309 /* If there are no active insns following, INSN is redundant. */
1310 if (active_insn
== 0)
1313 NOTE_SOURCE_FILE (insn
) = 0;
1314 NOTE_LINE_NUMBER (insn
) = NOTE_INSN_DELETED
;
1316 /* If the line number is unchanged, LINE is redundant. */
1318 && NOTE_LINE_NUMBER (line
) == NOTE_LINE_NUMBER (insn
)
1319 && NOTE_SOURCE_FILE (line
) == NOTE_SOURCE_FILE (insn
))
1322 NOTE_SOURCE_FILE (line
) = 0;
1323 NOTE_LINE_NUMBER (line
) = NOTE_INSN_DELETED
;
1330 else if (!((GET_CODE (insn
) == NOTE
1331 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_DELETED
)
1332 || (GET_CODE (insn
) == INSN
1333 && (GET_CODE (PATTERN (insn
)) == USE
1334 || GET_CODE (PATTERN (insn
)) == CLOBBER
))))
1337 if (sched_verbose
&& notes
)
1338 fprintf (sched_dump
, ";; deleted %d line-number notes\n", notes
);
1341 /* Delete notes between HEAD and TAIL and put them in the chain
1342 of notes ended by NOTE_LIST. */
1345 rm_other_notes (head
, tail
)
1353 if (head
== tail
&& (! INSN_P (head
)))
1356 next_tail
= NEXT_INSN (tail
);
1357 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
1361 /* Farm out notes, and maybe save them in NOTE_LIST.
1362 This is needed to keep the debugger from
1363 getting completely deranged. */
1364 if (GET_CODE (insn
) == NOTE
)
1368 insn
= unlink_other_notes (insn
, next_tail
);
1374 if (insn
== next_tail
)
1380 /* Functions for computation of registers live/usage info. */
1382 /* Calculate INSN_REG_WEIGHT for all insns of a block. */
1385 find_insn_reg_weight (b
)
1388 rtx insn
, next_tail
, head
, tail
;
1390 get_block_head_tail (b
, &head
, &tail
);
1391 next_tail
= NEXT_INSN (tail
);
1393 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
1398 /* Handle register life information. */
1399 if (! INSN_P (insn
))
1402 /* Increment weight for each register born here. */
1404 if ((GET_CODE (x
) == SET
|| GET_CODE (x
) == CLOBBER
)
1405 && register_operand (SET_DEST (x
), VOIDmode
))
1407 else if (GET_CODE (x
) == PARALLEL
)
1410 for (j
= XVECLEN (x
, 0) - 1; j
>= 0; j
--)
1412 x
= XVECEXP (PATTERN (insn
), 0, j
);
1413 if ((GET_CODE (x
) == SET
|| GET_CODE (x
) == CLOBBER
)
1414 && register_operand (SET_DEST (x
), VOIDmode
))
1419 /* Decrement weight for each register that dies here. */
1420 for (x
= REG_NOTES (insn
); x
; x
= XEXP (x
, 1))
1422 if (REG_NOTE_KIND (x
) == REG_DEAD
1423 || REG_NOTE_KIND (x
) == REG_UNUSED
)
1427 INSN_REG_WEIGHT (insn
) = reg_weight
;
1431 /* Scheduling clock, modified in schedule_block() and queue_to_ready (). */
1432 static int clock_var
;
1434 /* Move insns that became ready to fire from queue to ready list. */
1437 queue_to_ready (ready
)
1438 struct ready_list
*ready
;
1443 q_ptr
= NEXT_Q (q_ptr
);
1445 /* Add all pending insns that can be scheduled without stalls to the
1447 for (link
= insn_queue
[q_ptr
]; link
; link
= XEXP (link
, 1))
1449 insn
= XEXP (link
, 0);
1452 if (sched_verbose
>= 2)
1453 fprintf (sched_dump
, ";;\t\tQ-->Ready: insn %s: ",
1454 (*current_sched_info
->print_insn
) (insn
, 0));
1456 ready_add (ready
, insn
);
1457 if (sched_verbose
>= 2)
1458 fprintf (sched_dump
, "moving to ready without stalls\n");
1460 insn_queue
[q_ptr
] = 0;
1462 /* If there are no ready insns, stall until one is ready and add all
1463 of the pending insns at that point to the ready list. */
1464 if (ready
->n_ready
== 0)
1468 for (stalls
= 1; stalls
< INSN_QUEUE_SIZE
; stalls
++)
1470 if ((link
= insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)]))
1472 for (; link
; link
= XEXP (link
, 1))
1474 insn
= XEXP (link
, 0);
1477 if (sched_verbose
>= 2)
1478 fprintf (sched_dump
, ";;\t\tQ-->Ready: insn %s: ",
1479 (*current_sched_info
->print_insn
) (insn
, 0));
1481 ready_add (ready
, insn
);
1482 if (sched_verbose
>= 2)
1483 fprintf (sched_dump
, "moving to ready with %d stalls\n", stalls
);
1485 insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)] = 0;
1492 if (sched_verbose
&& stalls
)
1493 visualize_stall_cycles (stalls
);
1494 q_ptr
= NEXT_Q_AFTER (q_ptr
, stalls
);
1495 clock_var
+= stalls
;
1499 /* Print the ready list for debugging purposes. Callable from debugger. */
1502 debug_ready_list (ready
)
1503 struct ready_list
*ready
;
1508 if (ready
->n_ready
== 0)
1511 p
= ready_lastpos (ready
);
1512 for (i
= 0; i
< ready
->n_ready
; i
++)
1513 fprintf (sched_dump
, " %s", (*current_sched_info
->print_insn
) (p
[i
], 0));
1514 fprintf (sched_dump
, "\n");
1517 /* move_insn1: Remove INSN from insn chain, and link it after LAST insn. */
1520 move_insn1 (insn
, last
)
1523 NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
1524 PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
1526 NEXT_INSN (insn
) = NEXT_INSN (last
);
1527 PREV_INSN (NEXT_INSN (last
)) = insn
;
1529 NEXT_INSN (last
) = insn
;
1530 PREV_INSN (insn
) = last
;
1535 /* Search INSN for REG_SAVE_NOTE note pairs for
1536 NOTE_INSN_{LOOP,EHREGION}_{BEG,END}; and convert them back into
1537 NOTEs. The REG_SAVE_NOTE note following first one is contains the
1538 saved value for NOTE_BLOCK_NUMBER which is useful for
1539 NOTE_INSN_EH_REGION_{BEG,END} NOTEs. LAST is the last instruction
1540 output by the instruction scheduler. Return the new value of LAST. */
1543 reemit_notes (insn
, last
)
1550 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1552 if (REG_NOTE_KIND (note
) == REG_SAVE_NOTE
)
1554 enum insn_note note_type
= INTVAL (XEXP (note
, 0));
1556 if (note_type
== NOTE_INSN_RANGE_BEG
1557 || note_type
== NOTE_INSN_RANGE_END
)
1559 last
= emit_note_before (note_type
, last
);
1560 remove_note (insn
, note
);
1561 note
= XEXP (note
, 1);
1562 NOTE_RANGE_INFO (last
) = XEXP (note
, 0);
1566 last
= emit_note_before (note_type
, last
);
1567 remove_note (insn
, note
);
1568 note
= XEXP (note
, 1);
1569 if (note_type
== NOTE_INSN_EH_REGION_BEG
1570 || note_type
== NOTE_INSN_EH_REGION_END
)
1571 NOTE_EH_HANDLER (last
) = INTVAL (XEXP (note
, 0));
1573 remove_note (insn
, note
);
1580 /* NOTE_LIST is the end of a chain of notes previously found among the
1581 insns. Insert them at the beginning of the insns. Actually, insert
1582 NOTE_INSN_BLOCK_END notes at the end of the insns. Doing otherwise
1583 tends to collapse lexical blocks into empty regions, which is somewhat
1584 less than useful. */
1585 /* ??? Ideally we'd mark each insn with the block it originated from,
1586 and preserve that information. This requires some moderately
1587 sophisticated block reconstruction code, since block nestings must
1591 reemit_other_notes (head
, tail
)
1594 bool saw_block_beg
= false;
1598 rtx note_tail
= note_list
;
1599 note_list
= PREV_INSN (note_tail
);
1601 if (NOTE_LINE_NUMBER (note_tail
) == NOTE_INSN_BLOCK_END
1602 /* We can only extend the lexical block while we havn't
1603 seen a BLOCK_BEG note. Otherwise we risk mis-nesting
1607 rtx insert_after
= tail
;
1608 if (GET_CODE (NEXT_INSN (tail
)) == BARRIER
)
1609 insert_after
= NEXT_INSN (tail
);
1611 PREV_INSN (note_tail
) = insert_after
;
1612 NEXT_INSN (note_tail
) = NEXT_INSN (insert_after
);
1613 if (NEXT_INSN (insert_after
))
1614 PREV_INSN (NEXT_INSN (insert_after
)) = note_tail
;
1615 NEXT_INSN (insert_after
) = note_tail
;
1619 if (NOTE_LINE_NUMBER (note_tail
) == NOTE_INSN_BLOCK_BEG
)
1620 saw_block_beg
= true;
1622 PREV_INSN (note_tail
) = PREV_INSN (head
);
1623 NEXT_INSN (PREV_INSN (head
)) = note_tail
;
1624 NEXT_INSN (note_tail
) = head
;
1625 PREV_INSN (head
) = note_tail
;
1633 /* Move INSN, and all insns which should be issued before it,
1634 due to SCHED_GROUP_P flag. Reemit notes if needed.
1636 Return the last insn emitted by the scheduler, which is the
1637 return value from the first call to reemit_notes. */
1640 move_insn (insn
, last
)
1645 /* If INSN has SCHED_GROUP_P set, then issue it and any other
1646 insns with SCHED_GROUP_P set first. */
1647 while (SCHED_GROUP_P (insn
))
1649 rtx prev
= PREV_INSN (insn
);
1651 /* Move a SCHED_GROUP_P insn. */
1652 move_insn1 (insn
, last
);
1653 /* If this is the first call to reemit_notes, then record
1654 its return value. */
1655 if (retval
== NULL_RTX
)
1656 retval
= reemit_notes (insn
, insn
);
1658 reemit_notes (insn
, insn
);
1662 /* Now move the first non SCHED_GROUP_P insn. */
1663 move_insn1 (insn
, last
);
1665 /* If this is the first call to reemit_notes, then record
1666 its return value. */
1667 if (retval
== NULL_RTX
)
1668 retval
= reemit_notes (insn
, insn
);
1670 reemit_notes (insn
, insn
);
1675 /* Use forward list scheduling to rearrange insns of block B in region RGN,
1676 possibly bringing insns from subsequent blocks in the same region. */
1679 schedule_block (b
, rgn_n_insns
)
1684 struct ready_list ready
;
1687 /* Head/tail info for this block. */
1688 rtx prev_head
= current_sched_info
->prev_head
;
1689 rtx next_tail
= current_sched_info
->next_tail
;
1690 rtx head
= NEXT_INSN (prev_head
);
1691 rtx tail
= PREV_INSN (next_tail
);
1693 /* We used to have code to avoid getting parameters moved from hard
1694 argument registers into pseudos.
1696 However, it was removed when it proved to be of marginal benefit
1697 and caused problems because schedule_block and compute_forward_dependences
1698 had different notions of what the "head" insn was. */
1700 if (head
== tail
&& (! INSN_P (head
)))
1706 fprintf (sched_dump
, ";; ======================================================\n");
1707 fprintf (sched_dump
,
1708 ";; -- basic block %d from %d to %d -- %s reload\n",
1709 b
, INSN_UID (head
), INSN_UID (tail
),
1710 (reload_completed
? "after" : "before"));
1711 fprintf (sched_dump
, ";; ======================================================\n");
1712 fprintf (sched_dump
, "\n");
1715 init_block_visualization ();
1720 /* Allocate the ready list. */
1721 ready
.veclen
= rgn_n_insns
+ 1 + issue_rate
;
1722 ready
.first
= ready
.veclen
- 1;
1723 ready
.vec
= (rtx
*) xmalloc (ready
.veclen
* sizeof (rtx
));
1726 (*current_sched_info
->init_ready_list
) (&ready
);
1728 if (targetm
.sched
.md_init
)
1729 (*targetm
.sched
.md_init
) (sched_dump
, sched_verbose
, ready
.veclen
);
1731 /* No insns scheduled in this block yet. */
1732 last_scheduled_insn
= 0;
1734 /* Initialize INSN_QUEUE. Q_SIZE is the total number of insns in the
1739 memset ((char *) insn_queue
, 0, sizeof (insn_queue
));
1741 /* Start just before the beginning of time. */
1744 /* We start inserting insns after PREV_HEAD. */
1747 /* Loop until all the insns in BB are scheduled. */
1748 while ((*current_sched_info
->schedule_more_p
) ())
1752 /* Add to the ready list all pending insns that can be issued now.
1753 If there are no ready insns, increment clock until one
1754 is ready and add all pending insns at that point to the ready
1756 queue_to_ready (&ready
);
1758 if (sched_verbose
&& targetm
.sched
.cycle_display
)
1759 last
= (*targetm
.sched
.cycle_display
) (clock_var
, last
);
1761 if (ready
.n_ready
== 0)
1764 if (sched_verbose
>= 2)
1766 fprintf (sched_dump
, ";;\t\tReady list after queue_to_ready: ");
1767 debug_ready_list (&ready
);
1770 /* Sort the ready list based on priority. */
1771 ready_sort (&ready
);
1773 /* Allow the target to reorder the list, typically for
1774 better instruction bundling. */
1775 if (targetm
.sched
.reorder
)
1777 (*targetm
.sched
.reorder
) (sched_dump
, sched_verbose
,
1778 ready_lastpos (&ready
),
1779 &ready
.n_ready
, clock_var
);
1781 can_issue_more
= issue_rate
;
1785 fprintf (sched_dump
, "\n;;\tReady list (t =%3d): ", clock_var
);
1786 debug_ready_list (&ready
);
1789 /* Issue insns from ready list. */
1790 while (ready
.n_ready
!= 0
1792 && (*current_sched_info
->schedule_more_p
) ())
1794 /* Select and remove the insn from the ready list. */
1795 rtx insn
= ready_remove_first (&ready
);
1796 int cost
= actual_hazard (insn_unit (insn
), insn
, clock_var
, 0);
1800 queue_insn (insn
, cost
);
1804 if (! (*current_sched_info
->can_schedule_ready_p
) (insn
))
1807 last_scheduled_insn
= insn
;
1808 last
= move_insn (insn
, last
);
1810 if (targetm
.sched
.variable_issue
)
1812 (*targetm
.sched
.variable_issue
) (sched_dump
, sched_verbose
,
1813 insn
, can_issue_more
);
1817 schedule_insn (insn
, &ready
, clock_var
);
1820 if (targetm
.sched
.reorder2
)
1822 /* Sort the ready list based on priority. */
1823 if (ready
.n_ready
> 0)
1824 ready_sort (&ready
);
1826 (*targetm
.sched
.reorder2
) (sched_dump
,sched_verbose
,
1828 ? ready_lastpos (&ready
) : NULL
,
1829 &ready
.n_ready
, clock_var
);
1835 visualize_scheduled_insns (clock_var
);
1838 if (targetm
.sched
.md_finish
)
1839 (*targetm
.sched
.md_finish
) (sched_dump
, sched_verbose
);
1844 fprintf (sched_dump
, ";;\tReady list (final): ");
1845 debug_ready_list (&ready
);
1846 print_block_visualization ("");
1849 /* Sanity check -- queue must be empty now. Meaningless if region has
1851 if (current_sched_info
->queue_must_finish_empty
&& q_size
!= 0)
1854 /* Update head/tail boundaries. */
1855 head
= NEXT_INSN (prev_head
);
1858 head
= reemit_other_notes (head
, tail
);
1863 fprintf (sched_dump
, ";; total time = %d\n;; new head = %d\n",
1864 clock_var
, INSN_UID (head
));
1865 fprintf (sched_dump
, ";; new tail = %d\n\n",
1870 current_sched_info
->head
= head
;
1871 current_sched_info
->tail
= tail
;
1876 /* Set_priorities: compute priority of each insn in the block. */
1879 set_priorities (head
, tail
)
1887 prev_head
= PREV_INSN (head
);
1889 if (head
== tail
&& (! INSN_P (head
)))
1893 for (insn
= tail
; insn
!= prev_head
; insn
= PREV_INSN (insn
))
1895 if (GET_CODE (insn
) == NOTE
)
1898 if (!(SCHED_GROUP_P (insn
)))
1900 (void) priority (insn
);
1906 /* Initialize some global state for the scheduler. DUMP_FILE is to be used
1907 for debugging output. */
1910 sched_init (dump_file
)
1916 /* Disable speculative loads in their presence if cc0 defined. */
1918 flag_schedule_speculative_load
= 0;
1921 /* Set dump and sched_verbose for the desired debugging output. If no
1922 dump-file was specified, but -fsched-verbose=N (any N), print to stderr.
1923 For -fsched-verbose=N, N>=10, print everything to stderr. */
1924 sched_verbose
= sched_verbose_param
;
1925 if (sched_verbose_param
== 0 && dump_file
)
1927 sched_dump
= ((sched_verbose_param
>= 10 || !dump_file
)
1928 ? stderr
: dump_file
);
1930 /* Initialize issue_rate. */
1931 if (targetm
.sched
.issue_rate
)
1932 issue_rate
= (*targetm
.sched
.issue_rate
) ();
1936 /* We use LUID 0 for the fake insn (UID 0) which holds dependencies for
1937 pseudos which do not cross calls. */
1938 old_max_uid
= get_max_uid () + 1;
1940 h_i_d
= (struct haifa_insn_data
*) xcalloc (old_max_uid
, sizeof (*h_i_d
));
1944 for (b
= 0; b
< n_basic_blocks
; b
++)
1945 for (insn
= BLOCK_HEAD (b
);; insn
= NEXT_INSN (insn
))
1947 INSN_LUID (insn
) = luid
;
1949 /* Increment the next luid, unless this is a note. We don't
1950 really need separate IDs for notes and we don't want to
1951 schedule differently depending on whether or not there are
1952 line-number notes, i.e., depending on whether or not we're
1953 generating debugging information. */
1954 if (GET_CODE (insn
) != NOTE
)
1957 if (insn
== BLOCK_END (b
))
1961 init_dependency_caches (luid
);
1963 compute_bb_for_insn (old_max_uid
);
1965 init_alias_analysis ();
1967 if (write_symbols
!= NO_DEBUG
)
1971 line_note_head
= (rtx
*) xcalloc (n_basic_blocks
, sizeof (rtx
));
1973 /* Save-line-note-head:
1974 Determine the line-number at the start of each basic block.
1975 This must be computed and saved now, because after a basic block's
1976 predecessor has been scheduled, it is impossible to accurately
1977 determine the correct line number for the first insn of the block. */
1979 for (b
= 0; b
< n_basic_blocks
; b
++)
1981 for (line
= BLOCK_HEAD (b
); line
; line
= PREV_INSN (line
))
1982 if (GET_CODE (line
) == NOTE
&& NOTE_LINE_NUMBER (line
) > 0)
1984 line_note_head
[b
] = line
;
1987 /* Do a forward search as well, since we won't get to see the first
1988 notes in a basic block. */
1989 for (line
= BLOCK_HEAD (b
); line
; line
= NEXT_INSN (line
))
1993 if (GET_CODE (line
) == NOTE
&& NOTE_LINE_NUMBER (line
) > 0)
1994 line_note_head
[b
] = line
;
1999 /* Find units used in this function, for visualization. */
2001 init_target_units ();
2003 /* ??? Add a NOTE after the last insn of the last basic block. It is not
2004 known why this is done. */
2006 insn
= BLOCK_END (n_basic_blocks
- 1);
2007 if (NEXT_INSN (insn
) == 0
2008 || (GET_CODE (insn
) != NOTE
2009 && GET_CODE (insn
) != CODE_LABEL
2010 /* Don't emit a NOTE if it would end up before a BARRIER. */
2011 && GET_CODE (NEXT_INSN (insn
)) != BARRIER
))
2013 emit_note_after (NOTE_INSN_DELETED
, BLOCK_END (n_basic_blocks
- 1));
2014 /* Make insn to appear outside BB. */
2015 BLOCK_END (n_basic_blocks
- 1) = PREV_INSN (BLOCK_END (n_basic_blocks
- 1));
2018 /* Compute INSN_REG_WEIGHT for all blocks. We must do this before
2019 removing death notes. */
2020 for (b
= n_basic_blocks
- 1; b
>= 0; b
--)
2021 find_insn_reg_weight (b
);
2024 /* Free global data used during insn scheduling. */
2030 free_dependency_caches ();
2031 end_alias_analysis ();
2032 if (write_symbols
!= NO_DEBUG
)
2033 free (line_note_head
);
2035 #endif /* INSN_SCHEDULING */