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