]>
Commit | Line | Data |
---|---|---|
3eb9a99d | 1 | /* Instruction scheduling pass. |
2f791da8 | 2 | Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, |
04641143 | 3 | 1999, 2000, 2001, 2002 Free Software Foundation, Inc. |
3eb9a99d | 4 | Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by, |
5 | and currently maintained by, Jim Wilson (wilson@cygnus.com) | |
6 | ||
f12b58b3 | 7 | This file is part of GCC. |
b1820f75 | 8 | |
f12b58b3 | 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 | |
12 | version. | |
b1820f75 | 13 | |
f12b58b3 | 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 | |
b1820f75 | 16 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
17 | for more details. | |
18 | ||
19 | You should have received a copy of the GNU General Public License | |
f660683a | 20 | along with GCC; see the file COPYING. If not, write to the Free |
21 | Software Foundation, 59 Temple Place - Suite 330, Boston, MA | |
b1820f75 | 22 | 02111-1307, USA. */ |
3eb9a99d | 23 | |
7a31a7bd | 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. | |
3eb9a99d | 27 | |
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. | |
36 | ||
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. | |
41 | ||
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 | |
55 | remaining slots. | |
56 | ||
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. | |
63 | ||
64 | The following list shows the order in which we want to break ties | |
65 | among insns in the ready list: | |
66 | ||
67 | 1. choose insn with the longest path to end of bb, ties | |
68 | broken by | |
69 | 2. choose insn with least contribution to register pressure, | |
70 | ties broken by | |
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 | |
74 | broken by | |
75 | 6. choose insn with the least dependences upon the previously | |
76 | scheduled insn, or finally | |
02aef853 | 77 | 7 choose the insn which has the most insns dependent on it. |
78 | 8. choose insn with lowest UID. | |
3eb9a99d | 79 | |
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. | |
86 | ||
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 (). | |
90 | ||
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. | |
95 | ||
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 | |
103 | utilization. | |
104 | ||
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 | |
108 | of this case. | |
109 | ||
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. | |
114 | ||
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. | |
118 | ||
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). | |
123 | ||
124 | This pass must update information that subsequent passes expect to | |
125 | be correct. Namely: reg_n_refs, reg_n_sets, reg_n_deaths, | |
68676d00 | 126 | reg_n_calls_crossed, and reg_live_length. Also, BLOCK_HEAD, |
127 | BLOCK_END. | |
3eb9a99d | 128 | |
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 | |
7a31a7bd | 133 | beginning of basic blocks and regions that have been scheduled. */ |
3eb9a99d | 134 | \f |
3eb9a99d | 135 | #include "config.h" |
46c1a957 | 136 | #include "system.h" |
805e22b2 | 137 | #include "coretypes.h" |
138 | #include "tm.h" | |
d3b64f2d | 139 | #include "toplev.h" |
3eb9a99d | 140 | #include "rtl.h" |
7953c610 | 141 | #include "tm_p.h" |
d6cb6164 | 142 | #include "hard-reg-set.h" |
3eb9a99d | 143 | #include "basic-block.h" |
144 | #include "regs.h" | |
0a893c29 | 145 | #include "function.h" |
3eb9a99d | 146 | #include "flags.h" |
147 | #include "insn-config.h" | |
148 | #include "insn-attr.h" | |
149 | #include "except.h" | |
0e93a6ac | 150 | #include "toplev.h" |
ba1c8484 | 151 | #include "recog.h" |
c2069298 | 152 | #include "sched-int.h" |
747af5e7 | 153 | #include "target.h" |
3eb9a99d | 154 | |
3eb9a99d | 155 | #ifdef INSN_SCHEDULING |
156 | ||
3eb9a99d | 157 | /* issue_rate is the number of insns that can be scheduled in the same |
158 | machine cycle. It can be defined in the config/mach/mach.h file, | |
159 | otherwise we set it to 1. */ | |
160 | ||
161 | static int issue_rate; | |
162 | ||
c8515df4 | 163 | /* If the following variable value is nonzero, the scheduler inserts |
bea4bad2 | 164 | bubbles (nop insns). The value of variable affects on scheduler |
165 | behavior only if automaton pipeline interface with multipass | |
166 | scheduling is used and hook dfa_bubble is defined. */ | |
167 | int insert_schedule_bubbles_p = 0; | |
168 | ||
cc13a078 | 169 | /* sched-verbose controls the amount of debugging output the |
5c69f8a7 | 170 | scheduler prints. It is controlled by -fsched-verbose=N: |
3eb9a99d | 171 | N>0 and no -DSR : the output is directed to stderr. |
172 | N>=10 will direct the printouts to stderr (regardless of -dSR). | |
173 | N=1: same as -dSR. | |
174 | N=2: bb's probabilities, detailed ready list info, unit/insn info. | |
175 | N=3: rtl at abort point, control-flow, regions info. | |
cc13a078 | 176 | N=5: dependences info. */ |
3eb9a99d | 177 | |
3eb9a99d | 178 | static int sched_verbose_param = 0; |
7a31a7bd | 179 | int sched_verbose = 0; |
3eb9a99d | 180 | |
c4cd519a | 181 | /* Debugging file. All printouts are sent to dump, which is always set, |
3eb9a99d | 182 | either to stderr, or to the dump listing file (-dRS). */ |
10c06114 | 183 | FILE *sched_dump = 0; |
d0768316 | 184 | |
185 | /* Highest uid before scheduling. */ | |
186 | static int old_max_uid; | |
3eb9a99d | 187 | |
188 | /* fix_sched_param() is called from toplev.c upon detection | |
5c69f8a7 | 189 | of the -fsched-verbose=N option. */ |
3eb9a99d | 190 | |
191 | void | |
192 | fix_sched_param (param, val) | |
fdeac5ce | 193 | const char *param, *val; |
3eb9a99d | 194 | { |
cc13a078 | 195 | if (!strcmp (param, "verbose")) |
3eb9a99d | 196 | sched_verbose_param = atoi (val); |
3eb9a99d | 197 | else |
198 | warning ("fix_sched_param: unknown param: %s", param); | |
199 | } | |
200 | ||
6adce0fb | 201 | struct haifa_insn_data *h_i_d; |
d28d5327 | 202 | |
d28d5327 | 203 | #define LINE_NOTE(INSN) (h_i_d[INSN_UID (INSN)].line_note) |
204 | #define INSN_TICK(INSN) (h_i_d[INSN_UID (INSN)].tick) | |
3eb9a99d | 205 | |
206 | /* Vector indexed by basic block number giving the starting line-number | |
207 | for each basic block. */ | |
208 | static rtx *line_note_head; | |
209 | ||
210 | /* List of important notes we must keep around. This is a pointer to the | |
211 | last element in the list. */ | |
212 | static rtx note_list; | |
213 | ||
3eb9a99d | 214 | /* Queues, etc. */ |
215 | ||
216 | /* An instruction is ready to be scheduled when all insns preceding it | |
217 | have already been scheduled. It is important to ensure that all | |
218 | insns which use its result will not be executed until its result | |
219 | has been computed. An insn is maintained in one of four structures: | |
220 | ||
221 | (P) the "Pending" set of insns which cannot be scheduled until | |
222 | their dependencies have been satisfied. | |
223 | (Q) the "Queued" set of insns that can be scheduled when sufficient | |
224 | time has passed. | |
225 | (R) the "Ready" list of unscheduled, uncommitted insns. | |
226 | (S) the "Scheduled" list of insns. | |
227 | ||
228 | Initially, all insns are either "Pending" or "Ready" depending on | |
229 | whether their dependencies are satisfied. | |
230 | ||
231 | Insns move from the "Ready" list to the "Scheduled" list as they | |
232 | are committed to the schedule. As this occurs, the insns in the | |
233 | "Pending" list have their dependencies satisfied and move to either | |
234 | the "Ready" list or the "Queued" set depending on whether | |
235 | sufficient time has passed to make them ready. As time passes, | |
236 | insns move from the "Queued" set to the "Ready" list. Insns may | |
237 | move from the "Ready" list to the "Queued" set if they are blocked | |
238 | due to a function unit conflict. | |
239 | ||
240 | The "Pending" list (P) are the insns in the INSN_DEPEND of the unscheduled | |
241 | insns, i.e., those that are ready, queued, and pending. | |
242 | The "Queued" set (Q) is implemented by the variable `insn_queue'. | |
243 | The "Ready" list (R) is implemented by the variables `ready' and | |
244 | `n_ready'. | |
245 | The "Scheduled" list (S) is the new insn chain built by this pass. | |
246 | ||
247 | The transition (R->S) is implemented in the scheduling loop in | |
248 | `schedule_block' when the best insn to schedule is chosen. | |
249 | The transition (R->Q) is implemented in `queue_insn' when an | |
3398e91d | 250 | insn is found to have a function unit conflict with the already |
3eb9a99d | 251 | committed insns. |
252 | The transitions (P->R and P->Q) are implemented in `schedule_insn' as | |
253 | insns move from the ready list to the scheduled list. | |
254 | The transition (Q->R) is implemented in 'queue_to_insn' as time | |
255 | passes or stalls are introduced. */ | |
256 | ||
257 | /* Implement a circular buffer to delay instructions until sufficient | |
bea4bad2 | 258 | time has passed. For the old pipeline description interface, |
259 | INSN_QUEUE_SIZE is a power of two larger than MAX_BLOCKAGE and | |
260 | MAX_READY_COST computed by genattr.c. For the new pipeline | |
261 | description interface, MAX_INSN_QUEUE_INDEX is a power of two minus | |
262 | one which is larger than maximal time of instruction execution | |
263 | computed by genattr.c on the base maximal time of functional unit | |
264 | reservations and geting a result. This is the longest time an | |
265 | insn may be queued. */ | |
266 | ||
267 | #define MAX_INSN_QUEUE_INDEX max_insn_queue_index_macro_value | |
268 | ||
269 | static rtx *insn_queue; | |
3eb9a99d | 270 | static int q_ptr = 0; |
271 | static int q_size = 0; | |
bea4bad2 | 272 | #define NEXT_Q(X) (((X)+1) & MAX_INSN_QUEUE_INDEX) |
273 | #define NEXT_Q_AFTER(X, C) (((X)+C) & MAX_INSN_QUEUE_INDEX) | |
274 | ||
275 | /* The following variable defines value for macro | |
276 | MAX_INSN_QUEUE_INDEX. */ | |
277 | static int max_insn_queue_index_macro_value; | |
278 | ||
279 | /* The following variable value refers for all current and future | |
280 | reservations of the processor units. */ | |
281 | state_t curr_state; | |
282 | ||
283 | /* The following variable value is size of memory representing all | |
284 | current and future reservations of the processor units. It is used | |
285 | only by DFA based scheduler. */ | |
286 | static size_t dfa_state_size; | |
287 | ||
288 | /* The following array is used to find the best insn from ready when | |
289 | the automaton pipeline interface is used. */ | |
290 | static char *ready_try; | |
3eb9a99d | 291 | |
30b1ec30 | 292 | /* Describe the ready list of the scheduler. |
293 | VEC holds space enough for all insns in the current region. VECLEN | |
294 | says how many exactly. | |
295 | FIRST is the index of the element with the highest priority; i.e. the | |
296 | last one in the ready list, since elements are ordered by ascending | |
297 | priority. | |
298 | N_READY determines how many insns are on the ready list. */ | |
299 | ||
300 | struct ready_list | |
301 | { | |
302 | rtx *vec; | |
303 | int veclen; | |
304 | int first; | |
305 | int n_ready; | |
306 | }; | |
307 | ||
3eb9a99d | 308 | /* Forward declarations. */ |
bea4bad2 | 309 | |
310 | /* The scheduler using only DFA description should never use the | |
311 | following five functions: */ | |
38b9004f | 312 | static unsigned int blockage_range PARAMS ((int, rtx)); |
313 | static void clear_units PARAMS ((void)); | |
38b9004f | 314 | static void schedule_unit PARAMS ((int, rtx, int)); |
315 | static int actual_hazard PARAMS ((int, rtx, int, int)); | |
316 | static int potential_hazard PARAMS ((int, rtx, int)); | |
bea4bad2 | 317 | |
38b9004f | 318 | static int priority PARAMS ((rtx)); |
38b9004f | 319 | static int rank_for_schedule PARAMS ((const PTR, const PTR)); |
320 | static void swap_sort PARAMS ((rtx *, int)); | |
321 | static void queue_insn PARAMS ((rtx, int)); | |
30b1ec30 | 322 | static void schedule_insn PARAMS ((rtx, struct ready_list *, int)); |
38b9004f | 323 | static void find_insn_reg_weight PARAMS ((int)); |
38b9004f | 324 | static void adjust_priority PARAMS ((rtx)); |
bea4bad2 | 325 | static void advance_one_cycle PARAMS ((void)); |
3eb9a99d | 326 | |
3eb9a99d | 327 | /* Notes handling mechanism: |
328 | ========================= | |
329 | Generally, NOTES are saved before scheduling and restored after scheduling. | |
330 | The scheduler distinguishes between three types of notes: | |
331 | ||
332 | (1) LINE_NUMBER notes, generated and used for debugging. Here, | |
333 | before scheduling a region, a pointer to the LINE_NUMBER note is | |
334 | added to the insn following it (in save_line_notes()), and the note | |
335 | is removed (in rm_line_notes() and unlink_line_notes()). After | |
336 | scheduling the region, this pointer is used for regeneration of | |
337 | the LINE_NUMBER note (in restore_line_notes()). | |
338 | ||
339 | (2) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes: | |
340 | Before scheduling a region, a pointer to the note is added to the insn | |
341 | that follows or precedes it. (This happens as part of the data dependence | |
342 | computation). After scheduling an insn, the pointer contained in it is | |
343 | used for regenerating the corresponding note (in reemit_notes). | |
344 | ||
345 | (3) All other notes (e.g. INSN_DELETED): Before scheduling a block, | |
346 | these notes are put in a list (in rm_other_notes() and | |
347 | unlink_other_notes ()). After scheduling the block, these notes are | |
348 | inserted at the beginning of the block (in schedule_block()). */ | |
349 | ||
38b9004f | 350 | static rtx unlink_other_notes PARAMS ((rtx, rtx)); |
351 | static rtx unlink_line_notes PARAMS ((rtx, rtx)); | |
38b9004f | 352 | static rtx reemit_notes PARAMS ((rtx, rtx)); |
353 | ||
30b1ec30 | 354 | static rtx *ready_lastpos PARAMS ((struct ready_list *)); |
355 | static void ready_sort PARAMS ((struct ready_list *)); | |
356 | static rtx ready_remove_first PARAMS ((struct ready_list *)); | |
38b9004f | 357 | |
30b1ec30 | 358 | static void queue_to_ready PARAMS ((struct ready_list *)); |
359 | ||
360 | static void debug_ready_list PARAMS ((struct ready_list *)); | |
38b9004f | 361 | |
362 | static rtx move_insn1 PARAMS ((rtx, rtx)); | |
363 | static rtx move_insn PARAMS ((rtx, rtx)); | |
3eb9a99d | 364 | |
bea4bad2 | 365 | /* The following functions are used to implement multi-pass scheduling |
366 | on the first cycle. It is used only for DFA based scheduler. */ | |
367 | static rtx ready_element PARAMS ((struct ready_list *, int)); | |
368 | static rtx ready_remove PARAMS ((struct ready_list *, int)); | |
369 | static int max_issue PARAMS ((struct ready_list *, state_t, int *)); | |
370 | ||
371 | static rtx choose_ready PARAMS ((struct ready_list *)); | |
372 | ||
3eb9a99d | 373 | #endif /* INSN_SCHEDULING */ |
374 | \f | |
c2069298 | 375 | /* Point to state used for the current scheduling pass. */ |
376 | struct sched_info *current_sched_info; | |
3eb9a99d | 377 | \f |
378 | #ifndef INSN_SCHEDULING | |
379 | void | |
380 | schedule_insns (dump_file) | |
d8c9779c | 381 | FILE *dump_file ATTRIBUTE_UNUSED; |
3eb9a99d | 382 | { |
383 | } | |
384 | #else | |
3e016693 | 385 | |
3eb9a99d | 386 | /* Pointer to the last instruction scheduled. Used by rank_for_schedule, |
387 | so that insns independent of the last scheduled insn will be preferred | |
388 | over dependent instructions. */ | |
389 | ||
390 | static rtx last_scheduled_insn; | |
391 | ||
7a31a7bd | 392 | /* Compute the function units used by INSN. This caches the value |
393 | returned by function_units_used. A function unit is encoded as the | |
28c2d844 | 394 | unit number if the value is non-negative and the complement of a |
7a31a7bd | 395 | mask if the value is negative. A function unit index is the |
bea4bad2 | 396 | non-negative encoding. The scheduler using only DFA description |
397 | should never use the following function. */ | |
df6c1c81 | 398 | |
7a31a7bd | 399 | HAIFA_INLINE int |
400 | insn_unit (insn) | |
401 | rtx insn; | |
3eb9a99d | 402 | { |
19cb6b50 | 403 | int unit = INSN_UNIT (insn); |
df6c1c81 | 404 | |
7a31a7bd | 405 | if (unit == 0) |
8ef4c24f | 406 | { |
7a31a7bd | 407 | recog_memoized (insn); |
3eb9a99d | 408 | |
7a31a7bd | 409 | /* A USE insn, or something else we don't need to understand. |
410 | We can't pass these directly to function_units_used because it will | |
411 | trigger a fatal error for unrecognizable insns. */ | |
412 | if (INSN_CODE (insn) < 0) | |
413 | unit = -1; | |
414 | else | |
3eb9a99d | 415 | { |
7a31a7bd | 416 | unit = function_units_used (insn); |
417 | /* Increment non-negative values so we can cache zero. */ | |
418 | if (unit >= 0) | |
419 | unit++; | |
3eb9a99d | 420 | } |
7a31a7bd | 421 | /* We only cache 16 bits of the result, so if the value is out of |
422 | range, don't cache it. */ | |
423 | if (FUNCTION_UNITS_SIZE < HOST_BITS_PER_SHORT | |
424 | || unit >= 0 | |
425 | || (unit & ~((1 << (HOST_BITS_PER_SHORT - 1)) - 1)) == 0) | |
426 | INSN_UNIT (insn) = unit; | |
3eb9a99d | 427 | } |
7a31a7bd | 428 | return (unit > 0 ? unit - 1 : unit); |
429 | } | |
3eb9a99d | 430 | |
7a31a7bd | 431 | /* Compute the blockage range for executing INSN on UNIT. This caches |
432 | the value returned by the blockage_range_function for the unit. | |
433 | These values are encoded in an int where the upper half gives the | |
bea4bad2 | 434 | minimum value and the lower half gives the maximum value. The |
435 | scheduler using only DFA description should never use the following | |
436 | function. */ | |
3eb9a99d | 437 | |
7a31a7bd | 438 | HAIFA_INLINE static unsigned int |
439 | blockage_range (unit, insn) | |
440 | int unit; | |
441 | rtx insn; | |
442 | { | |
443 | unsigned int blockage = INSN_BLOCKAGE (insn); | |
444 | unsigned int range; | |
3eb9a99d | 445 | |
7a31a7bd | 446 | if ((int) UNIT_BLOCKED (blockage) != unit + 1) |
3eb9a99d | 447 | { |
7a31a7bd | 448 | range = function_units[unit].blockage_range_function (insn); |
449 | /* We only cache the blockage range for one unit and then only if | |
450 | the values fit. */ | |
451 | if (HOST_BITS_PER_INT >= UNIT_BITS + 2 * BLOCKAGE_BITS) | |
452 | INSN_BLOCKAGE (insn) = ENCODE_BLOCKAGE (unit + 1, range); | |
3eb9a99d | 453 | } |
454 | else | |
7a31a7bd | 455 | range = BLOCKAGE_RANGE (blockage); |
3eb9a99d | 456 | |
7a31a7bd | 457 | return range; |
3eb9a99d | 458 | } |
459 | ||
bea4bad2 | 460 | /* A vector indexed by function unit instance giving the last insn to |
461 | use the unit. The value of the function unit instance index for | |
462 | unit U instance I is (U + I * FUNCTION_UNITS_SIZE). The scheduler | |
463 | using only DFA description should never use the following variable. */ | |
464 | #if FUNCTION_UNITS_SIZE | |
7a31a7bd | 465 | static rtx unit_last_insn[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY]; |
bea4bad2 | 466 | #else |
467 | static rtx unit_last_insn[1]; | |
468 | #endif | |
3eb9a99d | 469 | |
bea4bad2 | 470 | /* A vector indexed by function unit instance giving the minimum time |
471 | when the unit will unblock based on the maximum blockage cost. The | |
472 | scheduler using only DFA description should never use the following | |
473 | variable. */ | |
474 | #if FUNCTION_UNITS_SIZE | |
7a31a7bd | 475 | static int unit_tick[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY]; |
bea4bad2 | 476 | #else |
477 | static int unit_tick[1]; | |
478 | #endif | |
7a31a7bd | 479 | |
480 | /* A vector indexed by function unit number giving the number of insns | |
bea4bad2 | 481 | that remain to use the unit. The scheduler using only DFA |
482 | description should never use the following variable. */ | |
483 | #if FUNCTION_UNITS_SIZE | |
7a31a7bd | 484 | static int unit_n_insns[FUNCTION_UNITS_SIZE]; |
bea4bad2 | 485 | #else |
486 | static int unit_n_insns[1]; | |
487 | #endif | |
3eb9a99d | 488 | |
bea4bad2 | 489 | /* Access the unit_last_insn array. Used by the visualization code. |
490 | The scheduler using only DFA description should never use the | |
491 | following function. */ | |
3eb9a99d | 492 | |
7a31a7bd | 493 | rtx |
494 | get_unit_last_insn (instance) | |
495 | int instance; | |
3eb9a99d | 496 | { |
7a31a7bd | 497 | return unit_last_insn[instance]; |
3eb9a99d | 498 | } |
499 | ||
7a31a7bd | 500 | /* Reset the function unit state to the null state. */ |
3eb9a99d | 501 | |
502 | static void | |
7a31a7bd | 503 | clear_units () |
3eb9a99d | 504 | { |
7a31a7bd | 505 | memset ((char *) unit_last_insn, 0, sizeof (unit_last_insn)); |
506 | memset ((char *) unit_tick, 0, sizeof (unit_tick)); | |
507 | memset ((char *) unit_n_insns, 0, sizeof (unit_n_insns)); | |
508 | } | |
3eb9a99d | 509 | |
bea4bad2 | 510 | /* Return the issue-delay of an insn. The scheduler using only DFA |
511 | description should never use the following function. */ | |
3eb9a99d | 512 | |
7a31a7bd | 513 | HAIFA_INLINE int |
514 | insn_issue_delay (insn) | |
515 | rtx insn; | |
516 | { | |
517 | int i, delay = 0; | |
518 | int unit = insn_unit (insn); | |
3eb9a99d | 519 | |
7a31a7bd | 520 | /* Efficiency note: in fact, we are working 'hard' to compute a |
521 | value that was available in md file, and is not available in | |
522 | function_units[] structure. It would be nice to have this | |
523 | value there, too. */ | |
524 | if (unit >= 0) | |
3eb9a99d | 525 | { |
7a31a7bd | 526 | if (function_units[unit].blockage_range_function && |
527 | function_units[unit].blockage_function) | |
528 | delay = function_units[unit].blockage_function (insn, insn); | |
3eb9a99d | 529 | } |
7a31a7bd | 530 | else |
531 | for (i = 0, unit = ~unit; unit; i++, unit >>= 1) | |
532 | if ((unit & 1) != 0 && function_units[i].blockage_range_function | |
533 | && function_units[i].blockage_function) | |
534 | delay = MAX (delay, function_units[i].blockage_function (insn, insn)); | |
3eb9a99d | 535 | |
7a31a7bd | 536 | return delay; |
3eb9a99d | 537 | } |
538 | ||
7a31a7bd | 539 | /* Return the actual hazard cost of executing INSN on the unit UNIT, |
540 | instance INSTANCE at time CLOCK if the previous actual hazard cost | |
bea4bad2 | 541 | was COST. The scheduler using only DFA description should never |
542 | use the following function. */ | |
3eb9a99d | 543 | |
7a31a7bd | 544 | HAIFA_INLINE int |
545 | actual_hazard_this_instance (unit, instance, insn, clock, cost) | |
546 | int unit, instance, clock, cost; | |
547 | rtx insn; | |
3eb9a99d | 548 | { |
7a31a7bd | 549 | int tick = unit_tick[instance]; /* Issue time of the last issued insn. */ |
3eb9a99d | 550 | |
7a31a7bd | 551 | if (tick - clock > cost) |
3eb9a99d | 552 | { |
7a31a7bd | 553 | /* The scheduler is operating forward, so unit's last insn is the |
554 | executing insn and INSN is the candidate insn. We want a | |
555 | more exact measure of the blockage if we execute INSN at CLOCK | |
556 | given when we committed the execution of the unit's last insn. | |
3eb9a99d | 557 | |
7a31a7bd | 558 | The blockage value is given by either the unit's max blockage |
559 | constant, blockage range function, or blockage function. Use | |
560 | the most exact form for the given unit. */ | |
3eb9a99d | 561 | |
7a31a7bd | 562 | if (function_units[unit].blockage_range_function) |
563 | { | |
564 | if (function_units[unit].blockage_function) | |
565 | tick += (function_units[unit].blockage_function | |
566 | (unit_last_insn[instance], insn) | |
567 | - function_units[unit].max_blockage); | |
568 | else | |
569 | tick += ((int) MAX_BLOCKAGE_COST (blockage_range (unit, insn)) | |
570 | - function_units[unit].max_blockage); | |
3eb9a99d | 571 | } |
7a31a7bd | 572 | if (tick - clock > cost) |
573 | cost = tick - clock; | |
3eb9a99d | 574 | } |
7a31a7bd | 575 | return cost; |
3eb9a99d | 576 | } |
577 | ||
bea4bad2 | 578 | /* Record INSN as having begun execution on the units encoded by UNIT |
579 | at time CLOCK. The scheduler using only DFA description should | |
580 | never use the following function. */ | |
3eb9a99d | 581 | |
3e016693 | 582 | HAIFA_INLINE static void |
3eb9a99d | 583 | schedule_unit (unit, insn, clock) |
584 | int unit, clock; | |
585 | rtx insn; | |
586 | { | |
587 | int i; | |
588 | ||
589 | if (unit >= 0) | |
590 | { | |
591 | int instance = unit; | |
592 | #if MAX_MULTIPLICITY > 1 | |
593 | /* Find the first free instance of the function unit and use that | |
594 | one. We assume that one is free. */ | |
595 | for (i = function_units[unit].multiplicity - 1; i > 0; i--) | |
596 | { | |
597 | if (!actual_hazard_this_instance (unit, instance, insn, clock, 0)) | |
598 | break; | |
599 | instance += FUNCTION_UNITS_SIZE; | |
600 | } | |
601 | #endif | |
602 | unit_last_insn[instance] = insn; | |
603 | unit_tick[instance] = (clock + function_units[unit].max_blockage); | |
604 | } | |
605 | else | |
606 | for (i = 0, unit = ~unit; unit; i++, unit >>= 1) | |
607 | if ((unit & 1) != 0) | |
608 | schedule_unit (i, insn, clock); | |
609 | } | |
610 | ||
bea4bad2 | 611 | /* Return the actual hazard cost of executing INSN on the units |
612 | encoded by UNIT at time CLOCK if the previous actual hazard cost | |
613 | was COST. The scheduler using only DFA description should never | |
614 | use the following function. */ | |
3eb9a99d | 615 | |
3e016693 | 616 | HAIFA_INLINE static int |
3eb9a99d | 617 | actual_hazard (unit, insn, clock, cost) |
618 | int unit, clock, cost; | |
619 | rtx insn; | |
620 | { | |
621 | int i; | |
622 | ||
623 | if (unit >= 0) | |
624 | { | |
625 | /* Find the instance of the function unit with the minimum hazard. */ | |
626 | int instance = unit; | |
627 | int best_cost = actual_hazard_this_instance (unit, instance, insn, | |
628 | clock, cost); | |
ae6c5f02 | 629 | #if MAX_MULTIPLICITY > 1 |
3eb9a99d | 630 | int this_cost; |
631 | ||
3eb9a99d | 632 | if (best_cost > cost) |
633 | { | |
634 | for (i = function_units[unit].multiplicity - 1; i > 0; i--) | |
635 | { | |
636 | instance += FUNCTION_UNITS_SIZE; | |
637 | this_cost = actual_hazard_this_instance (unit, instance, insn, | |
638 | clock, cost); | |
639 | if (this_cost < best_cost) | |
640 | { | |
641 | best_cost = this_cost; | |
642 | if (this_cost <= cost) | |
643 | break; | |
644 | } | |
645 | } | |
646 | } | |
647 | #endif | |
648 | cost = MAX (cost, best_cost); | |
649 | } | |
650 | else | |
651 | for (i = 0, unit = ~unit; unit; i++, unit >>= 1) | |
652 | if ((unit & 1) != 0) | |
653 | cost = actual_hazard (i, insn, clock, cost); | |
654 | ||
655 | return cost; | |
656 | } | |
657 | ||
658 | /* Return the potential hazard cost of executing an instruction on the | |
bea4bad2 | 659 | units encoded by UNIT if the previous potential hazard cost was |
660 | COST. An insn with a large blockage time is chosen in preference | |
661 | to one with a smaller time; an insn that uses a unit that is more | |
662 | likely to be used is chosen in preference to one with a unit that | |
663 | is less used. We are trying to minimize a subsequent actual | |
664 | hazard. The scheduler using only DFA description should never use | |
665 | the following function. */ | |
3eb9a99d | 666 | |
3e016693 | 667 | HAIFA_INLINE static int |
3eb9a99d | 668 | potential_hazard (unit, insn, cost) |
669 | int unit, cost; | |
670 | rtx insn; | |
671 | { | |
672 | int i, ncost; | |
673 | unsigned int minb, maxb; | |
674 | ||
675 | if (unit >= 0) | |
676 | { | |
677 | minb = maxb = function_units[unit].max_blockage; | |
678 | if (maxb > 1) | |
679 | { | |
680 | if (function_units[unit].blockage_range_function) | |
681 | { | |
682 | maxb = minb = blockage_range (unit, insn); | |
683 | maxb = MAX_BLOCKAGE_COST (maxb); | |
684 | minb = MIN_BLOCKAGE_COST (minb); | |
685 | } | |
686 | ||
687 | if (maxb > 1) | |
688 | { | |
689 | /* Make the number of instructions left dominate. Make the | |
690 | minimum delay dominate the maximum delay. If all these | |
691 | are the same, use the unit number to add an arbitrary | |
692 | ordering. Other terms can be added. */ | |
693 | ncost = minb * 0x40 + maxb; | |
694 | ncost *= (unit_n_insns[unit] - 1) * 0x1000 + unit; | |
695 | if (ncost > cost) | |
696 | cost = ncost; | |
697 | } | |
698 | } | |
699 | } | |
700 | else | |
701 | for (i = 0, unit = ~unit; unit; i++, unit >>= 1) | |
702 | if ((unit & 1) != 0) | |
703 | cost = potential_hazard (i, insn, cost); | |
704 | ||
705 | return cost; | |
706 | } | |
707 | ||
708 | /* Compute cost of executing INSN given the dependence LINK on the insn USED. | |
709 | This is the number of cycles between instruction issue and | |
710 | instruction results. */ | |
711 | ||
7a31a7bd | 712 | HAIFA_INLINE int |
3eb9a99d | 713 | insn_cost (insn, link, used) |
714 | rtx insn, link, used; | |
715 | { | |
19cb6b50 | 716 | int cost = INSN_COST (insn); |
3eb9a99d | 717 | |
bea4bad2 | 718 | if (cost < 0) |
3eb9a99d | 719 | { |
bea4bad2 | 720 | /* A USE insn, or something else we don't need to |
721 | understand. We can't pass these directly to | |
722 | result_ready_cost or insn_default_latency because it will | |
723 | trigger a fatal error for unrecognizable insns. */ | |
724 | if (recog_memoized (insn) < 0) | |
3eb9a99d | 725 | { |
bea4bad2 | 726 | INSN_COST (insn) = 0; |
727 | return 0; | |
3eb9a99d | 728 | } |
729 | else | |
730 | { | |
bea4bad2 | 731 | if (targetm.sched.use_dfa_pipeline_interface |
732 | && (*targetm.sched.use_dfa_pipeline_interface) ()) | |
733 | cost = insn_default_latency (insn); | |
734 | else | |
735 | cost = result_ready_cost (insn); | |
736 | ||
737 | if (cost < 0) | |
738 | cost = 0; | |
739 | ||
3eb9a99d | 740 | INSN_COST (insn) = cost; |
741 | } | |
742 | } | |
743 | ||
c4cd519a | 744 | /* In this case estimate cost without caring how insn is used. */ |
bea4bad2 | 745 | if (link == 0 || used == 0) |
3eb9a99d | 746 | return cost; |
747 | ||
bea4bad2 | 748 | /* A USE insn should never require the value used to be computed. |
749 | This allows the computation of a function's result and parameter | |
750 | values to overlap the return and call. */ | |
751 | if (recog_memoized (used) < 0) | |
de206697 | 752 | cost = 0; |
bea4bad2 | 753 | else |
3eb9a99d | 754 | { |
bea4bad2 | 755 | if (targetm.sched.use_dfa_pipeline_interface |
756 | && (*targetm.sched.use_dfa_pipeline_interface) ()) | |
de206697 | 757 | { |
bea4bad2 | 758 | if (INSN_CODE (insn) >= 0) |
759 | { | |
760 | if (REG_NOTE_KIND (link) == REG_DEP_ANTI) | |
761 | cost = 0; | |
762 | else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT) | |
763 | { | |
764 | cost = (insn_default_latency (insn) | |
765 | - insn_default_latency (used)); | |
766 | if (cost <= 0) | |
767 | cost = 1; | |
768 | } | |
769 | else if (bypass_p (insn)) | |
770 | cost = insn_latency (insn, used); | |
771 | } | |
de206697 | 772 | } |
17c7a04d | 773 | |
bea4bad2 | 774 | if (targetm.sched.adjust_cost) |
775 | cost = (*targetm.sched.adjust_cost) (used, link, insn, cost); | |
776 | ||
777 | if (cost < 0) | |
778 | cost = 0; | |
779 | } | |
780 | ||
3eb9a99d | 781 | return cost; |
782 | } | |
783 | ||
784 | /* Compute the priority number for INSN. */ | |
785 | ||
786 | static int | |
787 | priority (insn) | |
788 | rtx insn; | |
789 | { | |
3eb9a99d | 790 | rtx link; |
791 | ||
9204e736 | 792 | if (! INSN_P (insn)) |
3eb9a99d | 793 | return 0; |
794 | ||
89beeed3 | 795 | if (! INSN_PRIORITY_KNOWN (insn)) |
3eb9a99d | 796 | { |
89beeed3 | 797 | int this_priority = 0; |
798 | ||
3eb9a99d | 799 | if (INSN_DEPEND (insn) == 0) |
800 | this_priority = insn_cost (insn, 0, 0); | |
801 | else | |
89beeed3 | 802 | { |
803 | for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1)) | |
804 | { | |
805 | rtx next; | |
806 | int next_priority; | |
3eb9a99d | 807 | |
89beeed3 | 808 | if (RTX_INTEGRATED_P (link)) |
809 | continue; | |
c4fa4c4d | 810 | |
89beeed3 | 811 | next = XEXP (link, 0); |
3eb9a99d | 812 | |
89beeed3 | 813 | /* Critical path is meaningful in block boundaries only. */ |
814 | if (! (*current_sched_info->contributes_to_priority) (next, insn)) | |
815 | continue; | |
3eb9a99d | 816 | |
89beeed3 | 817 | next_priority = insn_cost (insn, link, next) + priority (next); |
818 | if (next_priority > this_priority) | |
819 | this_priority = next_priority; | |
820 | } | |
821 | } | |
3eb9a99d | 822 | INSN_PRIORITY (insn) = this_priority; |
89beeed3 | 823 | INSN_PRIORITY_KNOWN (insn) = 1; |
3eb9a99d | 824 | } |
89beeed3 | 825 | |
826 | return INSN_PRIORITY (insn); | |
3eb9a99d | 827 | } |
828 | \f | |
3eb9a99d | 829 | /* Macros and functions for keeping the priority queue sorted, and |
830 | dealing with queueing and dequeueing of instructions. */ | |
831 | ||
832 | #define SCHED_SORT(READY, N_READY) \ | |
833 | do { if ((N_READY) == 2) \ | |
834 | swap_sort (READY, N_READY); \ | |
835 | else if ((N_READY) > 2) \ | |
836 | qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \ | |
837 | while (0) | |
838 | ||
839 | /* Returns a positive value if x is preferred; returns a negative value if | |
840 | y is preferred. Should never return 0, since that will make the sort | |
841 | unstable. */ | |
842 | ||
843 | static int | |
844 | rank_for_schedule (x, y) | |
9520c8bb | 845 | const PTR x; |
846 | const PTR y; | |
3eb9a99d | 847 | { |
896c2bfe | 848 | rtx tmp = *(const rtx *) y; |
849 | rtx tmp2 = *(const rtx *) x; | |
ca78c3fa | 850 | rtx link; |
02aef853 | 851 | int tmp_class, tmp2_class, depend_count1, depend_count2; |
c2069298 | 852 | int val, priority_val, weight_val, info_val; |
3eb9a99d | 853 | |
c4cd519a | 854 | /* Prefer insn with higher priority. */ |
3eb9a99d | 855 | priority_val = INSN_PRIORITY (tmp2) - INSN_PRIORITY (tmp); |
856 | if (priority_val) | |
857 | return priority_val; | |
858 | ||
c4cd519a | 859 | /* Prefer an insn with smaller contribution to registers-pressure. */ |
3eb9a99d | 860 | if (!reload_completed && |
861 | (weight_val = INSN_REG_WEIGHT (tmp) - INSN_REG_WEIGHT (tmp2))) | |
805e22b2 | 862 | return weight_val; |
3eb9a99d | 863 | |
c2069298 | 864 | info_val = (*current_sched_info->rank) (tmp, tmp2); |
865 | if (info_val) | |
866 | return info_val; | |
3eb9a99d | 867 | |
c4cd519a | 868 | /* Compare insns based on their relation to the last-scheduled-insn. */ |
ca78c3fa | 869 | if (last_scheduled_insn) |
3eb9a99d | 870 | { |
871 | /* Classify the instructions into three classes: | |
872 | 1) Data dependent on last schedule insn. | |
873 | 2) Anti/Output dependent on last scheduled insn. | |
874 | 3) Independent of last scheduled insn, or has latency of one. | |
875 | Choose the insn from the highest numbered class if different. */ | |
ca78c3fa | 876 | link = find_insn_list (tmp, INSN_DEPEND (last_scheduled_insn)); |
877 | if (link == 0 || insn_cost (last_scheduled_insn, link, tmp) == 1) | |
3eb9a99d | 878 | tmp_class = 3; |
879 | else if (REG_NOTE_KIND (link) == 0) /* Data dependence. */ | |
880 | tmp_class = 1; | |
881 | else | |
882 | tmp_class = 2; | |
883 | ||
ca78c3fa | 884 | link = find_insn_list (tmp2, INSN_DEPEND (last_scheduled_insn)); |
885 | if (link == 0 || insn_cost (last_scheduled_insn, link, tmp2) == 1) | |
3eb9a99d | 886 | tmp2_class = 3; |
887 | else if (REG_NOTE_KIND (link) == 0) /* Data dependence. */ | |
888 | tmp2_class = 1; | |
889 | else | |
890 | tmp2_class = 2; | |
891 | ||
892 | if ((val = tmp2_class - tmp_class)) | |
893 | return val; | |
894 | } | |
895 | ||
896c2bfe | 896 | /* Prefer the insn which has more later insns that depend on it. |
02aef853 | 897 | This gives the scheduler more freedom when scheduling later |
898 | instructions at the expense of added register pressure. */ | |
899 | depend_count1 = 0; | |
900 | for (link = INSN_DEPEND (tmp); link; link = XEXP (link, 1)) | |
901 | depend_count1++; | |
902 | ||
903 | depend_count2 = 0; | |
904 | for (link = INSN_DEPEND (tmp2); link; link = XEXP (link, 1)) | |
905 | depend_count2++; | |
906 | ||
907 | val = depend_count2 - depend_count1; | |
908 | if (val) | |
909 | return val; | |
896c2bfe | 910 | |
3eb9a99d | 911 | /* If insns are equally good, sort by INSN_LUID (original insn order), |
912 | so that we make the sort stable. This minimizes instruction movement, | |
913 | thus minimizing sched's effect on debugging and cross-jumping. */ | |
914 | return INSN_LUID (tmp) - INSN_LUID (tmp2); | |
915 | } | |
916 | ||
917 | /* Resort the array A in which only element at index N may be out of order. */ | |
918 | ||
3e016693 | 919 | HAIFA_INLINE static void |
3eb9a99d | 920 | swap_sort (a, n) |
921 | rtx *a; | |
922 | int n; | |
923 | { | |
924 | rtx insn = a[n - 1]; | |
925 | int i = n - 2; | |
926 | ||
927 | while (i >= 0 && rank_for_schedule (a + i, &insn) >= 0) | |
928 | { | |
929 | a[i + 1] = a[i]; | |
930 | i -= 1; | |
931 | } | |
932 | a[i + 1] = insn; | |
933 | } | |
934 | ||
3eb9a99d | 935 | /* Add INSN to the insn queue so that it can be executed at least |
936 | N_CYCLES after the currently executing insn. Preserve insns | |
937 | chain for debugging purposes. */ | |
938 | ||
3e016693 | 939 | HAIFA_INLINE static void |
3eb9a99d | 940 | queue_insn (insn, n_cycles) |
941 | rtx insn; | |
942 | int n_cycles; | |
943 | { | |
944 | int next_q = NEXT_Q_AFTER (q_ptr, n_cycles); | |
7ce0700a | 945 | rtx link = alloc_INSN_LIST (insn, insn_queue[next_q]); |
3eb9a99d | 946 | insn_queue[next_q] = link; |
947 | q_size += 1; | |
948 | ||
949 | if (sched_verbose >= 2) | |
950 | { | |
c2069298 | 951 | fprintf (sched_dump, ";;\t\tReady-->Q: insn %s: ", |
952 | (*current_sched_info->print_insn) (insn, 0)); | |
3eb9a99d | 953 | |
d0768316 | 954 | fprintf (sched_dump, "queued for %d cycles.\n", n_cycles); |
3eb9a99d | 955 | } |
30b1ec30 | 956 | } |
957 | ||
958 | /* Return a pointer to the bottom of the ready list, i.e. the insn | |
959 | with the lowest priority. */ | |
960 | ||
961 | HAIFA_INLINE static rtx * | |
962 | ready_lastpos (ready) | |
963 | struct ready_list *ready; | |
964 | { | |
965 | if (ready->n_ready == 0) | |
966 | abort (); | |
967 | return ready->vec + ready->first - ready->n_ready + 1; | |
968 | } | |
969 | ||
970 | /* Add an element INSN to the ready list so that it ends up with the lowest | |
971 | priority. */ | |
972 | ||
7a31a7bd | 973 | HAIFA_INLINE void |
30b1ec30 | 974 | ready_add (ready, insn) |
975 | struct ready_list *ready; | |
976 | rtx insn; | |
977 | { | |
978 | if (ready->first == ready->n_ready) | |
979 | { | |
980 | memmove (ready->vec + ready->veclen - ready->n_ready, | |
981 | ready_lastpos (ready), | |
982 | ready->n_ready * sizeof (rtx)); | |
983 | ready->first = ready->veclen - 1; | |
984 | } | |
985 | ready->vec[ready->first - ready->n_ready] = insn; | |
986 | ready->n_ready++; | |
987 | } | |
3eb9a99d | 988 | |
30b1ec30 | 989 | /* Remove the element with the highest priority from the ready list and |
990 | return it. */ | |
991 | ||
992 | HAIFA_INLINE static rtx | |
993 | ready_remove_first (ready) | |
994 | struct ready_list *ready; | |
995 | { | |
996 | rtx t; | |
997 | if (ready->n_ready == 0) | |
998 | abort (); | |
999 | t = ready->vec[ready->first--]; | |
1000 | ready->n_ready--; | |
1001 | /* If the queue becomes empty, reset it. */ | |
1002 | if (ready->n_ready == 0) | |
1003 | ready->first = ready->veclen - 1; | |
1004 | return t; | |
1005 | } | |
1006 | ||
bea4bad2 | 1007 | /* The following code implements multi-pass scheduling for the first |
1008 | cycle. In other words, we will try to choose ready insn which | |
1009 | permits to start maximum number of insns on the same cycle. */ | |
1010 | ||
1011 | /* Return a pointer to the element INDEX from the ready. INDEX for | |
1012 | insn with the highest priority is 0, and the lowest priority has | |
1013 | N_READY - 1. */ | |
1014 | ||
1015 | HAIFA_INLINE static rtx | |
1016 | ready_element (ready, index) | |
1017 | struct ready_list *ready; | |
1018 | int index; | |
1019 | { | |
1020 | if (ready->n_ready == 0 || index >= ready->n_ready) | |
1021 | abort (); | |
1022 | return ready->vec[ready->first - index]; | |
1023 | } | |
1024 | ||
1025 | /* Remove the element INDEX from the ready list and return it. INDEX | |
1026 | for insn with the highest priority is 0, and the lowest priority | |
1027 | has N_READY - 1. */ | |
1028 | ||
1029 | HAIFA_INLINE static rtx | |
1030 | ready_remove (ready, index) | |
1031 | struct ready_list *ready; | |
1032 | int index; | |
1033 | { | |
1034 | rtx t; | |
1035 | int i; | |
1036 | ||
1037 | if (index == 0) | |
1038 | return ready_remove_first (ready); | |
1039 | if (ready->n_ready == 0 || index >= ready->n_ready) | |
1040 | abort (); | |
1041 | t = ready->vec[ready->first - index]; | |
1042 | ready->n_ready--; | |
1043 | for (i = index; i < ready->n_ready; i++) | |
1044 | ready->vec[ready->first - i] = ready->vec[ready->first - i - 1]; | |
1045 | return t; | |
1046 | } | |
1047 | ||
1048 | ||
30b1ec30 | 1049 | /* Sort the ready list READY by ascending priority, using the SCHED_SORT |
1050 | macro. */ | |
1051 | ||
1052 | HAIFA_INLINE static void | |
1053 | ready_sort (ready) | |
1054 | struct ready_list *ready; | |
1055 | { | |
1056 | rtx *first = ready_lastpos (ready); | |
1057 | SCHED_SORT (first, ready->n_ready); | |
3eb9a99d | 1058 | } |
1059 | ||
3eb9a99d | 1060 | /* PREV is an insn that is ready to execute. Adjust its priority if that |
ba57cb24 | 1061 | will help shorten or lengthen register lifetimes as appropriate. Also |
1062 | provide a hook for the target to tweek itself. */ | |
3eb9a99d | 1063 | |
3e016693 | 1064 | HAIFA_INLINE static void |
3eb9a99d | 1065 | adjust_priority (prev) |
747af5e7 | 1066 | rtx prev; |
3eb9a99d | 1067 | { |
ba57cb24 | 1068 | /* ??? There used to be code here to try and estimate how an insn |
1069 | affected register lifetimes, but it did it by looking at REG_DEAD | |
896c2bfe | 1070 | notes, which we removed in schedule_region. Nor did it try to |
ba57cb24 | 1071 | take into account register pressure or anything useful like that. |
3eb9a99d | 1072 | |
ba57cb24 | 1073 | Revisit when we have a machine model to work with and not before. */ |
de206697 | 1074 | |
747af5e7 | 1075 | if (targetm.sched.adjust_priority) |
1076 | INSN_PRIORITY (prev) = | |
1077 | (*targetm.sched.adjust_priority) (prev, INSN_PRIORITY (prev)); | |
3eb9a99d | 1078 | } |
1079 | ||
bea4bad2 | 1080 | /* Advance time on one cycle. */ |
1081 | HAIFA_INLINE static void | |
1082 | advance_one_cycle () | |
1083 | { | |
1084 | if (targetm.sched.use_dfa_pipeline_interface | |
1085 | && (*targetm.sched.use_dfa_pipeline_interface) ()) | |
1086 | { | |
1087 | if (targetm.sched.dfa_pre_cycle_insn) | |
1088 | state_transition (curr_state, | |
1089 | (*targetm.sched.dfa_pre_cycle_insn) ()); | |
1090 | ||
1091 | state_transition (curr_state, NULL); | |
1092 | ||
1093 | if (targetm.sched.dfa_post_cycle_insn) | |
1094 | state_transition (curr_state, | |
1095 | (*targetm.sched.dfa_post_cycle_insn) ()); | |
1096 | } | |
1097 | } | |
1098 | ||
8da6595b | 1099 | /* Clock at which the previous instruction was issued. */ |
1100 | static int last_clock_var; | |
1101 | ||
3eb9a99d | 1102 | /* INSN is the "currently executing insn". Launch each insn which was |
30b1ec30 | 1103 | waiting on INSN. READY is the ready list which contains the insns |
1104 | that are ready to fire. CLOCK is the current cycle. | |
1105 | */ | |
3eb9a99d | 1106 | |
30b1ec30 | 1107 | static void |
1108 | schedule_insn (insn, ready, clock) | |
3eb9a99d | 1109 | rtx insn; |
30b1ec30 | 1110 | struct ready_list *ready; |
3eb9a99d | 1111 | int clock; |
1112 | { | |
1113 | rtx link; | |
bea4bad2 | 1114 | int unit = 0; |
3eb9a99d | 1115 | |
bea4bad2 | 1116 | if (!targetm.sched.use_dfa_pipeline_interface |
1117 | || !(*targetm.sched.use_dfa_pipeline_interface) ()) | |
1118 | unit = insn_unit (insn); | |
3eb9a99d | 1119 | |
0bc18d66 | 1120 | if (targetm.sched.use_dfa_pipeline_interface |
1121 | && (*targetm.sched.use_dfa_pipeline_interface) () | |
1122 | && sched_verbose >= 1) | |
3eb9a99d | 1123 | { |
0bc18d66 | 1124 | char buf[2048]; |
bea4bad2 | 1125 | |
0bc18d66 | 1126 | print_insn (buf, insn, 0); |
1127 | buf[40]=0; | |
1128 | fprintf (sched_dump, ";;\t%3i--> %-40s:", clock, buf); | |
bea4bad2 | 1129 | |
0bc18d66 | 1130 | if (recog_memoized (insn) < 0) |
1131 | fprintf (sched_dump, "nothing"); | |
1132 | else | |
1133 | print_reservation (sched_dump, insn); | |
1134 | fputc ('\n', sched_dump); | |
1135 | } | |
1136 | else if (sched_verbose >= 2) | |
1137 | { | |
1138 | fprintf (sched_dump, ";;\t\t--> scheduling insn <<<%d>>> on unit ", | |
1139 | INSN_UID (insn)); | |
1140 | insn_print_units (insn); | |
1141 | fputc ('\n', sched_dump); | |
3eb9a99d | 1142 | } |
1143 | ||
bea4bad2 | 1144 | if (!targetm.sched.use_dfa_pipeline_interface |
1145 | || !(*targetm.sched.use_dfa_pipeline_interface) ()) | |
1146 | { | |
1147 | if (sched_verbose && unit == -1) | |
1148 | visualize_no_unit (insn); | |
3eb9a99d | 1149 | |
3eb9a99d | 1150 | |
bea4bad2 | 1151 | if (MAX_BLOCKAGE > 1 || issue_rate > 1 || sched_verbose) |
1152 | schedule_unit (unit, insn, clock); | |
1153 | ||
1154 | if (INSN_DEPEND (insn) == 0) | |
1155 | return; | |
1156 | } | |
3eb9a99d | 1157 | |
1158 | for (link = INSN_DEPEND (insn); link != 0; link = XEXP (link, 1)) | |
1159 | { | |
1160 | rtx next = XEXP (link, 0); | |
1161 | int cost = insn_cost (insn, link, next); | |
1162 | ||
1163 | INSN_TICK (next) = MAX (INSN_TICK (next), clock + cost); | |
1164 | ||
1165 | if ((INSN_DEP_COUNT (next) -= 1) == 0) | |
1166 | { | |
1167 | int effective_cost = INSN_TICK (next) - clock; | |
1168 | ||
c2069298 | 1169 | if (! (*current_sched_info->new_ready) (next)) |
3eb9a99d | 1170 | continue; |
1171 | ||
1172 | if (sched_verbose >= 2) | |
1173 | { | |
c2069298 | 1174 | fprintf (sched_dump, ";;\t\tdependences resolved: insn %s ", |
1175 | (*current_sched_info->print_insn) (next, 0)); | |
3eb9a99d | 1176 | |
de206697 | 1177 | if (effective_cost < 1) |
d0768316 | 1178 | fprintf (sched_dump, "into ready\n"); |
3eb9a99d | 1179 | else |
d0768316 | 1180 | fprintf (sched_dump, "into queue with cost=%d\n", effective_cost); |
3eb9a99d | 1181 | } |
1182 | ||
1183 | /* Adjust the priority of NEXT and either put it on the ready | |
1184 | list or queue it. */ | |
1185 | adjust_priority (next); | |
de206697 | 1186 | if (effective_cost < 1) |
30b1ec30 | 1187 | ready_add (ready, next); |
3eb9a99d | 1188 | else |
1189 | queue_insn (next, effective_cost); | |
1190 | } | |
1191 | } | |
1192 | ||
896c2bfe | 1193 | /* Annotate the instruction with issue information -- TImode |
8da6595b | 1194 | indicates that the instruction is expected not to be able |
1195 | to issue on the same cycle as the previous insn. A machine | |
1196 | may use this information to decide how the instruction should | |
1197 | be aligned. */ | |
bea4bad2 | 1198 | if (reload_completed && issue_rate > 1 |
1199 | && GET_CODE (PATTERN (insn)) != USE | |
1200 | && GET_CODE (PATTERN (insn)) != CLOBBER) | |
8da6595b | 1201 | { |
1202 | PUT_MODE (insn, clock > last_clock_var ? TImode : VOIDmode); | |
1203 | last_clock_var = clock; | |
1204 | } | |
3eb9a99d | 1205 | } |
1206 | ||
c4cd519a | 1207 | /* Functions for handling of notes. */ |
3eb9a99d | 1208 | |
1209 | /* Delete notes beginning with INSN and put them in the chain | |
1210 | of notes ended by NOTE_LIST. | |
1211 | Returns the insn following the notes. */ | |
1212 | ||
1213 | static rtx | |
1214 | unlink_other_notes (insn, tail) | |
1215 | rtx insn, tail; | |
1216 | { | |
1217 | rtx prev = PREV_INSN (insn); | |
1218 | ||
1219 | while (insn != tail && GET_CODE (insn) == NOTE) | |
1220 | { | |
1221 | rtx next = NEXT_INSN (insn); | |
1222 | /* Delete the note from its current position. */ | |
1223 | if (prev) | |
1224 | NEXT_INSN (prev) = next; | |
1225 | if (next) | |
1226 | PREV_INSN (next) = prev; | |
1227 | ||
ba57cb24 | 1228 | /* See sched_analyze to see how these are handled. */ |
9239aee6 | 1229 | if (NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG |
3eb9a99d | 1230 | && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_END |
1231 | && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_BEG | |
1232 | && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_END) | |
1233 | { | |
1234 | /* Insert the note at the end of the notes list. */ | |
1235 | PREV_INSN (insn) = note_list; | |
1236 | if (note_list) | |
1237 | NEXT_INSN (note_list) = insn; | |
1238 | note_list = insn; | |
1239 | } | |
1240 | ||
1241 | insn = next; | |
1242 | } | |
1243 | return insn; | |
1244 | } | |
1245 | ||
1246 | /* Delete line notes beginning with INSN. Record line-number notes so | |
1247 | they can be reused. Returns the insn following the notes. */ | |
1248 | ||
1249 | static rtx | |
1250 | unlink_line_notes (insn, tail) | |
1251 | rtx insn, tail; | |
1252 | { | |
1253 | rtx prev = PREV_INSN (insn); | |
1254 | ||
1255 | while (insn != tail && GET_CODE (insn) == NOTE) | |
1256 | { | |
1257 | rtx next = NEXT_INSN (insn); | |
1258 | ||
1259 | if (write_symbols != NO_DEBUG && NOTE_LINE_NUMBER (insn) > 0) | |
1260 | { | |
1261 | /* Delete the note from its current position. */ | |
1262 | if (prev) | |
1263 | NEXT_INSN (prev) = next; | |
1264 | if (next) | |
1265 | PREV_INSN (next) = prev; | |
1266 | ||
1267 | /* Record line-number notes so they can be reused. */ | |
1268 | LINE_NOTE (insn) = insn; | |
1269 | } | |
1270 | else | |
1271 | prev = insn; | |
1272 | ||
1273 | insn = next; | |
1274 | } | |
1275 | return insn; | |
1276 | } | |
1277 | ||
1278 | /* Return the head and tail pointers of BB. */ | |
1279 | ||
7a31a7bd | 1280 | void |
def93098 | 1281 | get_block_head_tail (b, headp, tailp) |
1282 | int b; | |
3eb9a99d | 1283 | rtx *headp; |
1284 | rtx *tailp; | |
1285 | { | |
3eb9a99d | 1286 | /* HEAD and TAIL delimit the basic block being scheduled. */ |
c2069298 | 1287 | rtx head = BLOCK_HEAD (b); |
1288 | rtx tail = BLOCK_END (b); | |
3eb9a99d | 1289 | |
1290 | /* Don't include any notes or labels at the beginning of the | |
1291 | basic block, or notes at the ends of basic blocks. */ | |
1292 | while (head != tail) | |
1293 | { | |
1294 | if (GET_CODE (head) == NOTE) | |
1295 | head = NEXT_INSN (head); | |
1296 | else if (GET_CODE (tail) == NOTE) | |
1297 | tail = PREV_INSN (tail); | |
1298 | else if (GET_CODE (head) == CODE_LABEL) | |
1299 | head = NEXT_INSN (head); | |
1300 | else | |
1301 | break; | |
1302 | } | |
1303 | ||
1304 | *headp = head; | |
1305 | *tailp = tail; | |
1306 | } | |
1307 | ||
c2069298 | 1308 | /* Return nonzero if there are no real insns in the range [ HEAD, TAIL ]. */ |
1309 | ||
7a31a7bd | 1310 | int |
c2069298 | 1311 | no_real_insns_p (head, tail) |
1312 | rtx head, tail; | |
1313 | { | |
1314 | while (head != NEXT_INSN (tail)) | |
1315 | { | |
1316 | if (GET_CODE (head) != NOTE && GET_CODE (head) != CODE_LABEL) | |
1317 | return 0; | |
1318 | head = NEXT_INSN (head); | |
1319 | } | |
1320 | return 1; | |
1321 | } | |
1322 | ||
2295df67 | 1323 | /* Delete line notes from one block. Save them so they can be later restored |
1324 | (in restore_line_notes). HEAD and TAIL are the boundaries of the | |
1325 | block in which notes should be processed. */ | |
3eb9a99d | 1326 | |
7a31a7bd | 1327 | void |
2295df67 | 1328 | rm_line_notes (head, tail) |
1329 | rtx head, tail; | |
3eb9a99d | 1330 | { |
1331 | rtx next_tail; | |
3eb9a99d | 1332 | rtx insn; |
1333 | ||
3eb9a99d | 1334 | next_tail = NEXT_INSN (tail); |
1335 | for (insn = head; insn != next_tail; insn = NEXT_INSN (insn)) | |
1336 | { | |
1337 | rtx prev; | |
1338 | ||
1339 | /* Farm out notes, and maybe save them in NOTE_LIST. | |
1340 | This is needed to keep the debugger from | |
1341 | getting completely deranged. */ | |
1342 | if (GET_CODE (insn) == NOTE) | |
1343 | { | |
1344 | prev = insn; | |
1345 | insn = unlink_line_notes (insn, next_tail); | |
1346 | ||
1347 | if (prev == tail) | |
1348 | abort (); | |
1349 | if (prev == head) | |
1350 | abort (); | |
1351 | if (insn == next_tail) | |
1352 | abort (); | |
1353 | } | |
1354 | } | |
1355 | } | |
1356 | ||
2295df67 | 1357 | /* Save line number notes for each insn in block B. HEAD and TAIL are |
04641143 | 1358 | the boundaries of the block in which notes should be processed. */ |
3eb9a99d | 1359 | |
7a31a7bd | 1360 | void |
2295df67 | 1361 | save_line_notes (b, head, tail) |
7a31a7bd | 1362 | int b; |
2295df67 | 1363 | rtx head, tail; |
3eb9a99d | 1364 | { |
3eb9a99d | 1365 | rtx next_tail; |
1366 | ||
1367 | /* We must use the true line number for the first insn in the block | |
1368 | that was computed and saved at the start of this pass. We can't | |
1369 | use the current line number, because scheduling of the previous | |
1370 | block may have changed the current line number. */ | |
1371 | ||
7a31a7bd | 1372 | rtx line = line_note_head[b]; |
3eb9a99d | 1373 | rtx insn; |
1374 | ||
3eb9a99d | 1375 | next_tail = NEXT_INSN (tail); |
1376 | ||
2295df67 | 1377 | for (insn = head; insn != next_tail; insn = NEXT_INSN (insn)) |
3eb9a99d | 1378 | if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0) |
1379 | line = insn; | |
1380 | else | |
1381 | LINE_NOTE (insn) = line; | |
1382 | } | |
1383 | ||
61ff7bd5 | 1384 | /* After a block was scheduled, insert line notes into the insns list. |
2295df67 | 1385 | HEAD and TAIL are the boundaries of the block in which notes should |
04641143 | 1386 | be processed. */ |
3eb9a99d | 1387 | |
7a31a7bd | 1388 | void |
61ff7bd5 | 1389 | restore_line_notes (head, tail) |
2295df67 | 1390 | rtx head, tail; |
3eb9a99d | 1391 | { |
1392 | rtx line, note, prev, new; | |
1393 | int added_notes = 0; | |
2295df67 | 1394 | rtx next_tail, insn; |
3eb9a99d | 1395 | |
2295df67 | 1396 | head = head; |
1397 | next_tail = NEXT_INSN (tail); | |
3eb9a99d | 1398 | |
1399 | /* Determine the current line-number. We want to know the current | |
1400 | line number of the first insn of the block here, in case it is | |
1401 | different from the true line number that was saved earlier. If | |
1402 | different, then we need a line number note before the first insn | |
1403 | of this block. If it happens to be the same, then we don't want to | |
1404 | emit another line number note here. */ | |
1405 | for (line = head; line; line = PREV_INSN (line)) | |
1406 | if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0) | |
1407 | break; | |
1408 | ||
1409 | /* Walk the insns keeping track of the current line-number and inserting | |
1410 | the line-number notes as needed. */ | |
1411 | for (insn = head; insn != next_tail; insn = NEXT_INSN (insn)) | |
1412 | if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0) | |
1413 | line = insn; | |
1414 | /* This used to emit line number notes before every non-deleted note. | |
1415 | However, this confuses a debugger, because line notes not separated | |
1416 | by real instructions all end up at the same address. I can find no | |
1417 | use for line number notes before other notes, so none are emitted. */ | |
1418 | else if (GET_CODE (insn) != NOTE | |
2295df67 | 1419 | && INSN_UID (insn) < old_max_uid |
3eb9a99d | 1420 | && (note = LINE_NOTE (insn)) != 0 |
1421 | && note != line | |
1422 | && (line == 0 | |
1423 | || NOTE_LINE_NUMBER (note) != NOTE_LINE_NUMBER (line) | |
1424 | || NOTE_SOURCE_FILE (note) != NOTE_SOURCE_FILE (line))) | |
1425 | { | |
1426 | line = note; | |
1427 | prev = PREV_INSN (insn); | |
1428 | if (LINE_NOTE (note)) | |
1429 | { | |
1430 | /* Re-use the original line-number note. */ | |
1431 | LINE_NOTE (note) = 0; | |
1432 | PREV_INSN (note) = prev; | |
1433 | NEXT_INSN (prev) = note; | |
1434 | PREV_INSN (insn) = note; | |
1435 | NEXT_INSN (note) = insn; | |
1436 | } | |
1437 | else | |
1438 | { | |
1439 | added_notes++; | |
1440 | new = emit_note_after (NOTE_LINE_NUMBER (note), prev); | |
1441 | NOTE_SOURCE_FILE (new) = NOTE_SOURCE_FILE (note); | |
1442 | RTX_INTEGRATED_P (new) = RTX_INTEGRATED_P (note); | |
1443 | } | |
1444 | } | |
1445 | if (sched_verbose && added_notes) | |
d0768316 | 1446 | fprintf (sched_dump, ";; added %d line-number notes\n", added_notes); |
3eb9a99d | 1447 | } |
1448 | ||
1449 | /* After scheduling the function, delete redundant line notes from the | |
1450 | insns list. */ | |
1451 | ||
7a31a7bd | 1452 | void |
3eb9a99d | 1453 | rm_redundant_line_notes () |
1454 | { | |
1455 | rtx line = 0; | |
1456 | rtx insn = get_insns (); | |
1457 | int active_insn = 0; | |
1458 | int notes = 0; | |
1459 | ||
1460 | /* Walk the insns deleting redundant line-number notes. Many of these | |
1461 | are already present. The remainder tend to occur at basic | |
1462 | block boundaries. */ | |
1463 | for (insn = get_last_insn (); insn; insn = PREV_INSN (insn)) | |
1464 | if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0) | |
1465 | { | |
1466 | /* If there are no active insns following, INSN is redundant. */ | |
1467 | if (active_insn == 0) | |
1468 | { | |
1469 | notes++; | |
1470 | NOTE_SOURCE_FILE (insn) = 0; | |
1471 | NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED; | |
1472 | } | |
1473 | /* If the line number is unchanged, LINE is redundant. */ | |
1474 | else if (line | |
1475 | && NOTE_LINE_NUMBER (line) == NOTE_LINE_NUMBER (insn) | |
1476 | && NOTE_SOURCE_FILE (line) == NOTE_SOURCE_FILE (insn)) | |
1477 | { | |
1478 | notes++; | |
1479 | NOTE_SOURCE_FILE (line) = 0; | |
1480 | NOTE_LINE_NUMBER (line) = NOTE_INSN_DELETED; | |
1481 | line = insn; | |
1482 | } | |
1483 | else | |
1484 | line = insn; | |
1485 | active_insn = 0; | |
1486 | } | |
1487 | else if (!((GET_CODE (insn) == NOTE | |
1488 | && NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED) | |
1489 | || (GET_CODE (insn) == INSN | |
1490 | && (GET_CODE (PATTERN (insn)) == USE | |
1491 | || GET_CODE (PATTERN (insn)) == CLOBBER)))) | |
1492 | active_insn++; | |
1493 | ||
1494 | if (sched_verbose && notes) | |
d0768316 | 1495 | fprintf (sched_dump, ";; deleted %d line-number notes\n", notes); |
3eb9a99d | 1496 | } |
1497 | ||
2295df67 | 1498 | /* Delete notes between HEAD and TAIL and put them in the chain |
3eb9a99d | 1499 | of notes ended by NOTE_LIST. */ |
1500 | ||
7a31a7bd | 1501 | void |
3eb9a99d | 1502 | rm_other_notes (head, tail) |
1503 | rtx head; | |
1504 | rtx tail; | |
1505 | { | |
1506 | rtx next_tail; | |
1507 | rtx insn; | |
1508 | ||
7a31a7bd | 1509 | note_list = 0; |
9204e736 | 1510 | if (head == tail && (! INSN_P (head))) |
3eb9a99d | 1511 | return; |
1512 | ||
1513 | next_tail = NEXT_INSN (tail); | |
1514 | for (insn = head; insn != next_tail; insn = NEXT_INSN (insn)) | |
1515 | { | |
1516 | rtx prev; | |
1517 | ||
1518 | /* Farm out notes, and maybe save them in NOTE_LIST. | |
1519 | This is needed to keep the debugger from | |
1520 | getting completely deranged. */ | |
1521 | if (GET_CODE (insn) == NOTE) | |
1522 | { | |
1523 | prev = insn; | |
1524 | ||
1525 | insn = unlink_other_notes (insn, next_tail); | |
1526 | ||
1527 | if (prev == tail) | |
1528 | abort (); | |
1529 | if (prev == head) | |
1530 | abort (); | |
1531 | if (insn == next_tail) | |
1532 | abort (); | |
1533 | } | |
1534 | } | |
1535 | } | |
1536 | ||
c4cd519a | 1537 | /* Functions for computation of registers live/usage info. */ |
3eb9a99d | 1538 | |
ba57cb24 | 1539 | /* Calculate INSN_REG_WEIGHT for all insns of a block. */ |
3eb9a99d | 1540 | |
1541 | static void | |
def93098 | 1542 | find_insn_reg_weight (b) |
896c2bfe | 1543 | int b; |
3eb9a99d | 1544 | { |
1545 | rtx insn, next_tail, head, tail; | |
3eb9a99d | 1546 | |
def93098 | 1547 | get_block_head_tail (b, &head, &tail); |
3eb9a99d | 1548 | next_tail = NEXT_INSN (tail); |
1549 | ||
1550 | for (insn = head; insn != next_tail; insn = NEXT_INSN (insn)) | |
1551 | { | |
3eb9a99d | 1552 | int reg_weight = 0; |
ba57cb24 | 1553 | rtx x; |
3eb9a99d | 1554 | |
1555 | /* Handle register life information. */ | |
9204e736 | 1556 | if (! INSN_P (insn)) |
3eb9a99d | 1557 | continue; |
1558 | ||
ba57cb24 | 1559 | /* Increment weight for each register born here. */ |
1560 | x = PATTERN (insn); | |
1561 | if ((GET_CODE (x) == SET || GET_CODE (x) == CLOBBER) | |
1562 | && register_operand (SET_DEST (x), VOIDmode)) | |
1563 | reg_weight++; | |
1564 | else if (GET_CODE (x) == PARALLEL) | |
3eb9a99d | 1565 | { |
ba57cb24 | 1566 | int j; |
1567 | for (j = XVECLEN (x, 0) - 1; j >= 0; j--) | |
1568 | { | |
1569 | x = XVECEXP (PATTERN (insn), 0, j); | |
1570 | if ((GET_CODE (x) == SET || GET_CODE (x) == CLOBBER) | |
1571 | && register_operand (SET_DEST (x), VOIDmode)) | |
1572 | reg_weight++; | |
1573 | } | |
3eb9a99d | 1574 | } |
1575 | ||
ba57cb24 | 1576 | /* Decrement weight for each register that dies here. */ |
1577 | for (x = REG_NOTES (insn); x; x = XEXP (x, 1)) | |
3eb9a99d | 1578 | { |
ba57cb24 | 1579 | if (REG_NOTE_KIND (x) == REG_DEAD |
1580 | || REG_NOTE_KIND (x) == REG_UNUSED) | |
1581 | reg_weight--; | |
3eb9a99d | 1582 | } |
1583 | ||
ba57cb24 | 1584 | INSN_REG_WEIGHT (insn) = reg_weight; |
3eb9a99d | 1585 | } |
3eb9a99d | 1586 | } |
1587 | ||
c4cd519a | 1588 | /* Scheduling clock, modified in schedule_block() and queue_to_ready (). */ |
3eb9a99d | 1589 | static int clock_var; |
1590 | ||
1591 | /* Move insns that became ready to fire from queue to ready list. */ | |
1592 | ||
30b1ec30 | 1593 | static void |
1594 | queue_to_ready (ready) | |
1595 | struct ready_list *ready; | |
3eb9a99d | 1596 | { |
1597 | rtx insn; | |
1598 | rtx link; | |
1599 | ||
1600 | q_ptr = NEXT_Q (q_ptr); | |
1601 | ||
1602 | /* Add all pending insns that can be scheduled without stalls to the | |
7a31a7bd | 1603 | ready list. */ |
1604 | for (link = insn_queue[q_ptr]; link; link = XEXP (link, 1)) | |
1605 | { | |
1606 | insn = XEXP (link, 0); | |
1607 | q_size -= 1; | |
c2069298 | 1608 | |
7a31a7bd | 1609 | if (sched_verbose >= 2) |
1610 | fprintf (sched_dump, ";;\t\tQ-->Ready: insn %s: ", | |
1611 | (*current_sched_info->print_insn) (insn, 0)); | |
c2069298 | 1612 | |
7a31a7bd | 1613 | ready_add (ready, insn); |
1614 | if (sched_verbose >= 2) | |
1615 | fprintf (sched_dump, "moving to ready without stalls\n"); | |
c2069298 | 1616 | } |
7a31a7bd | 1617 | insn_queue[q_ptr] = 0; |
1618 | ||
1619 | /* If there are no ready insns, stall until one is ready and add all | |
1620 | of the pending insns at that point to the ready list. */ | |
1621 | if (ready->n_ready == 0) | |
c2069298 | 1622 | { |
19cb6b50 | 1623 | int stalls; |
c2069298 | 1624 | |
bea4bad2 | 1625 | for (stalls = 1; stalls <= MAX_INSN_QUEUE_INDEX; stalls++) |
7a31a7bd | 1626 | { |
1627 | if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)])) | |
1628 | { | |
1629 | for (; link; link = XEXP (link, 1)) | |
1630 | { | |
1631 | insn = XEXP (link, 0); | |
1632 | q_size -= 1; | |
c2069298 | 1633 | |
7a31a7bd | 1634 | if (sched_verbose >= 2) |
1635 | fprintf (sched_dump, ";;\t\tQ-->Ready: insn %s: ", | |
1636 | (*current_sched_info->print_insn) (insn, 0)); | |
c2069298 | 1637 | |
7a31a7bd | 1638 | ready_add (ready, insn); |
1639 | if (sched_verbose >= 2) | |
1640 | fprintf (sched_dump, "moving to ready with %d stalls\n", stalls); | |
1641 | } | |
1642 | insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = 0; | |
c2069298 | 1643 | |
bea4bad2 | 1644 | advance_one_cycle (); |
1645 | ||
1646 | break; | |
7a31a7bd | 1647 | } |
bea4bad2 | 1648 | |
1649 | advance_one_cycle (); | |
7a31a7bd | 1650 | } |
c2069298 | 1651 | |
bea4bad2 | 1652 | if ((!targetm.sched.use_dfa_pipeline_interface |
1653 | || !(*targetm.sched.use_dfa_pipeline_interface) ()) | |
1654 | && sched_verbose && stalls) | |
7a31a7bd | 1655 | visualize_stall_cycles (stalls); |
bea4bad2 | 1656 | |
7a31a7bd | 1657 | q_ptr = NEXT_Q_AFTER (q_ptr, stalls); |
1658 | clock_var += stalls; | |
c2069298 | 1659 | } |
c2069298 | 1660 | } |
1661 | ||
7a31a7bd | 1662 | /* Print the ready list for debugging purposes. Callable from debugger. */ |
c2069298 | 1663 | |
7a31a7bd | 1664 | static void |
1665 | debug_ready_list (ready) | |
1666 | struct ready_list *ready; | |
c2069298 | 1667 | { |
7a31a7bd | 1668 | rtx *p; |
1669 | int i; | |
c2069298 | 1670 | |
7a31a7bd | 1671 | if (ready->n_ready == 0) |
bea4bad2 | 1672 | { |
1673 | fprintf (sched_dump, "\n"); | |
1674 | return; | |
1675 | } | |
c2069298 | 1676 | |
7a31a7bd | 1677 | p = ready_lastpos (ready); |
1678 | for (i = 0; i < ready->n_ready; i++) | |
1679 | fprintf (sched_dump, " %s", (*current_sched_info->print_insn) (p[i], 0)); | |
1680 | fprintf (sched_dump, "\n"); | |
1681 | } | |
c2069298 | 1682 | |
c4cd519a | 1683 | /* move_insn1: Remove INSN from insn chain, and link it after LAST insn. */ |
3eb9a99d | 1684 | |
1685 | static rtx | |
1686 | move_insn1 (insn, last) | |
1687 | rtx insn, last; | |
1688 | { | |
1689 | NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn); | |
1690 | PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn); | |
1691 | ||
1692 | NEXT_INSN (insn) = NEXT_INSN (last); | |
1693 | PREV_INSN (NEXT_INSN (last)) = insn; | |
1694 | ||
1695 | NEXT_INSN (last) = insn; | |
1696 | PREV_INSN (insn) = last; | |
1697 | ||
1698 | return insn; | |
1699 | } | |
1700 | ||
9239aee6 | 1701 | /* Search INSN for REG_SAVE_NOTE note pairs for |
3eb9a99d | 1702 | NOTE_INSN_{LOOP,EHREGION}_{BEG,END}; and convert them back into |
ba57cb24 | 1703 | NOTEs. The REG_SAVE_NOTE note following first one is contains the |
1704 | saved value for NOTE_BLOCK_NUMBER which is useful for | |
3eb9a99d | 1705 | NOTE_INSN_EH_REGION_{BEG,END} NOTEs. LAST is the last instruction |
1706 | output by the instruction scheduler. Return the new value of LAST. */ | |
1707 | ||
1708 | static rtx | |
1709 | reemit_notes (insn, last) | |
1710 | rtx insn; | |
1711 | rtx last; | |
1712 | { | |
1713 | rtx note, retval; | |
1714 | ||
1715 | retval = last; | |
1716 | for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) | |
1717 | { | |
ba57cb24 | 1718 | if (REG_NOTE_KIND (note) == REG_SAVE_NOTE) |
3eb9a99d | 1719 | { |
87e9bf87 | 1720 | enum insn_note note_type = INTVAL (XEXP (note, 0)); |
1721 | ||
f16b6102 | 1722 | last = emit_note_before (note_type, last); |
1723 | remove_note (insn, note); | |
1724 | note = XEXP (note, 1); | |
1725 | if (note_type == NOTE_INSN_EH_REGION_BEG | |
1726 | || note_type == NOTE_INSN_EH_REGION_END) | |
1727 | NOTE_EH_HANDLER (last) = INTVAL (XEXP (note, 0)); | |
3eb9a99d | 1728 | remove_note (insn, note); |
1729 | } | |
1730 | } | |
1731 | return retval; | |
1732 | } | |
1733 | ||
1734 | /* Move INSN, and all insns which should be issued before it, | |
44f831ee | 1735 | due to SCHED_GROUP_P flag. Reemit notes if needed. |
1736 | ||
1737 | Return the last insn emitted by the scheduler, which is the | |
1738 | return value from the first call to reemit_notes. */ | |
3eb9a99d | 1739 | |
1740 | static rtx | |
1741 | move_insn (insn, last) | |
1742 | rtx insn, last; | |
1743 | { | |
44f831ee | 1744 | rtx retval = NULL; |
3eb9a99d | 1745 | |
44f831ee | 1746 | /* If INSN has SCHED_GROUP_P set, then issue it and any other |
1747 | insns with SCHED_GROUP_P set first. */ | |
3eb9a99d | 1748 | while (SCHED_GROUP_P (insn)) |
1749 | { | |
1750 | rtx prev = PREV_INSN (insn); | |
44f831ee | 1751 | |
1752 | /* Move a SCHED_GROUP_P insn. */ | |
3eb9a99d | 1753 | move_insn1 (insn, last); |
44f831ee | 1754 | /* If this is the first call to reemit_notes, then record |
1755 | its return value. */ | |
1756 | if (retval == NULL_RTX) | |
1757 | retval = reemit_notes (insn, insn); | |
1758 | else | |
1759 | reemit_notes (insn, insn); | |
cb0e348a | 1760 | /* Consume SCHED_GROUP_P flag. */ |
1761 | SCHED_GROUP_P (insn) = 0; | |
3eb9a99d | 1762 | insn = prev; |
1763 | } | |
1764 | ||
44f831ee | 1765 | /* Now move the first non SCHED_GROUP_P insn. */ |
3eb9a99d | 1766 | move_insn1 (insn, last); |
44f831ee | 1767 | |
1768 | /* If this is the first call to reemit_notes, then record | |
1769 | its return value. */ | |
1770 | if (retval == NULL_RTX) | |
1771 | retval = reemit_notes (insn, insn); | |
1772 | else | |
1773 | reemit_notes (insn, insn); | |
1774 | ||
1775 | return retval; | |
3eb9a99d | 1776 | } |
1777 | ||
bea4bad2 | 1778 | /* The following function returns maximal (or close to maximal) number |
1779 | of insns which can be issued on the same cycle and one of which | |
1780 | insns is insns with the best rank (the last insn in READY). To | |
1781 | make this function tries different samples of ready insns. READY | |
1782 | is current queue `ready'. Global array READY_TRY reflects what | |
1783 | insns are already issued in this try. STATE is current processor | |
1784 | state. If the function returns nonzero, INDEX will contain index | |
1785 | of the best insn in READY. The following function is used only for | |
1786 | first cycle multipass scheduling. */ | |
1787 | ||
1788 | static int | |
1789 | max_issue (ready, state, index) | |
1790 | struct ready_list *ready; | |
1791 | state_t state; | |
1792 | int *index; | |
1793 | { | |
1794 | int i, best, n, temp_index, delay; | |
1795 | state_t temp_state; | |
1796 | rtx insn; | |
1797 | int max_lookahead = (*targetm.sched.first_cycle_multipass_dfa_lookahead) (); | |
1798 | ||
1799 | if (state_dead_lock_p (state)) | |
1800 | return 0; | |
1801 | ||
1802 | temp_state = alloca (dfa_state_size); | |
1803 | best = 0; | |
1804 | ||
1805 | for (i = 0; i < ready->n_ready; i++) | |
1806 | if (!ready_try [i]) | |
1807 | { | |
1808 | insn = ready_element (ready, i); | |
1809 | ||
1810 | if (INSN_CODE (insn) < 0) | |
1811 | continue; | |
1812 | ||
1813 | memcpy (temp_state, state, dfa_state_size); | |
1814 | ||
1815 | delay = state_transition (temp_state, insn); | |
1816 | ||
1817 | if (delay == 0) | |
1818 | { | |
1819 | if (!targetm.sched.dfa_bubble) | |
1820 | continue; | |
1821 | else | |
1822 | { | |
1823 | int j; | |
1824 | rtx bubble; | |
1825 | ||
1826 | for (j = 0; | |
1827 | (bubble = (*targetm.sched.dfa_bubble) (j)) != NULL_RTX; | |
1828 | j++) | |
1829 | if (state_transition (temp_state, bubble) < 0 | |
1830 | && state_transition (temp_state, insn) < 0) | |
1831 | break; | |
1832 | ||
1833 | if (bubble == NULL_RTX) | |
1834 | continue; | |
1835 | } | |
1836 | } | |
1837 | else if (delay > 0) | |
1838 | continue; | |
1839 | ||
1840 | --max_lookahead; | |
1841 | ||
1842 | if (max_lookahead < 0) | |
1843 | break; | |
1844 | ||
1845 | ready_try [i] = 1; | |
1846 | ||
1847 | n = max_issue (ready, temp_state, &temp_index); | |
1848 | if (n > 0 || ready_try[0]) | |
1849 | n += 1; | |
1850 | ||
1851 | if (best < n) | |
1852 | { | |
1853 | best = n; | |
1854 | *index = i; | |
1855 | } | |
1856 | ready_try [i] = 0; | |
1857 | } | |
1858 | ||
1859 | return best; | |
1860 | } | |
1861 | ||
1862 | /* The following function chooses insn from READY and modifies | |
1863 | *N_READY and READY. The following function is used only for first | |
1864 | cycle multipass scheduling. */ | |
1865 | ||
1866 | static rtx | |
1867 | choose_ready (ready) | |
1868 | struct ready_list *ready; | |
1869 | { | |
1870 | if (!targetm.sched.first_cycle_multipass_dfa_lookahead | |
1871 | || (*targetm.sched.first_cycle_multipass_dfa_lookahead) () <= 0) | |
1872 | return ready_remove_first (ready); | |
1873 | else | |
1874 | { | |
1875 | /* Try to choose the better insn. */ | |
1876 | int index; | |
1877 | ||
1878 | if (max_issue (ready, curr_state, &index) == 0) | |
1879 | return ready_remove_first (ready); | |
1880 | else | |
1881 | return ready_remove (ready, index); | |
1882 | } | |
1883 | } | |
1884 | ||
0b923690 | 1885 | /* Called from backends from targetm.sched.reorder to emit stuff into |
1886 | the instruction stream. */ | |
1887 | ||
1888 | rtx | |
1889 | sched_emit_insn (pat) | |
1890 | rtx pat; | |
1891 | { | |
1892 | rtx insn = emit_insn_after (pat, last_scheduled_insn); | |
1893 | last_scheduled_insn = insn; | |
1894 | return insn; | |
1895 | } | |
1896 | ||
7a31a7bd | 1897 | /* Use forward list scheduling to rearrange insns of block B in region RGN, |
c2069298 | 1898 | possibly bringing insns from subsequent blocks in the same region. */ |
3eb9a99d | 1899 | |
7a31a7bd | 1900 | void |
1901 | schedule_block (b, rgn_n_insns) | |
1902 | int b; | |
3eb9a99d | 1903 | int rgn_n_insns; |
1904 | { | |
30b1ec30 | 1905 | struct ready_list ready; |
bea4bad2 | 1906 | int first_cycle_insn_p; |
3eb9a99d | 1907 | int can_issue_more; |
bea4bad2 | 1908 | state_t temp_state = NULL; /* It is used for multipass scheduling. */ |
3eb9a99d | 1909 | |
c4cd519a | 1910 | /* Head/tail info for this block. */ |
c2069298 | 1911 | rtx prev_head = current_sched_info->prev_head; |
1912 | rtx next_tail = current_sched_info->next_tail; | |
1913 | rtx head = NEXT_INSN (prev_head); | |
1914 | rtx tail = PREV_INSN (next_tail); | |
3eb9a99d | 1915 | |
6106ad68 | 1916 | /* We used to have code to avoid getting parameters moved from hard |
1917 | argument registers into pseudos. | |
3eb9a99d | 1918 | |
6106ad68 | 1919 | However, it was removed when it proved to be of marginal benefit |
1920 | and caused problems because schedule_block and compute_forward_dependences | |
1921 | had different notions of what the "head" insn was. */ | |
3eb9a99d | 1922 | |
9204e736 | 1923 | if (head == tail && (! INSN_P (head))) |
c2069298 | 1924 | abort (); |
3eb9a99d | 1925 | |
c4cd519a | 1926 | /* Debug info. */ |
3eb9a99d | 1927 | if (sched_verbose) |
1928 | { | |
d0768316 | 1929 | fprintf (sched_dump, ";; ======================================================\n"); |
1930 | fprintf (sched_dump, | |
3eb9a99d | 1931 | ";; -- basic block %d from %d to %d -- %s reload\n", |
2295df67 | 1932 | b, INSN_UID (head), INSN_UID (tail), |
3eb9a99d | 1933 | (reload_completed ? "after" : "before")); |
d0768316 | 1934 | fprintf (sched_dump, ";; ======================================================\n"); |
1935 | fprintf (sched_dump, "\n"); | |
3eb9a99d | 1936 | |
10c06114 | 1937 | visualize_alloc (); |
3eb9a99d | 1938 | init_block_visualization (); |
1939 | } | |
1940 | ||
bea4bad2 | 1941 | if (targetm.sched.use_dfa_pipeline_interface |
1942 | && (*targetm.sched.use_dfa_pipeline_interface) ()) | |
1943 | state_reset (curr_state); | |
1944 | else | |
1945 | clear_units (); | |
3eb9a99d | 1946 | |
c4cd519a | 1947 | /* Allocate the ready list. */ |
747af5e7 | 1948 | ready.veclen = rgn_n_insns + 1 + issue_rate; |
30b1ec30 | 1949 | ready.first = ready.veclen - 1; |
1950 | ready.vec = (rtx *) xmalloc (ready.veclen * sizeof (rtx)); | |
1951 | ready.n_ready = 0; | |
3eb9a99d | 1952 | |
bea4bad2 | 1953 | if (targetm.sched.use_dfa_pipeline_interface |
1954 | && (*targetm.sched.use_dfa_pipeline_interface) ()) | |
1955 | { | |
1956 | /* It is used for first cycle multipass scheduling. */ | |
1957 | temp_state = alloca (dfa_state_size); | |
1958 | ready_try = (char *) xmalloc ((rgn_n_insns + 1) * sizeof (char)); | |
1959 | memset (ready_try, 0, (rgn_n_insns + 1) * sizeof (char)); | |
1960 | } | |
1961 | ||
c2069298 | 1962 | (*current_sched_info->init_ready_list) (&ready); |
3eb9a99d | 1963 | |
747af5e7 | 1964 | if (targetm.sched.md_init) |
1965 | (*targetm.sched.md_init) (sched_dump, sched_verbose, ready.veclen); | |
663b9536 | 1966 | |
0b923690 | 1967 | /* We start inserting insns after PREV_HEAD. */ |
1968 | last_scheduled_insn = prev_head; | |
3eb9a99d | 1969 | |
c2069298 | 1970 | /* Initialize INSN_QUEUE. Q_SIZE is the total number of insns in the |
1971 | queue. */ | |
3eb9a99d | 1972 | q_ptr = 0; |
1973 | q_size = 0; | |
bea4bad2 | 1974 | |
1975 | if (!targetm.sched.use_dfa_pipeline_interface | |
1976 | || !(*targetm.sched.use_dfa_pipeline_interface) ()) | |
1977 | max_insn_queue_index_macro_value = INSN_QUEUE_SIZE - 1; | |
1978 | else | |
1979 | max_insn_queue_index_macro_value = max_insn_queue_index; | |
1980 | ||
1981 | insn_queue = (rtx *) alloca ((MAX_INSN_QUEUE_INDEX + 1) * sizeof (rtx)); | |
1982 | memset ((char *) insn_queue, 0, (MAX_INSN_QUEUE_INDEX + 1) * sizeof (rtx)); | |
1983 | last_clock_var = -1; | |
3eb9a99d | 1984 | |
de206697 | 1985 | /* Start just before the beginning of time. */ |
1986 | clock_var = -1; | |
1987 | ||
c4cd519a | 1988 | /* Loop until all the insns in BB are scheduled. */ |
c2069298 | 1989 | while ((*current_sched_info->schedule_more_p) ()) |
3eb9a99d | 1990 | { |
3eb9a99d | 1991 | clock_var++; |
1992 | ||
bea4bad2 | 1993 | advance_one_cycle (); |
1994 | ||
3eb9a99d | 1995 | /* Add to the ready list all pending insns that can be issued now. |
1996 | If there are no ready insns, increment clock until one | |
1997 | is ready and add all pending insns at that point to the ready | |
1998 | list. */ | |
30b1ec30 | 1999 | queue_to_ready (&ready); |
3eb9a99d | 2000 | |
30b1ec30 | 2001 | if (ready.n_ready == 0) |
3eb9a99d | 2002 | abort (); |
2003 | ||
2004 | if (sched_verbose >= 2) | |
2005 | { | |
d0768316 | 2006 | fprintf (sched_dump, ";;\t\tReady list after queue_to_ready: "); |
30b1ec30 | 2007 | debug_ready_list (&ready); |
3eb9a99d | 2008 | } |
2009 | ||
de206697 | 2010 | /* Sort the ready list based on priority. */ |
30b1ec30 | 2011 | ready_sort (&ready); |
de206697 | 2012 | |
7a31a7bd | 2013 | /* Allow the target to reorder the list, typically for |
2014 | better instruction bundling. */ | |
747af5e7 | 2015 | if (targetm.sched.reorder) |
2016 | can_issue_more = | |
2017 | (*targetm.sched.reorder) (sched_dump, sched_verbose, | |
2018 | ready_lastpos (&ready), | |
2019 | &ready.n_ready, clock_var); | |
2020 | else | |
2021 | can_issue_more = issue_rate; | |
9bf1996d | 2022 | |
bea4bad2 | 2023 | first_cycle_insn_p = 1; |
2024 | for (;;) | |
9bf1996d | 2025 | { |
bea4bad2 | 2026 | rtx insn; |
2027 | int cost; | |
2028 | ||
0bc18d66 | 2029 | if (sched_verbose >= 2) |
bea4bad2 | 2030 | { |
2031 | fprintf (sched_dump, ";;\tReady list (t =%3d): ", | |
2032 | clock_var); | |
2033 | debug_ready_list (&ready); | |
2034 | } | |
2035 | ||
2036 | if (!targetm.sched.use_dfa_pipeline_interface | |
2037 | || !(*targetm.sched.use_dfa_pipeline_interface) ()) | |
2038 | { | |
2039 | if (ready.n_ready == 0 || !can_issue_more | |
2040 | || !(*current_sched_info->schedule_more_p) ()) | |
2041 | break; | |
2042 | insn = choose_ready (&ready); | |
2043 | cost = actual_hazard (insn_unit (insn), insn, clock_var, 0); | |
2044 | } | |
2045 | else | |
2046 | { | |
2047 | if (ready.n_ready == 0 || !can_issue_more | |
2048 | || state_dead_lock_p (curr_state) | |
2049 | || !(*current_sched_info->schedule_more_p) ()) | |
2050 | break; | |
2051 | ||
2052 | /* Select and remove the insn from the ready list. */ | |
2053 | insn = choose_ready (&ready); | |
2054 | ||
2055 | memcpy (temp_state, curr_state, dfa_state_size); | |
2056 | if (recog_memoized (insn) < 0) | |
2057 | { | |
2058 | if (!first_cycle_insn_p | |
2059 | && (GET_CODE (PATTERN (insn)) == ASM_INPUT | |
2060 | || asm_noperands (PATTERN (insn)) >= 0)) | |
2061 | /* This is asm insn which is tryed to be issued on the | |
2062 | cycle not first. Issue it on the next cycle. */ | |
2063 | cost = 1; | |
2064 | else | |
2065 | /* A USE insn, or something else we don't need to | |
2066 | understand. We can't pass these directly to | |
2067 | state_transition because it will trigger a | |
2068 | fatal error for unrecognizable insns. */ | |
2069 | cost = 0; | |
2070 | } | |
2071 | else | |
2072 | { | |
2073 | cost = state_transition (temp_state, insn); | |
2074 | ||
2075 | if (targetm.sched.first_cycle_multipass_dfa_lookahead | |
2076 | && targetm.sched.dfa_bubble) | |
2077 | { | |
2078 | if (cost == 0) | |
2079 | { | |
2080 | int j; | |
2081 | rtx bubble; | |
2082 | ||
2083 | for (j = 0; | |
2084 | (bubble = (*targetm.sched.dfa_bubble) (j)) | |
2085 | != NULL_RTX; | |
2086 | j++) | |
2087 | { | |
2088 | memcpy (temp_state, curr_state, dfa_state_size); | |
2089 | ||
2090 | if (state_transition (temp_state, bubble) < 0 | |
2091 | && state_transition (temp_state, insn) < 0) | |
2092 | break; | |
2093 | } | |
2094 | ||
2095 | if (bubble != NULL_RTX) | |
2096 | { | |
2097 | if (insert_schedule_bubbles_p) | |
2098 | { | |
2099 | rtx copy; | |
2100 | ||
2101 | copy = copy_rtx (PATTERN (bubble)); | |
2102 | emit_insn_after (copy, last_scheduled_insn); | |
2103 | last_scheduled_insn | |
2104 | = NEXT_INSN (last_scheduled_insn); | |
2105 | INSN_CODE (last_scheduled_insn) | |
2106 | = INSN_CODE (bubble); | |
2107 | ||
2108 | /* Annotate the same for the first insns | |
2109 | scheduling by using mode. */ | |
2110 | PUT_MODE (last_scheduled_insn, | |
2111 | (clock_var > last_clock_var | |
2112 | ? clock_var - last_clock_var | |
2113 | : VOIDmode)); | |
2114 | last_clock_var = clock_var; | |
2115 | ||
2116 | if (sched_verbose >= 2) | |
2117 | { | |
2118 | fprintf (sched_dump, | |
2119 | ";;\t\t--> scheduling bubble insn <<<%d>>>:reservation ", | |
2120 | INSN_UID (last_scheduled_insn)); | |
2121 | ||
2122 | if (recog_memoized (last_scheduled_insn) | |
2123 | < 0) | |
2124 | fprintf (sched_dump, "nothing"); | |
2125 | else | |
2126 | print_reservation | |
2127 | (sched_dump, last_scheduled_insn); | |
2128 | ||
2129 | fprintf (sched_dump, "\n"); | |
2130 | } | |
2131 | } | |
2132 | cost = -1; | |
2133 | } | |
2134 | } | |
2135 | } | |
2136 | ||
2137 | if (cost < 0) | |
2138 | cost = 0; | |
2139 | else if (cost == 0) | |
2140 | cost = 1; | |
2141 | } | |
2142 | } | |
9bf1996d | 2143 | |
9bf1996d | 2144 | |
7a31a7bd | 2145 | if (cost >= 1) |
2146 | { | |
2147 | queue_insn (insn, cost); | |
2148 | continue; | |
2149 | } | |
9bf1996d | 2150 | |
7a31a7bd | 2151 | if (! (*current_sched_info->can_schedule_ready_p) (insn)) |
2152 | goto next; | |
3eb9a99d | 2153 | |
0b923690 | 2154 | last_scheduled_insn = move_insn (insn, last_scheduled_insn); |
3eb9a99d | 2155 | |
bea4bad2 | 2156 | if (targetm.sched.use_dfa_pipeline_interface |
2157 | && (*targetm.sched.use_dfa_pipeline_interface) ()) | |
2158 | memcpy (curr_state, temp_state, dfa_state_size); | |
2159 | ||
747af5e7 | 2160 | if (targetm.sched.variable_issue) |
2161 | can_issue_more = | |
2162 | (*targetm.sched.variable_issue) (sched_dump, sched_verbose, | |
2163 | insn, can_issue_more); | |
37cde9fb | 2164 | /* A naked CLOBBER or USE generates no instruction, so do |
2165 | not count them against the issue rate. */ | |
2166 | else if (GET_CODE (PATTERN (insn)) != USE | |
2167 | && GET_CODE (PATTERN (insn)) != CLOBBER) | |
747af5e7 | 2168 | can_issue_more--; |
3eb9a99d | 2169 | |
7a31a7bd | 2170 | schedule_insn (insn, &ready, clock_var); |
3eb9a99d | 2171 | |
7a31a7bd | 2172 | next: |
bea4bad2 | 2173 | first_cycle_insn_p = 0; |
2174 | ||
747af5e7 | 2175 | if (targetm.sched.reorder2) |
2176 | { | |
2177 | /* Sort the ready list based on priority. */ | |
2178 | if (ready.n_ready > 0) | |
2179 | ready_sort (&ready); | |
2180 | can_issue_more = | |
2181 | (*targetm.sched.reorder2) (sched_dump,sched_verbose, | |
2182 | ready.n_ready | |
2183 | ? ready_lastpos (&ready) : NULL, | |
2184 | &ready.n_ready, clock_var); | |
2185 | } | |
7a31a7bd | 2186 | } |
3eb9a99d | 2187 | |
bea4bad2 | 2188 | if ((!targetm.sched.use_dfa_pipeline_interface |
2189 | || !(*targetm.sched.use_dfa_pipeline_interface) ()) | |
2190 | && sched_verbose) | |
2191 | /* Debug info. */ | |
7a31a7bd | 2192 | visualize_scheduled_insns (clock_var); |
2193 | } | |
3eb9a99d | 2194 | |
747af5e7 | 2195 | if (targetm.sched.md_finish) |
2196 | (*targetm.sched.md_finish) (sched_dump, sched_verbose); | |
2295df67 | 2197 | |
7a31a7bd | 2198 | /* Debug info. */ |
2199 | if (sched_verbose) | |
2200 | { | |
2201 | fprintf (sched_dump, ";;\tReady list (final): "); | |
2202 | debug_ready_list (&ready); | |
bea4bad2 | 2203 | if (!targetm.sched.use_dfa_pipeline_interface |
2204 | || !(*targetm.sched.use_dfa_pipeline_interface) ()) | |
2205 | print_block_visualization (""); | |
7a31a7bd | 2206 | } |
3eb9a99d | 2207 | |
7a31a7bd | 2208 | /* Sanity check -- queue must be empty now. Meaningless if region has |
2209 | multiple bbs. */ | |
2210 | if (current_sched_info->queue_must_finish_empty && q_size != 0) | |
2211 | abort (); | |
7ce0700a | 2212 | |
7a31a7bd | 2213 | /* Update head/tail boundaries. */ |
2214 | head = NEXT_INSN (prev_head); | |
0b923690 | 2215 | tail = last_scheduled_insn; |
7ce0700a | 2216 | |
78587df3 | 2217 | /* Restore-other-notes: NOTE_LIST is the end of a chain of notes |
2218 | previously found among the insns. Insert them at the beginning | |
2219 | of the insns. */ | |
2220 | if (note_list != 0) | |
2221 | { | |
2222 | rtx note_head = note_list; | |
2223 | ||
2224 | while (PREV_INSN (note_head)) | |
2225 | { | |
2226 | note_head = PREV_INSN (note_head); | |
2227 | } | |
2228 | ||
2229 | PREV_INSN (note_head) = PREV_INSN (head); | |
2230 | NEXT_INSN (PREV_INSN (head)) = note_head; | |
2231 | PREV_INSN (head) = note_list; | |
2232 | NEXT_INSN (note_list) = head; | |
2233 | head = note_head; | |
2234 | } | |
3eb9a99d | 2235 | |
7a31a7bd | 2236 | /* Debugging. */ |
2237 | if (sched_verbose) | |
3eb9a99d | 2238 | { |
7a31a7bd | 2239 | fprintf (sched_dump, ";; total time = %d\n;; new head = %d\n", |
2240 | clock_var, INSN_UID (head)); | |
2241 | fprintf (sched_dump, ";; new tail = %d\n\n", | |
2242 | INSN_UID (tail)); | |
2243 | visualize_free (); | |
2244 | } | |
3eb9a99d | 2245 | |
7a31a7bd | 2246 | current_sched_info->head = head; |
2247 | current_sched_info->tail = tail; | |
3eb9a99d | 2248 | |
7a31a7bd | 2249 | free (ready.vec); |
bea4bad2 | 2250 | |
2251 | if (targetm.sched.use_dfa_pipeline_interface | |
2252 | && (*targetm.sched.use_dfa_pipeline_interface) ()) | |
2253 | free (ready_try); | |
3eb9a99d | 2254 | } |
7a31a7bd | 2255 | \f |
c4cd519a | 2256 | /* Set_priorities: compute priority of each insn in the block. */ |
3eb9a99d | 2257 | |
7a31a7bd | 2258 | int |
2295df67 | 2259 | set_priorities (head, tail) |
2260 | rtx head, tail; | |
3eb9a99d | 2261 | { |
2262 | rtx insn; | |
2263 | int n_insn; | |
2264 | ||
3eb9a99d | 2265 | rtx prev_head; |
3eb9a99d | 2266 | |
3eb9a99d | 2267 | prev_head = PREV_INSN (head); |
2268 | ||
9204e736 | 2269 | if (head == tail && (! INSN_P (head))) |
3eb9a99d | 2270 | return 0; |
2271 | ||
2272 | n_insn = 0; | |
2273 | for (insn = tail; insn != prev_head; insn = PREV_INSN (insn)) | |
2274 | { | |
3eb9a99d | 2275 | if (GET_CODE (insn) == NOTE) |
2276 | continue; | |
2277 | ||
2278 | if (!(SCHED_GROUP_P (insn))) | |
2279 | n_insn++; | |
2280 | (void) priority (insn); | |
2281 | } | |
2282 | ||
2283 | return n_insn; | |
2284 | } | |
2285 | ||
d0768316 | 2286 | /* Initialize some global state for the scheduler. DUMP_FILE is to be used |
2287 | for debugging output. */ | |
3eb9a99d | 2288 | |
7a31a7bd | 2289 | void |
d0768316 | 2290 | sched_init (dump_file) |
3eb9a99d | 2291 | FILE *dump_file; |
2292 | { | |
4c26117a | 2293 | int luid; |
2294 | basic_block b; | |
3eb9a99d | 2295 | rtx insn; |
bea4bad2 | 2296 | int i; |
3eb9a99d | 2297 | |
c4cd519a | 2298 | /* Disable speculative loads in their presence if cc0 defined. */ |
3eb9a99d | 2299 | #ifdef HAVE_cc0 |
2300 | flag_schedule_speculative_load = 0; | |
2301 | #endif | |
2302 | ||
c4cd519a | 2303 | /* Set dump and sched_verbose for the desired debugging output. If no |
5c69f8a7 | 2304 | dump-file was specified, but -fsched-verbose=N (any N), print to stderr. |
2305 | For -fsched-verbose=N, N>=10, print everything to stderr. */ | |
3eb9a99d | 2306 | sched_verbose = sched_verbose_param; |
2307 | if (sched_verbose_param == 0 && dump_file) | |
2308 | sched_verbose = 1; | |
d0768316 | 2309 | sched_dump = ((sched_verbose_param >= 10 || !dump_file) |
2310 | ? stderr : dump_file); | |
3eb9a99d | 2311 | |
c4cd519a | 2312 | /* Initialize issue_rate. */ |
747af5e7 | 2313 | if (targetm.sched.issue_rate) |
2314 | issue_rate = (*targetm.sched.issue_rate) (); | |
2315 | else | |
2316 | issue_rate = 1; | |
3eb9a99d | 2317 | |
d696632f | 2318 | /* We use LUID 0 for the fake insn (UID 0) which holds dependencies for |
2319 | pseudos which do not cross calls. */ | |
d0768316 | 2320 | old_max_uid = get_max_uid () + 1; |
3eb9a99d | 2321 | |
d0768316 | 2322 | h_i_d = (struct haifa_insn_data *) xcalloc (old_max_uid, sizeof (*h_i_d)); |
3eb9a99d | 2323 | |
bea4bad2 | 2324 | for (i = 0; i < old_max_uid; i++) |
2325 | h_i_d [i].cost = -1; | |
2326 | ||
2327 | if (targetm.sched.use_dfa_pipeline_interface | |
2328 | && (*targetm.sched.use_dfa_pipeline_interface) ()) | |
2329 | { | |
2330 | if (targetm.sched.init_dfa_pre_cycle_insn) | |
2331 | (*targetm.sched.init_dfa_pre_cycle_insn) (); | |
2332 | ||
2333 | if (targetm.sched.init_dfa_post_cycle_insn) | |
2334 | (*targetm.sched.init_dfa_post_cycle_insn) (); | |
2335 | ||
2336 | if (targetm.sched.first_cycle_multipass_dfa_lookahead | |
2337 | && targetm.sched.init_dfa_bubbles) | |
2338 | (*targetm.sched.init_dfa_bubbles) (); | |
2339 | ||
2340 | dfa_start (); | |
2341 | dfa_state_size = state_size (); | |
2342 | curr_state = xmalloc (dfa_state_size); | |
2343 | } | |
2344 | ||
d28d5327 | 2345 | h_i_d[0].luid = 0; |
c45dd27b | 2346 | luid = 1; |
4c26117a | 2347 | FOR_EACH_BB (b) |
2348 | for (insn = b->head;; insn = NEXT_INSN (insn)) | |
3eb9a99d | 2349 | { |
62276683 | 2350 | INSN_LUID (insn) = luid; |
2351 | ||
2352 | /* Increment the next luid, unless this is a note. We don't | |
2353 | really need separate IDs for notes and we don't want to | |
2354 | schedule differently depending on whether or not there are | |
2355 | line-number notes, i.e., depending on whether or not we're | |
2356 | generating debugging information. */ | |
2357 | if (GET_CODE (insn) != NOTE) | |
2358 | ++luid; | |
2359 | ||
4c26117a | 2360 | if (insn == b->end) |
3eb9a99d | 2361 | break; |
2362 | } | |
896c2bfe | 2363 | |
d0768316 | 2364 | init_dependency_caches (luid); |
2365 | ||
d0768316 | 2366 | init_alias_analysis (); |
2367 | ||
2368 | if (write_symbols != NO_DEBUG) | |
f46b6d8a | 2369 | { |
d0768316 | 2370 | rtx line; |
2371 | ||
f20183e6 | 2372 | line_note_head = (rtx *) xcalloc (last_basic_block, sizeof (rtx)); |
d0768316 | 2373 | |
2374 | /* Save-line-note-head: | |
2375 | Determine the line-number at the start of each basic block. | |
2376 | This must be computed and saved now, because after a basic block's | |
2377 | predecessor has been scheduled, it is impossible to accurately | |
2378 | determine the correct line number for the first insn of the block. */ | |
2379 | ||
4c26117a | 2380 | FOR_EACH_BB (b) |
2295df67 | 2381 | { |
4c26117a | 2382 | for (line = b->head; line; line = PREV_INSN (line)) |
2295df67 | 2383 | if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0) |
2384 | { | |
4c26117a | 2385 | line_note_head[b->index] = line; |
2295df67 | 2386 | break; |
2387 | } | |
2388 | /* Do a forward search as well, since we won't get to see the first | |
2389 | notes in a basic block. */ | |
4c26117a | 2390 | for (line = b->head; line; line = NEXT_INSN (line)) |
d0768316 | 2391 | { |
2295df67 | 2392 | if (INSN_P (line)) |
2393 | break; | |
2394 | if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0) | |
4c26117a | 2395 | line_note_head[b->index] = line; |
d0768316 | 2396 | } |
2295df67 | 2397 | } |
f46b6d8a | 2398 | } |
3eb9a99d | 2399 | |
bea4bad2 | 2400 | if ((!targetm.sched.use_dfa_pipeline_interface |
2401 | || !(*targetm.sched.use_dfa_pipeline_interface) ()) | |
2402 | && sched_verbose) | |
2403 | /* Find units used in this function, for visualization. */ | |
d0768316 | 2404 | init_target_units (); |
2405 | ||
2406 | /* ??? Add a NOTE after the last insn of the last basic block. It is not | |
2407 | known why this is done. */ | |
2408 | ||
4c26117a | 2409 | insn = EXIT_BLOCK_PTR->prev_bb->end; |
d0768316 | 2410 | if (NEXT_INSN (insn) == 0 |
2411 | || (GET_CODE (insn) != NOTE | |
2412 | && GET_CODE (insn) != CODE_LABEL | |
42a9694b | 2413 | /* Don't emit a NOTE if it would end up before a BARRIER. */ |
2414 | && GET_CODE (NEXT_INSN (insn)) != BARRIER)) | |
9dda7915 | 2415 | { |
4c26117a | 2416 | emit_note_after (NOTE_INSN_DELETED, EXIT_BLOCK_PTR->prev_bb->end); |
9dda7915 | 2417 | /* Make insn to appear outside BB. */ |
4c26117a | 2418 | EXIT_BLOCK_PTR->prev_bb->end = PREV_INSN (EXIT_BLOCK_PTR->prev_bb->end); |
9dda7915 | 2419 | } |
d0768316 | 2420 | |
2421 | /* Compute INSN_REG_WEIGHT for all blocks. We must do this before | |
2422 | removing death notes. */ | |
4c26117a | 2423 | FOR_EACH_BB_REVERSE (b) |
2424 | find_insn_reg_weight (b->index); | |
d0768316 | 2425 | } |
2426 | ||
7a31a7bd | 2427 | /* Free global data used during insn scheduling. */ |
3eb9a99d | 2428 | |
d0768316 | 2429 | void |
7a31a7bd | 2430 | sched_finish () |
d0768316 | 2431 | { |
d28d5327 | 2432 | free (h_i_d); |
bea4bad2 | 2433 | |
2434 | if (targetm.sched.use_dfa_pipeline_interface | |
2435 | && (*targetm.sched.use_dfa_pipeline_interface) ()) | |
2436 | { | |
2437 | free (curr_state); | |
2438 | dfa_finish (); | |
2439 | } | |
7a31a7bd | 2440 | free_dependency_caches (); |
2441 | end_alias_analysis (); | |
d56876f5 | 2442 | if (write_symbols != NO_DEBUG) |
d28d5327 | 2443 | free (line_note_head); |
3eb9a99d | 2444 | } |
2445 | #endif /* INSN_SCHEDULING */ |