1 /* Instruction scheduling pass.
2 Copyright (C) 1992, 1993 Free Software Foundation, Inc.
3 Contributed by Michael Tiemann (tiemann@cygnus.com)
4 Enhanced by, and currently maintained by, Jim Wilson (wilson@cygnus.com)
6 This file is part of GNU CC.
8 GNU CC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2, or (at your option)
13 GNU CC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GNU CC; see the file COPYING. If not, write to
20 the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
22 /* Instruction scheduling pass.
24 This pass implements list scheduling within basic blocks. It is
25 run after flow analysis, but before register allocation. The
26 scheduler works as follows:
28 We compute insn priorities based on data dependencies. Flow
29 analysis only creates a fraction of the data-dependencies we must
30 observe: namely, only those dependencies which the combiner can be
31 expected to use. For this pass, we must therefore create the
32 remaining dependencies we need to observe: register dependencies,
33 memory dependencies, dependencies to keep function calls in order,
34 and the dependence between a conditional branch and the setting of
35 condition codes are all dealt with here.
37 The scheduler first traverses the data flow graph, starting with
38 the last instruction, and proceeding to the first, assigning
39 values to insn_priority as it goes. This sorts the instructions
40 topologically by data dependence.
42 Once priorities have been established, we order the insns using
43 list scheduling. This works as follows: starting with a list of
44 all the ready insns, and sorted according to priority number, we
45 schedule the insn from the end of the list by placing its
46 predecessors in the list according to their priority order. We
47 consider this insn scheduled by setting the pointer to the "end" of
48 the list to point to the previous insn. When an insn has no
49 predecessors, we either queue it until sufficient time has elapsed
50 or add it to the ready list. As the instructions are scheduled or
51 when stalls are introduced, the queue advances and dumps insns into
52 the ready list. When all insns down to the lowest priority have
53 been scheduled, the critical path of the basic block has been made
54 as short as possible. The remaining insns are then scheduled in
57 Function unit conflicts are resolved during reverse 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. Among the remaining insns on
63 the ready list to be considered, the first one with the largest
64 potential for causing a subsequent blockage is chosen.
66 The following list shows the order in which we want to break ties
67 among insns in the ready list:
69 1. choose insn with lowest conflict cost, ties broken by
70 2. choose insn with the longest path to end of bb, ties broken by
71 3. choose insn that kills the most registers, ties broken by
72 4. choose insn that conflicts with the most ready insns, or finally
73 5. choose insn with lowest UID.
75 Memory references complicate matters. Only if we can be certain
76 that memory references are not part of the data dependency graph
77 (via true, anti, or output dependence), can we move operations past
78 memory references. To first approximation, reads can be done
79 independently, while writes introduce dependencies. Better
80 approximations will yield fewer dependencies.
82 Dependencies set up by memory references are treated in exactly the
83 same way as other dependencies, by using LOG_LINKS.
85 Having optimized the critical path, we may have also unduly
86 extended the lifetimes of some registers. If an operation requires
87 that constants be loaded into registers, it is certainly desirable
88 to load those constants as early as necessary, but no earlier.
89 I.e., it will not do to load up a bunch of registers at the
90 beginning of a basic block only to use them at the end, if they
91 could be loaded later, since this may result in excessive register
94 Note that since branches are never in basic blocks, but only end
95 basic blocks, this pass will not do any branch scheduling. But
96 that is ok, since we can use GNU's delayed branch scheduling
97 pass to take care of this case.
99 Also note that no further optimizations based on algebraic identities
100 are performed, so this pass would be a good one to perform instruction
101 splitting, such as breaking up a multiply instruction into shifts
102 and adds where that is profitable.
104 Given the memory aliasing analysis that this pass should perform,
105 it should be possible to remove redundant stores to memory, and to
106 load values from registers instead of hitting memory.
108 This pass must update information that subsequent passes expect to be
109 correct. Namely: reg_n_refs, reg_n_sets, reg_n_deaths,
110 reg_n_calls_crossed, and reg_live_length. Also, basic_block_head,
113 The information in the line number notes is carefully retained by this
114 pass. All other NOTE insns are grouped in their same relative order at
115 the beginning of basic blocks that have been scheduled. */
120 #include "basic-block.h"
122 #include "hard-reg-set.h"
124 #include "insn-config.h"
125 #include "insn-attr.h"
127 #ifdef INSN_SCHEDULING
128 /* Arrays set up by scheduling for the same respective purposes as
129 similar-named arrays set up by flow analysis. We work with these
130 arrays during the scheduling pass so we can compare values against
133 Values of these arrays are copied at the end of this pass into the
134 arrays set up by flow analysis. */
135 static short *sched_reg_n_deaths;
136 static int *sched_reg_n_calls_crossed;
137 static int *sched_reg_live_length;
139 /* Element N is the next insn that sets (hard or pseudo) register
140 N within the current basic block; or zero, if there is no
141 such insn. Needed for new registers which may be introduced
142 by splitting insns. */
143 static rtx *reg_last_uses;
144 static rtx *reg_last_sets;
146 /* Vector indexed by INSN_UID giving the original ordering of the insns. */
147 static int *insn_luid;
148 #define INSN_LUID(INSN) (insn_luid[INSN_UID (INSN)])
150 /* Vector indexed by INSN_UID giving each instruction a priority. */
151 static int *insn_priority;
152 #define INSN_PRIORITY(INSN) (insn_priority[INSN_UID (INSN)])
154 static short *insn_costs;
155 #define INSN_COST(INSN) insn_costs[INSN_UID (INSN)]
157 /* Vector indexed by INSN_UID giving an encoding of the function units
159 static short *insn_units;
160 #define INSN_UNIT(INSN) insn_units[INSN_UID (INSN)]
162 /* Vector indexed by INSN_UID giving an encoding of the blockage range
163 function. The unit and the range are encoded. */
164 static unsigned int *insn_blockage;
165 #define INSN_BLOCKAGE(INSN) insn_blockage[INSN_UID (INSN)]
167 #define BLOCKAGE_MASK ((1 << BLOCKAGE_BITS) - 1)
168 #define ENCODE_BLOCKAGE(U,R) \
169 ((((U) << UNIT_BITS) << BLOCKAGE_BITS \
170 | MIN_BLOCKAGE_COST (R)) << BLOCKAGE_BITS \
171 | MAX_BLOCKAGE_COST (R))
172 #define UNIT_BLOCKED(B) ((B) >> (2 * BLOCKAGE_BITS))
173 #define BLOCKAGE_RANGE(B) \
174 (((((B) >> BLOCKAGE_BITS) & BLOCKAGE_MASK) << (HOST_BITS_PER_INT / 2)) \
175 | (B) & BLOCKAGE_MASK)
177 /* Encodings of the `<name>_unit_blockage_range' function. */
178 #define MIN_BLOCKAGE_COST(R) ((R) >> (HOST_BITS_PER_INT / 2))
179 #define MAX_BLOCKAGE_COST(R) ((R) & ((1 << (HOST_BITS_PER_INT / 2)) - 1))
181 #define DONE_PRIORITY -1
182 #define MAX_PRIORITY 0x7fffffff
183 #define TAIL_PRIORITY 0x7ffffffe
184 #define LAUNCH_PRIORITY 0x7f000001
185 #define DONE_PRIORITY_P(INSN) (INSN_PRIORITY (INSN) < 0)
186 #define LOW_PRIORITY_P(INSN) ((INSN_PRIORITY (INSN) & 0x7f000000) == 0)
188 /* Vector indexed by INSN_UID giving number of insns referring to this insn. */
189 static int *insn_ref_count;
190 #define INSN_REF_COUNT(INSN) (insn_ref_count[INSN_UID (INSN)])
192 /* Vector indexed by INSN_UID giving line-number note in effect for each
193 insn. For line-number notes, this indicates whether the note may be
195 static rtx *line_note;
196 #define LINE_NOTE(INSN) (line_note[INSN_UID (INSN)])
198 /* Vector indexed by basic block number giving the starting line-number
199 for each basic block. */
200 static rtx *line_note_head;
202 /* List of important notes we must keep around. This is a pointer to the
203 last element in the list. */
204 static rtx note_list;
206 /* Regsets telling whether a given register is live or dead before the last
207 scheduled insn. Must scan the instructions once before scheduling to
208 determine what registers are live or dead at the end of the block. */
209 static regset bb_dead_regs;
210 static regset bb_live_regs;
212 /* Regset telling whether a given register is live after the insn currently
213 being scheduled. Before processing an insn, this is equal to bb_live_regs
214 above. This is used so that we can find registers that are newly born/dead
215 after processing an insn. */
216 static regset old_live_regs;
218 /* The chain of REG_DEAD notes. REG_DEAD notes are removed from all insns
219 during the initial scan and reused later. If there are not exactly as
220 many REG_DEAD notes in the post scheduled code as there were in the
221 prescheduled code then we trigger an abort because this indicates a bug. */
222 static rtx dead_notes;
226 /* An instruction is ready to be scheduled when all insns following it
227 have already been scheduled. It is important to ensure that all
228 insns which use its result will not be executed until its result
229 has been computed. An insn is maintained in one of four structures:
231 (P) the "Pending" set of insns which cannot be scheduled until
232 their dependencies have been satisfied.
233 (Q) the "Queued" set of insns that can be scheduled when sufficient
235 (R) the "Ready" list of unscheduled, uncommitted insns.
236 (S) the "Scheduled" list of insns.
238 Initially, all insns are either "Pending" or "Ready" depending on
239 whether their dependencies are satisfied.
241 Insns move from the "Ready" list to the "Scheduled" list as they
242 are committed to the schedule. As this occurs, the insns in the
243 "Pending" list have their dependencies satisfied and move to either
244 the "Ready" list or the "Queued" set depending on whether
245 sufficient time has passed to make them ready. As time passes,
246 insns move from the "Queued" set to the "Ready" list. Insns may
247 move from the "Ready" list to the "Queued" set if they are blocked
248 due to a function unit conflict.
250 The "Pending" list (P) are the insns in the LOG_LINKS of the unscheduled
251 insns, i.e., those that are ready, queued, and pending.
252 The "Queued" set (Q) is implemented by the variable `insn_queue'.
253 The "Ready" list (R) is implemented by the variables `ready' and
255 The "Scheduled" list (S) is the new insn chain built by this pass.
257 The transition (R->S) is implemented in the scheduling loop in
258 `schedule_block' when the best insn to schedule is chosen.
259 The transition (R->Q) is implemented in `schedule_select' when an
260 insn is found to to have a function unit conflict with the already
262 The transitions (P->R and P->Q) are implemented in `schedule_insn' as
263 insns move from the ready list to the scheduled list.
264 The transition (Q->R) is implemented at the top of the scheduling
265 loop in `schedule_block' as time passes or stalls are introduced. */
267 /* Implement a circular buffer to delay instructions until sufficient
268 time has passed. INSN_QUEUE_SIZE is a power of two larger than
269 MAX_BLOCKAGE and MAX_READY_COST computed by genattr.c. This is the
270 longest time an isnsn may be queued. */
271 static rtx insn_queue[INSN_QUEUE_SIZE];
272 static int q_ptr = 0;
273 static int q_size = 0;
274 #define NEXT_Q(X) (((X)+1) & (INSN_QUEUE_SIZE-1))
275 #define NEXT_Q_AFTER(X,C) (((X)+C) & (INSN_QUEUE_SIZE-1))
277 /* Vector indexed by INSN_UID giving the minimum clock tick at which
278 the insn becomes ready. This is used to note timing constraints for
279 insns in the pending list. */
280 static int *insn_tick;
281 #define INSN_TICK(INSN) (insn_tick[INSN_UID (INSN)])
283 /* Forward declarations. */
284 static void sched_analyze_2 ();
285 static void schedule_block ();
287 /* Main entry point of this file. */
288 void schedule_insns ();
289 #endif /* INSN_SCHEDULING */
291 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
293 /* Vector indexed by N giving the initial (unchanging) value known
294 for pseudo-register N. */
295 static rtx *reg_known_value;
297 /* Vector recording for each reg_known_value whether it is due to a
298 REG_EQUIV note. Future passes (viz., reload) may replace the
299 pseudo with the equivalent expression and so we account for the
300 dependences that would be introduced if that happens. */
301 /* ??? This is a problem only on the Convex. The REG_EQUIV notes created in
302 assign_parms mention the arg pointer, and there are explicit insns in the
303 RTL that modify the arg pointer. Thus we must ensure that such insns don't
304 get scheduled across each other because that would invalidate the REG_EQUIV
305 notes. One could argue that the REG_EQUIV notes are wrong, but solving
306 the problem in the scheduler will likely give better code, so we do it
308 static char *reg_known_equiv_p;
310 /* Indicates number of valid entries in reg_known_value. */
311 static int reg_known_value_size;
317 if (GET_CODE (x) == REG && REGNO (x) >= FIRST_PSEUDO_REGISTER
318 && REGNO (x) <= reg_known_value_size)
319 return reg_known_value[REGNO (x)];
320 else if (GET_CODE (x) == PLUS)
322 rtx x0 = canon_rtx (XEXP (x, 0));
323 rtx x1 = canon_rtx (XEXP (x, 1));
325 if (x0 != XEXP (x, 0) || x1 != XEXP (x, 1))
327 /* We can tolerate LO_SUMs being offset here; these
328 rtl are used for nothing other than comparisons. */
329 if (GET_CODE (x0) == CONST_INT)
330 return plus_constant_for_output (x1, INTVAL (x0));
331 else if (GET_CODE (x1) == CONST_INT)
332 return plus_constant_for_output (x0, INTVAL (x1));
333 return gen_rtx (PLUS, GET_MODE (x), x0, x1);
339 /* Set up all info needed to perform alias analysis on memory references. */
342 init_alias_analysis ()
344 int maxreg = max_reg_num ();
349 reg_known_value_size = maxreg;
352 = (rtx *) oballoc ((maxreg-FIRST_PSEUDO_REGISTER) * sizeof (rtx))
353 - FIRST_PSEUDO_REGISTER;
354 bzero (reg_known_value+FIRST_PSEUDO_REGISTER,
355 (maxreg-FIRST_PSEUDO_REGISTER) * sizeof (rtx));
358 = (char *) oballoc ((maxreg-FIRST_PSEUDO_REGISTER) * sizeof (char))
359 - FIRST_PSEUDO_REGISTER;
360 bzero (reg_known_equiv_p+FIRST_PSEUDO_REGISTER,
361 (maxreg-FIRST_PSEUDO_REGISTER) * sizeof (char));
363 /* Fill in the entries with known constant values. */
364 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
365 if ((set = single_set (insn)) != 0
366 && GET_CODE (SET_DEST (set)) == REG
367 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER
368 && (((note = find_reg_note (insn, REG_EQUAL, 0)) != 0
369 && reg_n_sets[REGNO (SET_DEST (set))] == 1)
370 || (note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != 0)
371 && GET_CODE (XEXP (note, 0)) != EXPR_LIST)
373 int regno = REGNO (SET_DEST (set));
374 reg_known_value[regno] = XEXP (note, 0);
375 reg_known_equiv_p[regno] = REG_NOTE_KIND (note) == REG_EQUIV;
378 /* Fill in the remaining entries. */
379 while (--maxreg >= FIRST_PSEUDO_REGISTER)
380 if (reg_known_value[maxreg] == 0)
381 reg_known_value[maxreg] = regno_reg_rtx[maxreg];
384 /* Return 1 if X and Y are identical-looking rtx's.
386 We use the data in reg_known_value above to see if two registers with
387 different numbers are, in fact, equivalent. */
390 rtx_equal_for_memref_p (x, y)
395 register enum rtx_code code;
398 if (x == 0 && y == 0)
400 if (x == 0 || y == 0)
409 /* Rtx's of different codes cannot be equal. */
410 if (code != GET_CODE (y))
413 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
414 (REG:SI x) and (REG:HI x) are NOT equivalent. */
416 if (GET_MODE (x) != GET_MODE (y))
419 /* REG, LABEL_REF, and SYMBOL_REF can be compared nonrecursively. */
422 return REGNO (x) == REGNO (y);
423 if (code == LABEL_REF)
424 return XEXP (x, 0) == XEXP (y, 0);
425 if (code == SYMBOL_REF)
426 return XSTR (x, 0) == XSTR (y, 0);
428 /* Compare the elements. If any pair of corresponding elements
429 fail to match, return 0 for the whole things. */
431 fmt = GET_RTX_FORMAT (code);
432 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
437 if (XWINT (x, i) != XWINT (y, i))
443 if (XINT (x, i) != XINT (y, i))
449 /* Two vectors must have the same length. */
450 if (XVECLEN (x, i) != XVECLEN (y, i))
453 /* And the corresponding elements must match. */
454 for (j = 0; j < XVECLEN (x, i); j++)
455 if (rtx_equal_for_memref_p (XVECEXP (x, i, j), XVECEXP (y, i, j)) == 0)
460 if (rtx_equal_for_memref_p (XEXP (x, i), XEXP (y, i)) == 0)
466 if (strcmp (XSTR (x, i), XSTR (y, i)))
471 /* These are just backpointers, so they don't matter. */
477 /* It is believed that rtx's at this level will never
478 contain anything but integers and other rtx's,
479 except for within LABEL_REFs and SYMBOL_REFs. */
487 /* Given an rtx X, find a SYMBOL_REF or LABEL_REF within
488 X and return it, or return 0 if none found. */
491 find_symbolic_term (x)
495 register enum rtx_code code;
499 if (code == SYMBOL_REF || code == LABEL_REF)
501 if (GET_RTX_CLASS (code) == 'o')
504 fmt = GET_RTX_FORMAT (code);
505 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
511 t = find_symbolic_term (XEXP (x, i));
515 else if (fmt[i] == 'E')
521 /* Return nonzero if X and Y (memory addresses) could reference the
522 same location in memory. C is an offset accumulator. When
523 C is nonzero, we are testing aliases between X and Y + C.
524 XSIZE is the size in bytes of the X reference,
525 similarly YSIZE is the size in bytes for Y.
527 If XSIZE or YSIZE is zero, we do not know the amount of memory being
528 referenced (the reference was BLKmode), so make the most pessimistic
531 We recognize the following cases of non-conflicting memory:
533 (1) addresses involving the frame pointer cannot conflict
534 with addresses involving static variables.
535 (2) static variables with different addresses cannot conflict.
537 Nice to notice that varying addresses cannot conflict with fp if no
538 local variables had their addresses taken, but that's too hard now. */
540 /* ??? In Fortran, references to a array parameter can never conflict with
541 another array parameter. */
544 memrefs_conflict_p (xsize, x, ysize, y, c)
549 if (GET_CODE (x) == HIGH)
551 else if (GET_CODE (x) == LO_SUM)
555 if (GET_CODE (y) == HIGH)
557 else if (GET_CODE (y) == LO_SUM)
562 if (rtx_equal_for_memref_p (x, y))
563 return (xsize == 0 || ysize == 0 ||
564 (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
566 if (y == frame_pointer_rtx || y == hard_frame_pointer_rtx
567 || y == stack_pointer_rtx)
571 y = x; ysize = xsize;
572 x = t; xsize = tsize;
575 if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
576 || x == stack_pointer_rtx)
583 if (GET_CODE (y) == PLUS
584 && canon_rtx (XEXP (y, 0)) == x
585 && (y1 = canon_rtx (XEXP (y, 1)))
586 && GET_CODE (y1) == CONST_INT)
589 return (xsize == 0 || ysize == 0
590 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
593 if (GET_CODE (y) == PLUS
594 && (y1 = canon_rtx (XEXP (y, 0)))
601 if (GET_CODE (x) == PLUS)
603 /* The fact that X is canonicalized means that this
604 PLUS rtx is canonicalized. */
605 rtx x0 = XEXP (x, 0);
606 rtx x1 = XEXP (x, 1);
608 if (GET_CODE (y) == PLUS)
610 /* The fact that Y is canonicalized means that this
611 PLUS rtx is canonicalized. */
612 rtx y0 = XEXP (y, 0);
613 rtx y1 = XEXP (y, 1);
615 if (rtx_equal_for_memref_p (x1, y1))
616 return memrefs_conflict_p (xsize, x0, ysize, y0, c);
617 if (rtx_equal_for_memref_p (x0, y0))
618 return memrefs_conflict_p (xsize, x1, ysize, y1, c);
619 if (GET_CODE (x1) == CONST_INT)
620 if (GET_CODE (y1) == CONST_INT)
621 return memrefs_conflict_p (xsize, x0, ysize, y0,
622 c - INTVAL (x1) + INTVAL (y1));
624 return memrefs_conflict_p (xsize, x0, ysize, y, c - INTVAL (x1));
625 else if (GET_CODE (y1) == CONST_INT)
626 return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1));
628 /* Handle case where we cannot understand iteration operators,
629 but we notice that the base addresses are distinct objects. */
630 x = find_symbolic_term (x);
633 y = find_symbolic_term (y);
636 return rtx_equal_for_memref_p (x, y);
638 else if (GET_CODE (x1) == CONST_INT)
639 return memrefs_conflict_p (xsize, x0, ysize, y, c - INTVAL (x1));
641 else if (GET_CODE (y) == PLUS)
643 /* The fact that Y is canonicalized means that this
644 PLUS rtx is canonicalized. */
645 rtx y0 = XEXP (y, 0);
646 rtx y1 = XEXP (y, 1);
648 if (GET_CODE (y1) == CONST_INT)
649 return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1));
654 if (GET_CODE (x) == GET_CODE (y))
655 switch (GET_CODE (x))
659 /* Handle cases where we expect the second operands to be the
660 same, and check only whether the first operand would conflict
663 rtx x1 = canon_rtx (XEXP (x, 1));
664 rtx y1 = canon_rtx (XEXP (y, 1));
665 if (! rtx_equal_for_memref_p (x1, y1))
667 x0 = canon_rtx (XEXP (x, 0));
668 y0 = canon_rtx (XEXP (y, 0));
669 if (rtx_equal_for_memref_p (x0, y0))
670 return (xsize == 0 || ysize == 0
671 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
673 /* Can't properly adjust our sizes. */
674 if (GET_CODE (x1) != CONST_INT)
676 xsize /= INTVAL (x1);
677 ysize /= INTVAL (x1);
679 return memrefs_conflict_p (xsize, x0, ysize, y0, c);
685 if (GET_CODE (x) == CONST_INT && GET_CODE (y) == CONST_INT)
687 c += (INTVAL (y) - INTVAL (x));
688 return (xsize == 0 || ysize == 0
689 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
692 if (GET_CODE (x) == CONST)
694 if (GET_CODE (y) == CONST)
695 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
696 ysize, canon_rtx (XEXP (y, 0)), c);
698 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
701 if (GET_CODE (y) == CONST)
702 return memrefs_conflict_p (xsize, x, ysize,
703 canon_rtx (XEXP (y, 0)), c);
706 return (rtx_equal_for_memref_p (x, y)
707 && (xsize == 0 || ysize == 0
708 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0)));
715 /* Functions to compute memory dependencies.
717 Since we process the insns in execution order, we can build tables
718 to keep track of what registers are fixed (and not aliased), what registers
719 are varying in known ways, and what registers are varying in unknown
722 If both memory references are volatile, then there must always be a
723 dependence between the two references, since their order can not be
724 changed. A volatile and non-volatile reference can be interchanged
727 A MEM_IN_STRUCT reference at a non-QImode varying address can never
728 conflict with a non-MEM_IN_STRUCT reference at a fixed address. We must
729 allow QImode aliasing because the ANSI C standard allows character
730 pointers to alias anything. We are assuming that characters are
731 always QImode here. */
733 /* Read dependence: X is read after read in MEM takes place. There can
734 only be a dependence here if both reads are volatile. */
737 read_dependence (mem, x)
741 return MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem);
744 /* True dependence: X is read after store in MEM takes place. */
747 true_dependence (mem, x)
751 /* If X is an unchanging read, then it can't possibly conflict with any
752 non-unchanging store. It may conflict with an unchanging write though,
753 because there may be a single store to this address to initialize it.
754 Just fall through to the code below to resolve the case where we have
755 both an unchanging read and an unchanging write. This won't handle all
756 cases optimally, but the possible performance loss should be
758 if (RTX_UNCHANGING_P (x) && ! RTX_UNCHANGING_P (mem))
761 return ((MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
762 || (memrefs_conflict_p (SIZE_FOR_MODE (mem), XEXP (mem, 0),
763 SIZE_FOR_MODE (x), XEXP (x, 0), 0)
764 && ! (MEM_IN_STRUCT_P (mem) && rtx_addr_varies_p (mem)
765 && GET_MODE (mem) != QImode
766 && ! MEM_IN_STRUCT_P (x) && ! rtx_addr_varies_p (x))
767 && ! (MEM_IN_STRUCT_P (x) && rtx_addr_varies_p (x)
768 && GET_MODE (x) != QImode
769 && ! MEM_IN_STRUCT_P (mem) && ! rtx_addr_varies_p (mem))));
772 /* Anti dependence: X is written after read in MEM takes place. */
775 anti_dependence (mem, x)
779 /* If MEM is an unchanging read, then it can't possibly conflict with
780 the store to X, because there is at most one store to MEM, and it must
781 have occured somewhere before MEM. */
782 if (RTX_UNCHANGING_P (mem))
785 return ((MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
786 || (memrefs_conflict_p (SIZE_FOR_MODE (mem), XEXP (mem, 0),
787 SIZE_FOR_MODE (x), XEXP (x, 0), 0)
788 && ! (MEM_IN_STRUCT_P (mem) && rtx_addr_varies_p (mem)
789 && GET_MODE (mem) != QImode
790 && ! MEM_IN_STRUCT_P (x) && ! rtx_addr_varies_p (x))
791 && ! (MEM_IN_STRUCT_P (x) && rtx_addr_varies_p (x)
792 && GET_MODE (x) != QImode
793 && ! MEM_IN_STRUCT_P (mem) && ! rtx_addr_varies_p (mem))));
796 /* Output dependence: X is written after store in MEM takes place. */
799 output_dependence (mem, x)
803 return ((MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
804 || (memrefs_conflict_p (SIZE_FOR_MODE (mem), XEXP (mem, 0),
805 SIZE_FOR_MODE (x), XEXP (x, 0), 0)
806 && ! (MEM_IN_STRUCT_P (mem) && rtx_addr_varies_p (mem)
807 && GET_MODE (mem) != QImode
808 && ! MEM_IN_STRUCT_P (x) && ! rtx_addr_varies_p (x))
809 && ! (MEM_IN_STRUCT_P (x) && rtx_addr_varies_p (x)
810 && GET_MODE (x) != QImode
811 && ! MEM_IN_STRUCT_P (mem) && ! rtx_addr_varies_p (mem))));
814 /* Helper functions for instruction scheduling. */
816 /* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the
817 LOG_LINKS of INSN, if not already there. DEP_TYPE indicates the type
818 of dependence that this link represents. */
821 add_dependence (insn, elem, dep_type)
824 enum reg_note dep_type;
828 /* Don't depend an insn on itself. */
832 /* If elem is part of a sequence that must be scheduled together, then
833 make the dependence point to the last insn of the sequence.
834 When HAVE_cc0, it is possible for NOTEs to exist between users and
835 setters of the condition codes, so we must skip past notes here.
836 Otherwise, NOTEs are impossible here. */
838 next = NEXT_INSN (elem);
841 while (next && GET_CODE (next) == NOTE)
842 next = NEXT_INSN (next);
845 if (next && SCHED_GROUP_P (next))
847 /* Notes will never intervene here though, so don't bother checking
849 /* We must reject CODE_LABELs, so that we don't get confused by one
850 that has LABEL_PRESERVE_P set, which is represented by the same
851 bit in the rtl as SCHED_GROUP_P. A CODE_LABEL can never be
853 while (NEXT_INSN (next) && SCHED_GROUP_P (NEXT_INSN (next))
854 && GET_CODE (NEXT_INSN (next)) != CODE_LABEL)
855 next = NEXT_INSN (next);
857 /* Again, don't depend an insn on itself. */
861 /* Make the dependence to NEXT, the last insn of the group, instead
862 of the original ELEM. */
866 /* Check that we don't already have this dependence. */
867 for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
868 if (XEXP (link, 0) == elem)
870 /* If this is a more restrictive type of dependence than the existing
871 one, then change the existing dependence to this type. */
872 if ((int) dep_type < (int) REG_NOTE_KIND (link))
873 PUT_REG_NOTE_KIND (link, dep_type);
876 /* Might want to check one level of transitivity to save conses. */
878 link = rtx_alloc (INSN_LIST);
879 /* Insn dependency, not data dependency. */
880 PUT_REG_NOTE_KIND (link, dep_type);
881 XEXP (link, 0) = elem;
882 XEXP (link, 1) = LOG_LINKS (insn);
883 LOG_LINKS (insn) = link;
886 /* Remove ELEM wrapped in an INSN_LIST from the LOG_LINKS
887 of INSN. Abort if not found. */
889 remove_dependence (insn, elem)
896 for (prev = 0, link = LOG_LINKS (insn); link;
897 prev = link, link = XEXP (link, 1))
899 if (XEXP (link, 0) == elem)
902 XEXP (prev, 1) = XEXP (link, 1);
904 LOG_LINKS (insn) = XEXP (link, 1);
914 #ifndef INSN_SCHEDULING
915 void schedule_insns () {}
921 /* Computation of memory dependencies. */
923 /* The *_insns and *_mems are paired lists. Each pending memory operation
924 will have a pointer to the MEM rtx on one list and a pointer to the
925 containing insn on the other list in the same place in the list. */
927 /* We can't use add_dependence like the old code did, because a single insn
928 may have multiple memory accesses, and hence needs to be on the list
929 once for each memory access. Add_dependence won't let you add an insn
930 to a list more than once. */
932 /* An INSN_LIST containing all insns with pending read operations. */
933 static rtx pending_read_insns;
935 /* An EXPR_LIST containing all MEM rtx's which are pending reads. */
936 static rtx pending_read_mems;
938 /* An INSN_LIST containing all insns with pending write operations. */
939 static rtx pending_write_insns;
941 /* An EXPR_LIST containing all MEM rtx's which are pending writes. */
942 static rtx pending_write_mems;
944 /* Indicates the combined length of the two pending lists. We must prevent
945 these lists from ever growing too large since the number of dependencies
946 produced is at least O(N*N), and execution time is at least O(4*N*N), as
947 a function of the length of these pending lists. */
949 static int pending_lists_length;
951 /* An INSN_LIST containing all INSN_LISTs allocated but currently unused. */
953 static rtx unused_insn_list;
955 /* An EXPR_LIST containing all EXPR_LISTs allocated but currently unused. */
957 static rtx unused_expr_list;
959 /* The last insn upon which all memory references must depend.
960 This is an insn which flushed the pending lists, creating a dependency
961 between it and all previously pending memory references. This creates
962 a barrier (or a checkpoint) which no memory reference is allowed to cross.
964 This includes all non constant CALL_INSNs. When we do interprocedural
965 alias analysis, this restriction can be relaxed.
966 This may also be an INSN that writes memory if the pending lists grow
969 static rtx last_pending_memory_flush;
971 /* The last function call we have seen. All hard regs, and, of course,
972 the last function call, must depend on this. */
974 static rtx last_function_call;
976 /* The LOG_LINKS field of this is a list of insns which use a pseudo register
977 that does not already cross a call. We create dependencies between each
978 of those insn and the next call insn, to ensure that they won't cross a call
979 after scheduling is done. */
981 static rtx sched_before_next_call;
983 /* Pointer to the last instruction scheduled. Used by rank_for_schedule,
984 so that insns independent of the last scheduled insn will be preferred
985 over dependent instructions. */
987 static rtx last_scheduled_insn;
989 /* Process an insn's memory dependencies. There are four kinds of
992 (0) read dependence: read follows read
993 (1) true dependence: read follows write
994 (2) anti dependence: write follows read
995 (3) output dependence: write follows write
997 We are careful to build only dependencies which actually exist, and
998 use transitivity to avoid building too many links. */
1000 /* Return the INSN_LIST containing INSN in LIST, or NULL
1001 if LIST does not contain INSN. */
1004 find_insn_list (insn, list)
1010 if (XEXP (list, 0) == insn)
1012 list = XEXP (list, 1);
1017 /* Compute the function units used by INSN. This caches the value
1018 returned by function_units_used. A function unit is encoded as the
1019 unit number if the value is non-negative and the compliment of a
1020 mask if the value is negative. A function unit index is the
1021 non-negative encoding. */
1027 register int unit = INSN_UNIT (insn);
1031 recog_memoized (insn);
1033 /* A USE insn, or something else we don't need to understand.
1034 We can't pass these directly to function_units_used because it will
1035 trigger a fatal error for unrecognizable insns. */
1036 if (INSN_CODE (insn) < 0)
1040 unit = function_units_used (insn);
1041 /* Increment non-negative values so we can cache zero. */
1042 if (unit >= 0) unit++;
1044 /* We only cache 16 bits of the result, so if the value is out of
1045 range, don't cache it. */
1046 if (FUNCTION_UNITS_SIZE < HOST_BITS_PER_SHORT
1048 || (~unit & ((1 << (HOST_BITS_PER_SHORT - 1)) - 1)) == 0)
1049 INSN_UNIT (insn) = unit;
1051 return (unit > 0 ? unit - 1 : unit);
1054 /* Compute the blockage range for executing INSN on UNIT. This caches
1055 the value returned by the blockage_range_function for the unit.
1056 These values are encoded in an int where the upper half gives the
1057 minimum value and the lower half gives the maximum value. */
1059 __inline static unsigned int
1060 blockage_range (unit, insn)
1064 unsigned int blockage = INSN_BLOCKAGE (insn);
1067 if (UNIT_BLOCKED (blockage) != unit + 1)
1069 range = function_units[unit].blockage_range_function (insn);
1070 /* We only cache the blockage range for one unit and then only if
1072 if (HOST_BITS_PER_INT >= UNIT_BITS + 2 * BLOCKAGE_BITS)
1073 INSN_BLOCKAGE (insn) = ENCODE_BLOCKAGE (unit + 1, range);
1076 range = BLOCKAGE_RANGE (blockage);
1081 /* A vector indexed by function unit instance giving the last insn to use
1082 the unit. The value of the function unit instance index for unit U
1083 instance I is (U + I * FUNCTION_UNITS_SIZE). */
1084 static rtx unit_last_insn[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY];
1086 /* A vector indexed by function unit instance giving the minimum time when
1087 the unit will unblock based on the maximum blockage cost. */
1088 static int unit_tick[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY];
1090 /* A vector indexed by function unit number giving the number of insns
1091 that remain to use the unit. */
1092 static int unit_n_insns[FUNCTION_UNITS_SIZE];
1094 /* Reset the function unit state to the null state. */
1101 bzero (unit_last_insn, sizeof (unit_last_insn));
1102 bzero (unit_tick, sizeof (unit_tick));
1103 bzero (unit_n_insns, sizeof (unit_n_insns));
1106 /* Record an insn as one that will use the units encoded by UNIT. */
1108 __inline static void
1115 unit_n_insns[unit]++;
1117 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
1118 if ((unit & 1) != 0)
1122 /* Return the actual hazard cost of executing INSN on the unit UNIT,
1123 instance INSTANCE at time CLOCK if the previous actual hazard cost
1127 actual_hazard_this_instance (unit, instance, insn, clock, cost)
1128 int unit, instance, clock, cost;
1132 int tick = unit_tick[instance];
1134 if (tick - clock > cost)
1136 /* The scheduler is operating in reverse, so INSN is the executing
1137 insn and the unit's last insn is the candidate insn. We want a
1138 more exact measure of the blockage if we execute INSN at CLOCK
1139 given when we committed the execution of the unit's last insn.
1141 The blockage value is given by either the unit's max blockage
1142 constant, blockage range function, or blockage function. Use
1143 the most exact form for the given unit. */
1145 if (function_units[unit].blockage_range_function)
1147 if (function_units[unit].blockage_function)
1148 tick += (function_units[unit].blockage_function
1149 (insn, unit_last_insn[instance])
1150 - function_units[unit].max_blockage);
1152 tick += ((int) MAX_BLOCKAGE_COST (blockage_range (unit, insn))
1153 - function_units[unit].max_blockage);
1155 if (tick - clock > cost)
1156 cost = tick - clock;
1161 /* Record INSN as having begun execution on the units encoded by UNIT at
1164 __inline static void
1165 schedule_unit (unit, insn, clock)
1173 int instance = unit;
1174 #if MAX_MULTIPLICITY > 1
1175 /* Find the first free instance of the function unit and use that
1176 one. We assume that one is free. */
1177 for (i = function_units[unit].multiplicity - 1; i > 0; i--)
1179 if (! actual_hazard_this_instance (unit, instance, insn, clock, 0))
1181 instance += FUNCTION_UNITS_SIZE;
1184 unit_last_insn[instance] = insn;
1185 unit_tick[instance] = (clock + function_units[unit].max_blockage);
1188 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
1189 if ((unit & 1) != 0)
1190 schedule_unit (i, insn, clock);
1193 /* Return the actual hazard cost of executing INSN on the units encoded by
1194 UNIT at time CLOCK if the previous actual hazard cost was COST. */
1197 actual_hazard (unit, insn, clock, cost)
1198 int unit, clock, cost;
1205 /* Find the instance of the function unit with the minimum hazard. */
1206 int instance = unit;
1207 int best = instance;
1208 int best_cost = actual_hazard_this_instance (unit, instance, insn,
1212 #if MAX_MULTIPLICITY > 1
1213 if (best_cost > cost)
1215 for (i = function_units[unit].multiplicity - 1; i > 0; i--)
1217 instance += FUNCTION_UNITS_SIZE;
1218 this_cost = actual_hazard_this_instance (unit, instance, insn,
1220 if (this_cost < best_cost)
1223 best_cost = this_cost;
1224 if (this_cost <= cost)
1230 cost = MAX (cost, best_cost);
1233 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
1234 if ((unit & 1) != 0)
1235 cost = actual_hazard (i, insn, clock, cost);
1240 /* Return the potential hazard cost of executing an instruction on the
1241 units encoded by UNIT if the previous potential hazard cost was COST.
1242 An insn with a large blockage time is chosen in preference to one
1243 with a smaller time; an insn that uses a unit that is more likely
1244 to be used is chosen in preference to one with a unit that is less
1245 used. We are trying to minimize a subsequent actual hazard. */
1248 potential_hazard (unit, insn, cost)
1253 unsigned int minb, maxb;
1257 minb = maxb = function_units[unit].max_blockage;
1260 if (function_units[unit].blockage_range_function)
1262 maxb = minb = blockage_range (unit, insn);
1263 maxb = MAX_BLOCKAGE_COST (maxb);
1264 minb = MIN_BLOCKAGE_COST (minb);
1269 /* Make the number of instructions left dominate. Make the
1270 minimum delay dominate the maximum delay. If all these
1271 are the same, use the unit number to add an arbitrary
1272 ordering. Other terms can be added. */
1273 ncost = minb * 0x40 + maxb;
1274 ncost *= (unit_n_insns[unit] - 1) * 0x1000 + unit;
1281 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
1282 if ((unit & 1) != 0)
1283 cost = potential_hazard (i, insn, cost);
1288 /* Compute cost of executing INSN given the dependence LINK on the insn USED.
1289 This is the number of virtual cycles taken between instruction issue and
1290 instruction results. */
1293 insn_cost (insn, link, used)
1294 rtx insn, link, used;
1296 register int cost = INSN_COST (insn);
1300 recog_memoized (insn);
1302 /* A USE insn, or something else we don't need to understand.
1303 We can't pass these directly to result_ready_cost because it will
1304 trigger a fatal error for unrecognizable insns. */
1305 if (INSN_CODE (insn) < 0)
1307 INSN_COST (insn) = 1;
1312 cost = result_ready_cost (insn);
1317 INSN_COST (insn) = cost;
1321 /* A USE insn should never require the value used to be computed. This
1322 allows the computation of a function's result and parameter values to
1323 overlap the return and call. */
1324 recog_memoized (used);
1325 if (INSN_CODE (used) < 0)
1326 LINK_COST_FREE (link) = 1;
1328 /* If some dependencies vary the cost, compute the adjustment. Most
1329 commonly, the adjustment is complete: either the cost is ignored
1330 (in the case of an output- or anti-dependence), or the cost is
1331 unchanged. These values are cached in the link as LINK_COST_FREE
1332 and LINK_COST_ZERO. */
1334 if (LINK_COST_FREE (link))
1337 else if (! LINK_COST_ZERO (link))
1341 ADJUST_COST (used, link, insn, ncost);
1343 LINK_COST_FREE (link) = ncost = 1;
1345 LINK_COST_ZERO (link) = 1;
1352 /* Compute the priority number for INSN. */
1358 if (insn && GET_RTX_CLASS (GET_CODE (insn)) == 'i')
1362 int this_priority = INSN_PRIORITY (insn);
1365 if (this_priority > 0)
1366 return this_priority;
1370 /* Nonzero if these insns must be scheduled together. */
1371 if (SCHED_GROUP_P (insn))
1374 while (SCHED_GROUP_P (prev))
1376 prev = PREV_INSN (prev);
1377 INSN_REF_COUNT (prev) += 1;
1381 for (prev = LOG_LINKS (insn); prev; prev = XEXP (prev, 1))
1383 rtx x = XEXP (prev, 0);
1385 /* A dependence pointing to a note is always obsolete, because
1386 sched_analyze_insn will have created any necessary new dependences
1387 which replace it. Notes can be created when instructions are
1388 deleted by insn splitting, or by register allocation. */
1389 if (GET_CODE (x) == NOTE)
1391 remove_dependence (insn, x);
1395 /* Clear the link cost adjustment bits. */
1396 LINK_COST_FREE (prev) = 0;
1398 LINK_COST_ZERO (prev) = 0;
1401 /* This priority calculation was chosen because it results in the
1402 least instruction movement, and does not hurt the performance
1403 of the resulting code compared to the old algorithm.
1404 This makes the sched algorithm more stable, which results
1405 in better code, because there is less register pressure,
1406 cross jumping is more likely to work, and debugging is easier.
1408 When all instructions have a latency of 1, there is no need to
1409 move any instructions. Subtracting one here ensures that in such
1410 cases all instructions will end up with a priority of one, and
1411 hence no scheduling will be done.
1413 The original code did not subtract the one, and added the
1414 insn_cost of the current instruction to its priority (e.g.
1415 move the insn_cost call down to the end). */
1417 if (REG_NOTE_KIND (prev) == 0)
1418 /* Data dependence. */
1419 prev_priority = priority (x) + insn_cost (x, prev, insn) - 1;
1421 /* Anti or output dependence. Don't add the latency of this
1422 insn's result, because it isn't being used. */
1423 prev_priority = priority (x);
1425 if (prev_priority > max_priority)
1426 max_priority = prev_priority;
1427 INSN_REF_COUNT (x) += 1;
1430 prepare_unit (insn_unit (insn));
1431 INSN_PRIORITY (insn) = max_priority;
1432 return INSN_PRIORITY (insn);
1437 /* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
1438 them to the unused_*_list variables, so that they can be reused. */
1441 free_pending_lists ()
1443 register rtx link, prev_link;
1445 if (pending_read_insns)
1447 prev_link = pending_read_insns;
1448 link = XEXP (prev_link, 1);
1453 link = XEXP (link, 1);
1456 XEXP (prev_link, 1) = unused_insn_list;
1457 unused_insn_list = pending_read_insns;
1458 pending_read_insns = 0;
1461 if (pending_write_insns)
1463 prev_link = pending_write_insns;
1464 link = XEXP (prev_link, 1);
1469 link = XEXP (link, 1);
1472 XEXP (prev_link, 1) = unused_insn_list;
1473 unused_insn_list = pending_write_insns;
1474 pending_write_insns = 0;
1477 if (pending_read_mems)
1479 prev_link = pending_read_mems;
1480 link = XEXP (prev_link, 1);
1485 link = XEXP (link, 1);
1488 XEXP (prev_link, 1) = unused_expr_list;
1489 unused_expr_list = pending_read_mems;
1490 pending_read_mems = 0;
1493 if (pending_write_mems)
1495 prev_link = pending_write_mems;
1496 link = XEXP (prev_link, 1);
1501 link = XEXP (link, 1);
1504 XEXP (prev_link, 1) = unused_expr_list;
1505 unused_expr_list = pending_write_mems;
1506 pending_write_mems = 0;
1510 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
1511 The MEM is a memory reference contained within INSN, which we are saving
1512 so that we can do memory aliasing on it. */
1515 add_insn_mem_dependence (insn_list, mem_list, insn, mem)
1516 rtx *insn_list, *mem_list, insn, mem;
1520 if (unused_insn_list)
1522 link = unused_insn_list;
1523 unused_insn_list = XEXP (link, 1);
1526 link = rtx_alloc (INSN_LIST);
1527 XEXP (link, 0) = insn;
1528 XEXP (link, 1) = *insn_list;
1531 if (unused_expr_list)
1533 link = unused_expr_list;
1534 unused_expr_list = XEXP (link, 1);
1537 link = rtx_alloc (EXPR_LIST);
1538 XEXP (link, 0) = mem;
1539 XEXP (link, 1) = *mem_list;
1542 pending_lists_length++;
1545 /* Make a dependency between every memory reference on the pending lists
1546 and INSN, thus flushing the pending lists. */
1549 flush_pending_lists (insn)
1554 while (pending_read_insns)
1556 add_dependence (insn, XEXP (pending_read_insns, 0), REG_DEP_ANTI);
1558 link = pending_read_insns;
1559 pending_read_insns = XEXP (pending_read_insns, 1);
1560 XEXP (link, 1) = unused_insn_list;
1561 unused_insn_list = link;
1563 link = pending_read_mems;
1564 pending_read_mems = XEXP (pending_read_mems, 1);
1565 XEXP (link, 1) = unused_expr_list;
1566 unused_expr_list = link;
1568 while (pending_write_insns)
1570 add_dependence (insn, XEXP (pending_write_insns, 0), REG_DEP_ANTI);
1572 link = pending_write_insns;
1573 pending_write_insns = XEXP (pending_write_insns, 1);
1574 XEXP (link, 1) = unused_insn_list;
1575 unused_insn_list = link;
1577 link = pending_write_mems;
1578 pending_write_mems = XEXP (pending_write_mems, 1);
1579 XEXP (link, 1) = unused_expr_list;
1580 unused_expr_list = link;
1582 pending_lists_length = 0;
1584 if (last_pending_memory_flush)
1585 add_dependence (insn, last_pending_memory_flush, REG_DEP_ANTI);
1587 last_pending_memory_flush = insn;
1590 /* Analyze a single SET or CLOBBER rtx, X, creating all dependencies generated
1591 by the write to the destination of X, and reads of everything mentioned. */
1594 sched_analyze_1 (x, insn)
1599 register rtx dest = SET_DEST (x);
1604 while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
1605 || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
1607 if (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
1609 /* The second and third arguments are values read by this insn. */
1610 sched_analyze_2 (XEXP (dest, 1), insn);
1611 sched_analyze_2 (XEXP (dest, 2), insn);
1613 dest = SUBREG_REG (dest);
1616 if (GET_CODE (dest) == REG)
1618 register int offset, bit, i;
1620 regno = REGNO (dest);
1622 /* A hard reg in a wide mode may really be multiple registers.
1623 If so, mark all of them just like the first. */
1624 if (regno < FIRST_PSEUDO_REGISTER)
1626 i = HARD_REGNO_NREGS (regno, GET_MODE (dest));
1631 for (u = reg_last_uses[regno+i]; u; u = XEXP (u, 1))
1632 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
1633 reg_last_uses[regno + i] = 0;
1634 if (reg_last_sets[regno + i])
1635 add_dependence (insn, reg_last_sets[regno + i],
1637 reg_last_sets[regno + i] = insn;
1638 if ((call_used_regs[i] || global_regs[i])
1639 && last_function_call)
1640 /* Function calls clobber all call_used regs. */
1641 add_dependence (insn, last_function_call, REG_DEP_ANTI);
1648 for (u = reg_last_uses[regno]; u; u = XEXP (u, 1))
1649 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
1650 reg_last_uses[regno] = 0;
1651 if (reg_last_sets[regno])
1652 add_dependence (insn, reg_last_sets[regno], REG_DEP_OUTPUT);
1653 reg_last_sets[regno] = insn;
1655 /* Pseudos that are REG_EQUIV to something may be replaced
1656 by that during reloading. We need only add dependencies for
1657 the address in the REG_EQUIV note. */
1658 if (! reload_completed
1659 && reg_known_equiv_p[regno]
1660 && GET_CODE (reg_known_value[regno]) == MEM)
1661 sched_analyze_2 (XEXP (reg_known_value[regno], 0), insn);
1663 /* Don't let it cross a call after scheduling if it doesn't
1664 already cross one. */
1665 if (reg_n_calls_crossed[regno] == 0 && last_function_call)
1666 add_dependence (insn, last_function_call, REG_DEP_ANTI);
1669 else if (GET_CODE (dest) == MEM)
1671 /* Writing memory. */
1673 if (pending_lists_length > 32)
1675 /* Flush all pending reads and writes to prevent the pending lists
1676 from getting any larger. Insn scheduling runs too slowly when
1677 these lists get long. The number 32 was chosen because it
1678 seems like a reasonable number. When compiling GCC with itself,
1679 this flush occurs 8 times for sparc, and 10 times for m88k using
1681 flush_pending_lists (insn);
1685 rtx pending, pending_mem;
1687 pending = pending_read_insns;
1688 pending_mem = pending_read_mems;
1691 /* If a dependency already exists, don't create a new one. */
1692 if (! find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
1693 if (anti_dependence (XEXP (pending_mem, 0), dest))
1694 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
1696 pending = XEXP (pending, 1);
1697 pending_mem = XEXP (pending_mem, 1);
1700 pending = pending_write_insns;
1701 pending_mem = pending_write_mems;
1704 /* If a dependency already exists, don't create a new one. */
1705 if (! find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
1706 if (output_dependence (XEXP (pending_mem, 0), dest))
1707 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
1709 pending = XEXP (pending, 1);
1710 pending_mem = XEXP (pending_mem, 1);
1713 if (last_pending_memory_flush)
1714 add_dependence (insn, last_pending_memory_flush, REG_DEP_ANTI);
1716 add_insn_mem_dependence (&pending_write_insns, &pending_write_mems,
1719 sched_analyze_2 (XEXP (dest, 0), insn);
1722 /* Analyze reads. */
1723 if (GET_CODE (x) == SET)
1724 sched_analyze_2 (SET_SRC (x), insn);
1727 /* Analyze the uses of memory and registers in rtx X in INSN. */
1730 sched_analyze_2 (x, insn)
1736 register enum rtx_code code;
1742 code = GET_CODE (x);
1751 /* Ignore constants. Note that we must handle CONST_DOUBLE here
1752 because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but
1753 this does not mean that this insn is using cc0. */
1761 /* There may be a note before this insn now, but all notes will
1762 be removed before we actually try to schedule the insns, so
1763 it won't cause a problem later. We must avoid it here though. */
1765 /* User of CC0 depends on immediately preceding insn. */
1766 SCHED_GROUP_P (insn) = 1;
1768 /* Make a copy of all dependencies on the immediately previous insn,
1769 and add to this insn. This is so that all the dependencies will
1770 apply to the group. Remove an explicit dependence on this insn
1771 as SCHED_GROUP_P now represents it. */
1773 prev = PREV_INSN (insn);
1774 while (GET_CODE (prev) == NOTE)
1775 prev = PREV_INSN (prev);
1777 if (find_insn_list (prev, LOG_LINKS (insn)))
1778 remove_dependence (insn, prev);
1780 for (link = LOG_LINKS (prev); link; link = XEXP (link, 1))
1781 add_dependence (insn, XEXP (link, 0), REG_NOTE_KIND (link));
1789 int regno = REGNO (x);
1790 if (regno < FIRST_PSEUDO_REGISTER)
1794 i = HARD_REGNO_NREGS (regno, GET_MODE (x));
1797 reg_last_uses[regno + i]
1798 = gen_rtx (INSN_LIST, VOIDmode,
1799 insn, reg_last_uses[regno + i]);
1800 if (reg_last_sets[regno + i])
1801 add_dependence (insn, reg_last_sets[regno + i], 0);
1802 if ((call_used_regs[regno + i] || global_regs[regno + i])
1803 && last_function_call)
1804 /* Function calls clobber all call_used regs. */
1805 add_dependence (insn, last_function_call, REG_DEP_ANTI);
1810 reg_last_uses[regno]
1811 = gen_rtx (INSN_LIST, VOIDmode, insn, reg_last_uses[regno]);
1812 if (reg_last_sets[regno])
1813 add_dependence (insn, reg_last_sets[regno], 0);
1815 /* Pseudos that are REG_EQUIV to something may be replaced
1816 by that during reloading. We need only add dependencies for
1817 the address in the REG_EQUIV note. */
1818 if (! reload_completed
1819 && reg_known_equiv_p[regno]
1820 && GET_CODE (reg_known_value[regno]) == MEM)
1821 sched_analyze_2 (XEXP (reg_known_value[regno], 0), insn);
1823 /* If the register does not already cross any calls, then add this
1824 insn to the sched_before_next_call list so that it will still
1825 not cross calls after scheduling. */
1826 if (reg_n_calls_crossed[regno] == 0)
1827 add_dependence (sched_before_next_call, insn, REG_DEP_ANTI);
1834 /* Reading memory. */
1836 rtx pending, pending_mem;
1838 pending = pending_read_insns;
1839 pending_mem = pending_read_mems;
1842 /* If a dependency already exists, don't create a new one. */
1843 if (! find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
1844 if (read_dependence (XEXP (pending_mem, 0), x))
1845 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
1847 pending = XEXP (pending, 1);
1848 pending_mem = XEXP (pending_mem, 1);
1851 pending = pending_write_insns;
1852 pending_mem = pending_write_mems;
1855 /* If a dependency already exists, don't create a new one. */
1856 if (! find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
1857 if (true_dependence (XEXP (pending_mem, 0), x))
1858 add_dependence (insn, XEXP (pending, 0), 0);
1860 pending = XEXP (pending, 1);
1861 pending_mem = XEXP (pending_mem, 1);
1863 if (last_pending_memory_flush)
1864 add_dependence (insn, last_pending_memory_flush, REG_DEP_ANTI);
1866 /* Always add these dependencies to pending_reads, since
1867 this insn may be followed by a write. */
1868 add_insn_mem_dependence (&pending_read_insns, &pending_read_mems,
1871 /* Take advantage of tail recursion here. */
1872 sched_analyze_2 (XEXP (x, 0), insn);
1878 case UNSPEC_VOLATILE:
1883 /* Traditional and volatile asm instructions must be considered to use
1884 and clobber all hard registers and all of memory. So must
1885 TRAP_IF and UNSPEC_VOLATILE operations. */
1886 if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
1888 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1890 for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
1891 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
1892 reg_last_uses[i] = 0;
1893 if (reg_last_sets[i])
1894 add_dependence (insn, reg_last_sets[i], 0);
1895 reg_last_sets[i] = insn;
1898 flush_pending_lists (insn);
1901 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
1902 We can not just fall through here since then we would be confused
1903 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
1904 traditional asms unlike their normal usage. */
1906 if (code == ASM_OPERANDS)
1908 for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
1909 sched_analyze_2 (ASM_OPERANDS_INPUT (x, j), insn);
1919 /* These both read and modify the result. We must handle them as writes
1920 to get proper dependencies for following instructions. We must handle
1921 them as reads to get proper dependencies from this to previous
1922 instructions. Thus we need to pass them to both sched_analyze_1
1923 and sched_analyze_2. We must call sched_analyze_2 first in order
1924 to get the proper antecedent for the read. */
1925 sched_analyze_2 (XEXP (x, 0), insn);
1926 sched_analyze_1 (x, insn);
1930 /* Other cases: walk the insn. */
1931 fmt = GET_RTX_FORMAT (code);
1932 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1935 sched_analyze_2 (XEXP (x, i), insn);
1936 else if (fmt[i] == 'E')
1937 for (j = 0; j < XVECLEN (x, i); j++)
1938 sched_analyze_2 (XVECEXP (x, i, j), insn);
1942 /* Analyze an INSN with pattern X to find all dependencies. */
1945 sched_analyze_insn (x, insn)
1948 register RTX_CODE code = GET_CODE (x);
1951 if (code == SET || code == CLOBBER)
1952 sched_analyze_1 (x, insn);
1953 else if (code == PARALLEL)
1956 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
1958 code = GET_CODE (XVECEXP (x, 0, i));
1959 if (code == SET || code == CLOBBER)
1960 sched_analyze_1 (XVECEXP (x, 0, i), insn);
1962 sched_analyze_2 (XVECEXP (x, 0, i), insn);
1966 sched_analyze_2 (x, insn);
1968 /* Handle function calls and function returns created by the epilogue
1970 if (GET_CODE (insn) == CALL_INSN || GET_CODE (insn) == JUMP_INSN)
1975 /* When scheduling instructions, we make sure calls don't lose their
1976 accompanying USE insns by depending them one on another in order.
1978 Also, we must do the same thing for returns created by the epilogue
1979 threading code. Note this code works only in this special case,
1980 because other passes make no guarantee that they will never emit
1981 an instruction between a USE and a RETURN. There is such a guarantee
1982 for USE instructions immediately before a call. */
1984 prev_dep_insn = insn;
1985 dep_insn = PREV_INSN (insn);
1986 while (GET_CODE (dep_insn) == INSN
1987 && GET_CODE (PATTERN (dep_insn)) == USE)
1989 SCHED_GROUP_P (prev_dep_insn) = 1;
1991 /* Make a copy of all dependencies on dep_insn, and add to insn.
1992 This is so that all of the dependencies will apply to the
1995 for (link = LOG_LINKS (dep_insn); link; link = XEXP (link, 1))
1996 add_dependence (insn, XEXP (link, 0), REG_NOTE_KIND (link));
1998 prev_dep_insn = dep_insn;
1999 dep_insn = PREV_INSN (dep_insn);
2004 /* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
2005 for every dependency. */
2008 sched_analyze (head, tail)
2012 register int n_insns = 0;
2014 register int luid = 0;
2016 for (insn = head; ; insn = NEXT_INSN (insn))
2018 INSN_LUID (insn) = luid++;
2020 if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
2022 sched_analyze_insn (PATTERN (insn), insn);
2025 else if (GET_CODE (insn) == CALL_INSN)
2031 /* Any instruction using a hard register which may get clobbered
2032 by a call needs to be marked as dependent on this call.
2033 This prevents a use of a hard return reg from being moved
2034 past a void call (i.e. it does not explicitly set the hard
2037 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2038 if (call_used_regs[i] || global_regs[i])
2040 for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
2041 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
2042 reg_last_uses[i] = 0;
2043 if (reg_last_sets[i])
2044 add_dependence (insn, reg_last_sets[i], REG_DEP_ANTI);
2045 reg_last_sets[i] = insn;
2046 /* Insn, being a CALL_INSN, magically depends on
2047 `last_function_call' already. */
2050 /* For each insn which shouldn't cross a call, add a dependence
2051 between that insn and this call insn. */
2052 x = LOG_LINKS (sched_before_next_call);
2055 add_dependence (insn, XEXP (x, 0), REG_DEP_ANTI);
2058 LOG_LINKS (sched_before_next_call) = 0;
2060 sched_analyze_insn (PATTERN (insn), insn);
2062 /* We don't need to flush memory for a function call which does
2063 not involve memory. */
2064 if (! CONST_CALL_P (insn))
2066 /* In the absence of interprocedural alias analysis,
2067 we must flush all pending reads and writes, and
2068 start new dependencies starting from here. */
2069 flush_pending_lists (insn);
2072 /* Depend this function call (actually, the user of this
2073 function call) on all hard register clobberage. */
2074 last_function_call = insn;
2083 /* Called when we see a set of a register. If death is true, then we are
2084 scanning backwards. Mark that register as unborn. If nobody says
2085 otherwise, that is how things will remain. If death is false, then we
2086 are scanning forwards. Mark that register as being born. */
2089 sched_note_set (b, x, death)
2094 register int regno, j;
2095 register rtx reg = SET_DEST (x);
2101 while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == STRICT_LOW_PART
2102 || GET_CODE (reg) == SIGN_EXTRACT || GET_CODE (reg) == ZERO_EXTRACT)
2104 /* Must treat modification of just one hardware register of a multi-reg
2105 value or just a byte field of a register exactly the same way that
2106 mark_set_1 in flow.c does, i.e. anything except a paradoxical subreg
2107 does not kill the entire register. */
2108 if (GET_CODE (reg) != SUBREG
2109 || REG_SIZE (SUBREG_REG (reg)) > REG_SIZE (reg))
2112 reg = SUBREG_REG (reg);
2115 if (GET_CODE (reg) != REG)
2118 /* Global registers are always live, so the code below does not apply
2121 regno = REGNO (reg);
2122 if (regno >= FIRST_PSEUDO_REGISTER || ! global_regs[regno])
2124 register int offset = regno / REGSET_ELT_BITS;
2125 register REGSET_ELT_TYPE bit
2126 = (REGSET_ELT_TYPE) 1 << (regno % REGSET_ELT_BITS);
2130 /* If we only set part of the register, then this set does not
2135 /* Try killing this register. */
2136 if (regno < FIRST_PSEUDO_REGISTER)
2138 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
2141 offset = (regno + j) / REGSET_ELT_BITS;
2142 bit = (REGSET_ELT_TYPE) 1 << ((regno + j) % REGSET_ELT_BITS);
2144 bb_live_regs[offset] &= ~bit;
2145 bb_dead_regs[offset] |= bit;
2150 bb_live_regs[offset] &= ~bit;
2151 bb_dead_regs[offset] |= bit;
2156 /* Make the register live again. */
2157 if (regno < FIRST_PSEUDO_REGISTER)
2159 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
2162 offset = (regno + j) / REGSET_ELT_BITS;
2163 bit = (REGSET_ELT_TYPE) 1 << ((regno + j) % REGSET_ELT_BITS);
2165 bb_live_regs[offset] |= bit;
2166 bb_dead_regs[offset] &= ~bit;
2171 bb_live_regs[offset] |= bit;
2172 bb_dead_regs[offset] &= ~bit;
2178 /* Macros and functions for keeping the priority queue sorted, and
2179 dealing with queueing and unqueueing of instructions. */
2181 #define SCHED_SORT(READY, NEW_READY, OLD_READY) \
2182 do { if ((NEW_READY) - (OLD_READY) == 1) \
2183 swap_sort (READY, NEW_READY); \
2184 else if ((NEW_READY) - (OLD_READY) > 1) \
2185 qsort (READY, NEW_READY, sizeof (rtx), rank_for_schedule); } \
2188 /* Returns a positive value if y is preferred; returns a negative value if
2189 x is preferred. Should never return 0, since that will make the sort
2193 rank_for_schedule (x, y)
2199 int tmp_class, tmp2_class;
2202 /* Choose the instruction with the highest priority, if different. */
2203 if (value = INSN_PRIORITY (tmp) - INSN_PRIORITY (tmp2))
2206 if (last_scheduled_insn)
2208 /* Classify the instructions into three classes:
2209 1) Data dependent on last schedule insn.
2210 2) Anti/Output dependent on last scheduled insn.
2211 3) Independent of last scheduled insn, or has latency of one.
2212 Choose the insn from the highest numbered class if different. */
2213 link = find_insn_list (tmp, LOG_LINKS (last_scheduled_insn));
2214 if (link == 0 || insn_cost (tmp, link, last_scheduled_insn) == 1)
2216 else if (REG_NOTE_KIND (link) == 0) /* Data dependence. */
2221 link = find_insn_list (tmp2, LOG_LINKS (last_scheduled_insn));
2222 if (link == 0 || insn_cost (tmp2, link, last_scheduled_insn) == 1)
2224 else if (REG_NOTE_KIND (link) == 0) /* Data dependence. */
2229 if (value = tmp_class - tmp2_class)
2233 /* If insns are equally good, sort by INSN_LUID (original insn order),
2234 so that we make the sort stable. This minimizes instruction movement,
2235 thus minimizing sched's effect on debugging and cross-jumping. */
2236 return INSN_LUID (tmp) - INSN_LUID (tmp2);
2239 /* Resort the array A in which only element at index N may be out of order. */
2241 __inline static void
2249 while (i >= 0 && rank_for_schedule (a+i, &insn) >= 0)
2257 static int max_priority;
2259 /* Add INSN to the insn queue so that it fires at least N_CYCLES
2260 before the currently executing insn. */
2262 __inline static void
2263 queue_insn (insn, n_cycles)
2267 int next_q = NEXT_Q_AFTER (q_ptr, n_cycles);
2268 NEXT_INSN (insn) = insn_queue[next_q];
2269 insn_queue[next_q] = insn;
2273 /* Return nonzero if PAT is the pattern of an insn which makes a
2277 birthing_insn_p (pat)
2282 if (reload_completed == 1)
2285 if (GET_CODE (pat) == SET
2286 && GET_CODE (SET_DEST (pat)) == REG)
2288 rtx dest = SET_DEST (pat);
2289 int i = REGNO (dest);
2290 int offset = i / REGSET_ELT_BITS;
2291 REGSET_ELT_TYPE bit = (REGSET_ELT_TYPE) 1 << (i % REGSET_ELT_BITS);
2293 /* It would be more accurate to use refers_to_regno_p or
2294 reg_mentioned_p to determine when the dest is not live before this
2297 if (bb_live_regs[offset] & bit)
2298 return (reg_n_sets[i] == 1);
2302 if (GET_CODE (pat) == PARALLEL)
2304 for (j = 0; j < XVECLEN (pat, 0); j++)
2305 if (birthing_insn_p (XVECEXP (pat, 0, j)))
2311 /* PREV is an insn that is ready to execute. Adjust its priority if that
2312 will help shorten register lifetimes. */
2314 __inline static void
2315 adjust_priority (prev)
2318 /* Trying to shorten register lives after reload has completed
2319 is useless and wrong. It gives inaccurate schedules. */
2320 if (reload_completed == 0)
2325 /* ??? This code has no effect, because REG_DEAD notes are removed
2326 before we ever get here. */
2327 for (note = REG_NOTES (prev); note; note = XEXP (note, 1))
2328 if (REG_NOTE_KIND (note) == REG_DEAD)
2331 /* Defer scheduling insns which kill registers, since that
2332 shortens register lives. Prefer scheduling insns which
2333 make registers live for the same reason. */
2337 INSN_PRIORITY (prev) >>= 3;
2340 INSN_PRIORITY (prev) >>= 2;
2344 INSN_PRIORITY (prev) >>= 1;
2347 if (birthing_insn_p (PATTERN (prev)))
2349 int max = max_priority;
2351 if (max > INSN_PRIORITY (prev))
2352 INSN_PRIORITY (prev) = max;
2359 /* INSN is the "currently executing insn". Launch each insn which was
2360 waiting on INSN (in the backwards dataflow sense). READY is a
2361 vector of insns which are ready to fire. N_READY is the number of
2362 elements in READY. CLOCK is the current virtual cycle. */
2365 schedule_insn (insn, ready, n_ready, clock)
2372 int new_ready = n_ready;
2374 if (MAX_BLOCKAGE > 1)
2375 schedule_unit (insn_unit (insn), insn, clock);
2377 if (LOG_LINKS (insn) == 0)
2380 /* This is used by the function adjust_priority above. */
2382 max_priority = MAX (INSN_PRIORITY (ready[0]), INSN_PRIORITY (insn));
2384 max_priority = INSN_PRIORITY (insn);
2386 for (link = LOG_LINKS (insn); link != 0; link = XEXP (link, 1))
2388 rtx prev = XEXP (link, 0);
2389 int cost = insn_cost (prev, link, insn);
2391 if ((INSN_REF_COUNT (prev) -= 1) != 0)
2393 /* We satisfied one requirement to fire PREV. Record the earliest
2394 time when PREV can fire. No need to do this if the cost is 1,
2395 because PREV can fire no sooner than the next cycle. */
2397 INSN_TICK (prev) = MAX (INSN_TICK (prev), clock + cost);
2401 /* We satisfied the last requirement to fire PREV. Ensure that all
2402 timing requirements are satisfied. */
2403 if (INSN_TICK (prev) - clock > cost)
2404 cost = INSN_TICK (prev) - clock;
2406 /* Adjust the priority of PREV and either put it on the ready
2407 list or queue it. */
2408 adjust_priority (prev);
2410 ready[new_ready++] = prev;
2412 queue_insn (prev, cost);
2419 /* Given N_READY insns in the ready list READY at time CLOCK, queue
2420 those that are blocked due to function unit hazards and rearrange
2421 the remaining ones to minimize subsequent function unit hazards. */
2424 schedule_select (ready, n_ready, clock, file)
2429 int pri = INSN_PRIORITY (ready[0]);
2430 int i, j, k, q, cost, best_cost, best_insn = 0, new_ready = n_ready;
2433 /* Work down the ready list in groups of instructions with the same
2434 priority value. Queue insns in the group that are blocked and
2435 select among those that remain for the one with the largest
2436 potential hazard. */
2437 for (i = 0; i < n_ready; i = j)
2440 for (j = i + 1; j < n_ready; j++)
2441 if ((pri = INSN_PRIORITY (ready[j])) != opri)
2444 /* Queue insns in the group that are blocked. */
2445 for (k = i, q = 0; k < j; k++)
2448 if ((cost = actual_hazard (insn_unit (insn), insn, clock, 0)) != 0)
2452 queue_insn (insn, cost);
2454 fprintf (file, "\n;; blocking insn %d for %d cycles",
2455 INSN_UID (insn), cost);
2460 /* Check the next group if all insns were queued. */
2464 /* If more than one remains, select the first one with the largest
2465 potential hazard. */
2466 else if (j - i - q > 1)
2469 for (k = i; k < j; k++)
2471 if ((insn = ready[k]) == 0)
2473 if ((cost = potential_hazard (insn_unit (insn), insn, 0))
2481 /* We have found a suitable insn to schedule. */
2485 /* Move the best insn to be front of the ready list. */
2490 fprintf (file, ", now");
2491 for (i = 0; i < n_ready; i++)
2493 fprintf (file, " %d", INSN_UID (ready[i]));
2494 fprintf (file, "\n;; insn %d has a greater potential hazard",
2495 INSN_UID (ready[best_insn]));
2497 for (i = best_insn; i > 0; i--)
2500 ready[i-1] = ready[i];
2505 /* Compact the ready list. */
2506 if (new_ready < n_ready)
2507 for (i = j = 0; i < n_ready; i++)
2509 ready[j++] = ready[i];
2514 /* Add a REG_DEAD note for REG to INSN, reusing a REG_DEAD note from the
2518 create_reg_dead_note (reg, insn)
2523 /* The number of registers killed after scheduling must be the same as the
2524 number of registers killed before scheduling. The number of REG_DEAD
2525 notes may not be conserved, i.e. two SImode hard register REG_DEAD notes
2526 might become one DImode hard register REG_DEAD note, but the number of
2527 registers killed will be conserved.
2529 We carefully remove REG_DEAD notes from the dead_notes list, so that
2530 there will be none left at the end. If we run out early, then there
2531 is a bug somewhere in flow, combine and/or sched. */
2533 if (dead_notes == 0)
2538 link = rtx_alloc (EXPR_LIST);
2539 PUT_REG_NOTE_KIND (link, REG_DEAD);
2544 /* Number of regs killed by REG. */
2545 int regs_killed = (REGNO (reg) >= FIRST_PSEUDO_REGISTER ? 1
2546 : HARD_REGNO_NREGS (REGNO (reg), GET_MODE (reg)));
2547 /* Number of regs killed by REG_DEAD notes taken off the list. */
2551 reg_note_regs = (REGNO (XEXP (link, 0)) >= FIRST_PSEUDO_REGISTER ? 1
2552 : HARD_REGNO_NREGS (REGNO (XEXP (link, 0)),
2553 GET_MODE (XEXP (link, 0))));
2554 while (reg_note_regs < regs_killed)
2556 link = XEXP (link, 1);
2557 reg_note_regs += (REGNO (XEXP (link, 0)) >= FIRST_PSEUDO_REGISTER ? 1
2558 : HARD_REGNO_NREGS (REGNO (XEXP (link, 0)),
2559 GET_MODE (XEXP (link, 0))));
2561 dead_notes = XEXP (link, 1);
2563 /* If we took too many regs kills off, put the extra ones back. */
2564 while (reg_note_regs > regs_killed)
2566 rtx temp_reg, temp_link;
2568 temp_reg = gen_rtx (REG, word_mode, 0);
2569 temp_link = rtx_alloc (EXPR_LIST);
2570 PUT_REG_NOTE_KIND (temp_link, REG_DEAD);
2571 XEXP (temp_link, 0) = temp_reg;
2572 XEXP (temp_link, 1) = dead_notes;
2573 dead_notes = temp_link;
2578 XEXP (link, 0) = reg;
2579 XEXP (link, 1) = REG_NOTES (insn);
2580 REG_NOTES (insn) = link;
2583 /* Subroutine on attach_deaths_insn--handles the recursive search
2584 through INSN. If SET_P is true, then x is being modified by the insn. */
2587 attach_deaths (x, insn, set_p)
2594 register enum rtx_code code;
2600 code = GET_CODE (x);
2612 /* Get rid of the easy cases first. */
2617 /* If the register dies in this insn, queue that note, and mark
2618 this register as needing to die. */
2619 /* This code is very similar to mark_used_1 (if set_p is false)
2620 and mark_set_1 (if set_p is true) in flow.c. */
2622 register int regno = REGNO (x);
2623 register int offset = regno / REGSET_ELT_BITS;
2624 register REGSET_ELT_TYPE bit
2625 = (REGSET_ELT_TYPE) 1 << (regno % REGSET_ELT_BITS);
2626 REGSET_ELT_TYPE all_needed = (old_live_regs[offset] & bit);
2627 REGSET_ELT_TYPE some_needed = (old_live_regs[offset] & bit);
2632 if (regno < FIRST_PSEUDO_REGISTER)
2636 n = HARD_REGNO_NREGS (regno, GET_MODE (x));
2639 some_needed |= (old_live_regs[(regno + n) / REGSET_ELT_BITS]
2640 & ((REGSET_ELT_TYPE) 1
2641 << ((regno + n) % REGSET_ELT_BITS)));
2642 all_needed &= (old_live_regs[(regno + n) / REGSET_ELT_BITS]
2643 & ((REGSET_ELT_TYPE) 1
2644 << ((regno + n) % REGSET_ELT_BITS)));
2648 /* If it wasn't live before we started, then add a REG_DEAD note.
2649 We must check the previous lifetime info not the current info,
2650 because we may have to execute this code several times, e.g.
2651 once for a clobber (which doesn't add a note) and later
2652 for a use (which does add a note).
2654 Always make the register live. We must do this even if it was
2655 live before, because this may be an insn which sets and uses
2656 the same register, in which case the register has already been
2657 killed, so we must make it live again.
2659 Global registers are always live, and should never have a REG_DEAD
2660 note added for them, so none of the code below applies to them. */
2662 if (regno >= FIRST_PSEUDO_REGISTER || ! global_regs[regno])
2664 /* Never add REG_DEAD notes for the FRAME_POINTER_REGNUM or the
2665 STACK_POINTER_REGNUM, since these are always considered to be
2666 live. Similarly for ARG_POINTER_REGNUM if it is fixed. */
2667 if (regno != FRAME_POINTER_REGNUM
2668 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
2669 && ! (regno == HARD_FRAME_POINTER_REGNUM)
2671 #if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
2672 && ! (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
2674 && regno != STACK_POINTER_REGNUM)
2676 if (! all_needed && ! dead_or_set_p (insn, x))
2678 /* If none of the words in X is needed, make a REG_DEAD
2679 note. Otherwise, we must make partial REG_DEAD
2682 create_reg_dead_note (x, insn);
2687 /* Don't make a REG_DEAD note for a part of a
2688 register that is set in the insn. */
2689 for (i = HARD_REGNO_NREGS (regno, GET_MODE (x)) - 1;
2691 if ((old_live_regs[(regno + i) / REGSET_ELT_BITS]
2692 & ((REGSET_ELT_TYPE) 1
2693 << ((regno +i) % REGSET_ELT_BITS))) == 0
2694 && ! dead_or_set_regno_p (insn, regno + i))
2695 create_reg_dead_note (gen_rtx (REG, word_mode,
2702 if (regno < FIRST_PSEUDO_REGISTER)
2704 int j = HARD_REGNO_NREGS (regno, GET_MODE (x));
2707 offset = (regno + j) / REGSET_ELT_BITS;
2709 = (REGSET_ELT_TYPE) 1 << ((regno + j) % REGSET_ELT_BITS);
2711 bb_dead_regs[offset] &= ~bit;
2712 bb_live_regs[offset] |= bit;
2717 bb_dead_regs[offset] &= ~bit;
2718 bb_live_regs[offset] |= bit;
2725 /* Handle tail-recursive case. */
2726 attach_deaths (XEXP (x, 0), insn, 0);
2730 case STRICT_LOW_PART:
2731 /* These two cases preserve the value of SET_P, so handle them
2733 attach_deaths (XEXP (x, 0), insn, set_p);
2738 /* This case preserves the value of SET_P for the first operand, but
2739 clears it for the other two. */
2740 attach_deaths (XEXP (x, 0), insn, set_p);
2741 attach_deaths (XEXP (x, 1), insn, 0);
2742 attach_deaths (XEXP (x, 2), insn, 0);
2746 /* Other cases: walk the insn. */
2747 fmt = GET_RTX_FORMAT (code);
2748 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2751 attach_deaths (XEXP (x, i), insn, 0);
2752 else if (fmt[i] == 'E')
2753 for (j = 0; j < XVECLEN (x, i); j++)
2754 attach_deaths (XVECEXP (x, i, j), insn, 0);
2759 /* After INSN has executed, add register death notes for each register
2760 that is dead after INSN. */
2763 attach_deaths_insn (insn)
2766 rtx x = PATTERN (insn);
2767 register RTX_CODE code = GET_CODE (x);
2771 attach_deaths (SET_SRC (x), insn, 0);
2773 /* A register might die here even if it is the destination, e.g.
2774 it is the target of a volatile read and is otherwise unused.
2775 Hence we must always call attach_deaths for the SET_DEST. */
2776 attach_deaths (SET_DEST (x), insn, 1);
2778 else if (code == PARALLEL)
2781 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
2783 code = GET_CODE (XVECEXP (x, 0, i));
2786 attach_deaths (SET_SRC (XVECEXP (x, 0, i)), insn, 0);
2788 attach_deaths (SET_DEST (XVECEXP (x, 0, i)), insn, 1);
2790 /* Flow does not add REG_DEAD notes to registers that die in
2791 clobbers, so we can't either. */
2792 else if (code != CLOBBER)
2793 attach_deaths (XVECEXP (x, 0, i), insn, 0);
2796 /* Flow does not add REG_DEAD notes to registers that die in
2797 clobbers, so we can't either. */
2798 else if (code != CLOBBER)
2799 attach_deaths (x, insn, 0);
2802 /* Delete notes beginning with INSN and maybe put them in the chain
2803 of notes ended by NOTE_LIST.
2804 Returns the insn following the notes. */
2807 unlink_notes (insn, tail)
2810 rtx prev = PREV_INSN (insn);
2812 while (insn != tail && GET_CODE (insn) == NOTE)
2814 rtx next = NEXT_INSN (insn);
2815 /* Delete the note from its current position. */
2817 NEXT_INSN (prev) = next;
2819 PREV_INSN (next) = prev;
2821 if (write_symbols != NO_DEBUG && NOTE_LINE_NUMBER (insn) > 0)
2822 /* Record line-number notes so they can be reused. */
2823 LINE_NOTE (insn) = insn;
2826 /* Insert the note at the end of the notes list. */
2827 PREV_INSN (insn) = note_list;
2829 NEXT_INSN (note_list) = insn;
2838 /* Data structure for keeping track of register information
2839 during that register's life. */
2843 short offset; short bit;
2844 short live_length; short calls_crossed;
2847 /* Constructor for `sometimes' data structure. */
2850 new_sometimes_live (regs_sometimes_live, offset, bit, sometimes_max)
2851 struct sometimes *regs_sometimes_live;
2855 register struct sometimes *p;
2856 register int regno = offset * REGSET_ELT_BITS + bit;
2859 /* There should never be a register greater than max_regno here. If there
2860 is, it means that a define_split has created a new pseudo reg. This
2861 is not allowed, since there will not be flow info available for any
2862 new register, so catch the error here. */
2863 if (regno >= max_regno)
2866 p = ®s_sometimes_live[sometimes_max];
2870 p->calls_crossed = 0;
2872 return sometimes_max;
2875 /* Count lengths of all regs we are currently tracking,
2876 and find new registers no longer live. */
2879 finish_sometimes_live (regs_sometimes_live, sometimes_max)
2880 struct sometimes *regs_sometimes_live;
2885 for (i = 0; i < sometimes_max; i++)
2887 register struct sometimes *p = ®s_sometimes_live[i];
2890 regno = p->offset * REGSET_ELT_BITS + p->bit;
2892 sched_reg_live_length[regno] += p->live_length;
2893 sched_reg_n_calls_crossed[regno] += p->calls_crossed;
2897 /* Use modified list scheduling to rearrange insns in basic block
2898 B. FILE, if nonzero, is where we dump interesting output about
2902 schedule_block (b, file)
2909 int i, j, n_ready = 0, new_ready, n_insns = 0;
2910 int sched_n_insns = 0;
2912 #define NEED_NOTHING 0
2917 /* HEAD and TAIL delimit the region being scheduled. */
2918 rtx head = basic_block_head[b];
2919 rtx tail = basic_block_end[b];
2920 /* PREV_HEAD and NEXT_TAIL are the boundaries of the insns
2921 being scheduled. When the insns have been ordered,
2922 these insns delimit where the new insns are to be
2923 spliced back into the insn chain. */
2927 /* Keep life information accurate. */
2928 register struct sometimes *regs_sometimes_live;
2932 fprintf (file, ";;\t -- basic block number %d from %d to %d --\n",
2933 b, INSN_UID (basic_block_head[b]), INSN_UID (basic_block_end[b]));
2936 reg_last_uses = (rtx *) alloca (i * sizeof (rtx));
2937 bzero (reg_last_uses, i * sizeof (rtx));
2938 reg_last_sets = (rtx *) alloca (i * sizeof (rtx));
2939 bzero (reg_last_sets, i * sizeof (rtx));
2942 /* Remove certain insns at the beginning from scheduling,
2943 by advancing HEAD. */
2945 /* At the start of a function, before reload has run, don't delay getting
2946 parameters from hard registers into pseudo registers. */
2947 if (reload_completed == 0 && b == 0)
2950 && GET_CODE (head) == NOTE
2951 && NOTE_LINE_NUMBER (head) != NOTE_INSN_FUNCTION_BEG)
2952 head = NEXT_INSN (head);
2954 && GET_CODE (head) == INSN
2955 && GET_CODE (PATTERN (head)) == SET)
2957 rtx src = SET_SRC (PATTERN (head));
2958 while (GET_CODE (src) == SUBREG
2959 || GET_CODE (src) == SIGN_EXTEND
2960 || GET_CODE (src) == ZERO_EXTEND
2961 || GET_CODE (src) == SIGN_EXTRACT
2962 || GET_CODE (src) == ZERO_EXTRACT)
2963 src = XEXP (src, 0);
2964 if (GET_CODE (src) != REG
2965 || REGNO (src) >= FIRST_PSEUDO_REGISTER)
2967 /* Keep this insn from ever being scheduled. */
2968 INSN_REF_COUNT (head) = 1;
2969 head = NEXT_INSN (head);
2973 /* Don't include any notes or labels at the beginning of the
2974 basic block, or notes at the ends of basic blocks. */
2975 while (head != tail)
2977 if (GET_CODE (head) == NOTE)
2978 head = NEXT_INSN (head);
2979 else if (GET_CODE (tail) == NOTE)
2980 tail = PREV_INSN (tail);
2981 else if (GET_CODE (head) == CODE_LABEL)
2982 head = NEXT_INSN (head);
2985 /* If the only insn left is a NOTE or a CODE_LABEL, then there is no need
2986 to schedule this block. */
2988 && (GET_CODE (head) == NOTE || GET_CODE (head) == CODE_LABEL))
2992 /* This short-cut doesn't work. It does not count call insns crossed by
2993 registers in reg_sometimes_live. It does not mark these registers as
2994 dead if they die in this block. It does not mark these registers live
2995 (or create new reg_sometimes_live entries if necessary) if they are born
2998 The easy solution is to just always schedule a block. This block only
2999 has one insn, so this won't slow down this pass by much. */
3005 /* Now HEAD through TAIL are the insns actually to be rearranged;
3006 Let PREV_HEAD and NEXT_TAIL enclose them. */
3007 prev_head = PREV_INSN (head);
3008 next_tail = NEXT_INSN (tail);
3010 /* Initialize basic block data structures. */
3012 pending_read_insns = 0;
3013 pending_read_mems = 0;
3014 pending_write_insns = 0;
3015 pending_write_mems = 0;
3016 pending_lists_length = 0;
3017 last_pending_memory_flush = 0;
3018 last_function_call = 0;
3019 last_scheduled_insn = 0;
3021 LOG_LINKS (sched_before_next_call) = 0;
3023 n_insns += sched_analyze (head, tail);
3026 free_pending_lists ();
3030 /* Allocate vector to hold insns to be rearranged (except those
3031 insns which are controlled by an insn with SCHED_GROUP_P set).
3032 All these insns are included between ORIG_HEAD and ORIG_TAIL,
3033 as those variables ultimately are set up. */
3034 ready = (rtx *) alloca ((n_insns+1) * sizeof (rtx));
3036 /* TAIL is now the last of the insns to be rearranged.
3037 Put those insns into the READY vector. */
3040 /* For all branches, calls, uses, and cc0 setters, force them to remain
3041 in order at the end of the block by adding dependencies and giving
3042 the last a high priority. There may be notes present, and prev_head
3045 Branches must obviously remain at the end. Calls should remain at the
3046 end since moving them results in worse register allocation. Uses remain
3047 at the end to ensure proper register allocation. cc0 setters remaim
3048 at the end because they can't be moved away from their cc0 user. */
3050 while (GET_CODE (insn) == CALL_INSN || GET_CODE (insn) == JUMP_INSN
3051 || (GET_CODE (insn) == INSN
3052 && (GET_CODE (PATTERN (insn)) == USE
3054 || sets_cc0_p (PATTERN (insn))
3057 || GET_CODE (insn) == NOTE)
3059 if (GET_CODE (insn) != NOTE)
3064 ready[n_ready++] = insn;
3065 INSN_PRIORITY (insn) = TAIL_PRIORITY - i;
3066 INSN_REF_COUNT (insn) = 0;
3068 else if (! find_insn_list (insn, LOG_LINKS (last)))
3070 add_dependence (last, insn, REG_DEP_ANTI);
3071 INSN_REF_COUNT (insn)++;
3075 /* Skip over insns that are part of a group. */
3076 while (SCHED_GROUP_P (insn))
3078 insn = prev_nonnote_insn (insn);
3083 insn = PREV_INSN (insn);
3084 /* Don't overrun the bounds of the basic block. */
3085 if (insn == prev_head)
3089 /* Assign priorities to instructions. Also check whether they
3090 are in priority order already. If so then I will be nonnegative.
3091 We use this shortcut only before reloading. */
3093 i = reload_completed ? DONE_PRIORITY : MAX_PRIORITY;
3096 for (; insn != prev_head; insn = PREV_INSN (insn))
3098 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
3101 if (INSN_REF_COUNT (insn) == 0)
3104 ready[n_ready++] = insn;
3107 /* Make this dependent on the last of the instructions
3108 that must remain in order at the end of the block. */
3109 add_dependence (last, insn, REG_DEP_ANTI);
3110 INSN_REF_COUNT (insn) = 1;
3113 if (SCHED_GROUP_P (insn))
3115 while (SCHED_GROUP_P (insn))
3117 insn = PREV_INSN (insn);
3118 while (GET_CODE (insn) == NOTE)
3119 insn = PREV_INSN (insn);
3127 if (INSN_PRIORITY (insn) < i)
3128 i = INSN_PRIORITY (insn);
3129 else if (INSN_PRIORITY (insn) > i)
3136 /* This short-cut doesn't work. It does not count call insns crossed by
3137 registers in reg_sometimes_live. It does not mark these registers as
3138 dead if they die in this block. It does not mark these registers live
3139 (or create new reg_sometimes_live entries if necessary) if they are born
3142 The easy solution is to just always schedule a block. These blocks tend
3143 to be very short, so this doesn't slow down this pass by much. */
3145 /* If existing order is good, don't bother to reorder. */
3146 if (i != DONE_PRIORITY)
3149 fprintf (file, ";; already scheduled\n");
3151 if (reload_completed == 0)
3153 for (i = 0; i < sometimes_max; i++)
3154 regs_sometimes_live[i].live_length += n_insns;
3156 finish_sometimes_live (regs_sometimes_live, sometimes_max);
3158 free_pending_lists ();
3163 /* Scan all the insns to be scheduled, removing NOTE insns
3164 and register death notes.
3165 Line number NOTE insns end up in NOTE_LIST.
3166 Register death notes end up in DEAD_NOTES.
3168 Recreate the register life information for the end of this basic
3171 if (reload_completed == 0)
3173 bcopy (basic_block_live_at_start[b], bb_live_regs, regset_bytes);
3174 bzero (bb_dead_regs, regset_bytes);
3178 /* This is the first block in the function. There may be insns
3179 before head that we can't schedule. We still need to examine
3180 them though for accurate register lifetime analysis. */
3182 /* We don't want to remove any REG_DEAD notes as the code below
3185 for (insn = basic_block_head[b]; insn != head;
3186 insn = NEXT_INSN (insn))
3187 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
3189 /* See if the register gets born here. */
3190 /* We must check for registers being born before we check for
3191 registers dying. It is possible for a register to be born
3192 and die in the same insn, e.g. reading from a volatile
3193 memory location into an otherwise unused register. Such
3194 a register must be marked as dead after this insn. */
3195 if (GET_CODE (PATTERN (insn)) == SET
3196 || GET_CODE (PATTERN (insn)) == CLOBBER)
3197 sched_note_set (b, PATTERN (insn), 0);
3198 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
3201 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
3202 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
3203 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
3204 sched_note_set (b, XVECEXP (PATTERN (insn), 0, j), 0);
3206 /* ??? This code is obsolete and should be deleted. It
3207 is harmless though, so we will leave it in for now. */
3208 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
3209 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == USE)
3210 sched_note_set (b, XVECEXP (PATTERN (insn), 0, j), 0);
3213 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
3215 if ((REG_NOTE_KIND (link) == REG_DEAD
3216 || REG_NOTE_KIND (link) == REG_UNUSED)
3217 /* Verify that the REG_NOTE has a legal value. */
3218 && GET_CODE (XEXP (link, 0)) == REG)
3220 register int regno = REGNO (XEXP (link, 0));
3221 register int offset = regno / REGSET_ELT_BITS;
3222 register REGSET_ELT_TYPE bit
3223 = (REGSET_ELT_TYPE) 1 << (regno % REGSET_ELT_BITS);
3225 if (regno < FIRST_PSEUDO_REGISTER)
3227 int j = HARD_REGNO_NREGS (regno,
3228 GET_MODE (XEXP (link, 0)));
3231 offset = (regno + j) / REGSET_ELT_BITS;
3232 bit = ((REGSET_ELT_TYPE) 1
3233 << ((regno + j) % REGSET_ELT_BITS));
3235 bb_live_regs[offset] &= ~bit;
3236 bb_dead_regs[offset] |= bit;
3241 bb_live_regs[offset] &= ~bit;
3242 bb_dead_regs[offset] |= bit;
3250 /* If debugging information is being produced, keep track of the line
3251 number notes for each insn. */
3252 if (write_symbols != NO_DEBUG)
3254 /* We must use the true line number for the first insn in the block
3255 that was computed and saved at the start of this pass. We can't
3256 use the current line number, because scheduling of the previous
3257 block may have changed the current line number. */
3258 rtx line = line_note_head[b];
3260 for (insn = basic_block_head[b];
3262 insn = NEXT_INSN (insn))
3263 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
3266 LINE_NOTE (insn) = line;
3269 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
3271 rtx prev, next, link;
3273 /* Farm out notes. This is needed to keep the debugger from
3274 getting completely deranged. */
3275 if (GET_CODE (insn) == NOTE)
3278 insn = unlink_notes (insn, next_tail);
3283 if (insn == next_tail)
3287 if (reload_completed == 0
3288 && GET_RTX_CLASS (GET_CODE (insn)) == 'i')
3290 /* See if the register gets born here. */
3291 /* We must check for registers being born before we check for
3292 registers dying. It is possible for a register to be born and
3293 die in the same insn, e.g. reading from a volatile memory
3294 location into an otherwise unused register. Such a register
3295 must be marked as dead after this insn. */
3296 if (GET_CODE (PATTERN (insn)) == SET
3297 || GET_CODE (PATTERN (insn)) == CLOBBER)
3298 sched_note_set (b, PATTERN (insn), 0);
3299 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
3302 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
3303 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
3304 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
3305 sched_note_set (b, XVECEXP (PATTERN (insn), 0, j), 0);
3307 /* ??? This code is obsolete and should be deleted. It
3308 is harmless though, so we will leave it in for now. */
3309 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
3310 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == USE)
3311 sched_note_set (b, XVECEXP (PATTERN (insn), 0, j), 0);
3314 /* Need to know what registers this insn kills. */
3315 for (prev = 0, link = REG_NOTES (insn); link; link = next)
3319 next = XEXP (link, 1);
3320 if ((REG_NOTE_KIND (link) == REG_DEAD
3321 || REG_NOTE_KIND (link) == REG_UNUSED)
3322 /* Verify that the REG_NOTE has a legal value. */
3323 && GET_CODE (XEXP (link, 0)) == REG)
3325 register int regno = REGNO (XEXP (link, 0));
3326 register int offset = regno / REGSET_ELT_BITS;
3327 register REGSET_ELT_TYPE bit
3328 = (REGSET_ELT_TYPE) 1 << (regno % REGSET_ELT_BITS);
3330 /* Only unlink REG_DEAD notes; leave REG_UNUSED notes
3332 if (REG_NOTE_KIND (link) == REG_DEAD)
3335 XEXP (prev, 1) = next;
3337 REG_NOTES (insn) = next;
3338 XEXP (link, 1) = dead_notes;
3344 if (regno < FIRST_PSEUDO_REGISTER)
3346 int j = HARD_REGNO_NREGS (regno,
3347 GET_MODE (XEXP (link, 0)));
3350 offset = (regno + j) / REGSET_ELT_BITS;
3351 bit = ((REGSET_ELT_TYPE) 1
3352 << ((regno + j) % REGSET_ELT_BITS));
3354 bb_live_regs[offset] &= ~bit;
3355 bb_dead_regs[offset] |= bit;
3360 bb_live_regs[offset] &= ~bit;
3361 bb_dead_regs[offset] |= bit;
3370 if (reload_completed == 0)
3372 /* Keep track of register lives. */
3373 old_live_regs = (regset) alloca (regset_bytes);
3375 = (struct sometimes *) alloca (max_regno * sizeof (struct sometimes));
3378 /* Start with registers live at end. */
3379 for (j = 0; j < regset_size; j++)
3381 REGSET_ELT_TYPE live = bb_live_regs[j];
3382 old_live_regs[j] = live;
3386 for (bit = 0; bit < REGSET_ELT_BITS; bit++)
3387 if (live & ((REGSET_ELT_TYPE) 1 << bit))
3388 sometimes_max = new_sometimes_live (regs_sometimes_live, j,
3389 bit, sometimes_max);
3394 SCHED_SORT (ready, n_ready, 1);
3398 fprintf (file, ";; ready list initially:\n;; ");
3399 for (i = 0; i < n_ready; i++)
3400 fprintf (file, "%d ", INSN_UID (ready[i]));
3401 fprintf (file, "\n\n");
3403 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
3404 if (INSN_PRIORITY (insn) > 0)
3405 fprintf (file, ";; insn[%4d]: priority = %4d, ref_count = %4d\n",
3406 INSN_UID (insn), INSN_PRIORITY (insn),
3407 INSN_REF_COUNT (insn));
3410 /* Now HEAD and TAIL are going to become disconnected
3411 entirely from the insn chain. */
3414 /* Q_SIZE will always be zero here. */
3415 q_ptr = 0; clock = 0;
3416 bzero (insn_queue, sizeof (insn_queue));
3418 /* Now, perform list scheduling. */
3420 /* Where we start inserting insns is after TAIL. */
3423 new_needs = (NEXT_INSN (prev_head) == basic_block_head[b]
3424 ? NEED_HEAD : NEED_NOTHING);
3425 if (PREV_INSN (next_tail) == basic_block_end[b])
3426 new_needs |= NEED_TAIL;
3428 new_ready = n_ready;
3429 while (sched_n_insns < n_insns)
3431 q_ptr = NEXT_Q (q_ptr); clock++;
3433 /* Add all pending insns that can be scheduled without stalls to the
3435 for (insn = insn_queue[q_ptr]; insn; insn = NEXT_INSN (insn))
3438 fprintf (file, ";; launching %d before %d with no stalls at T-%d\n",
3439 INSN_UID (insn), INSN_UID (last), clock);
3440 ready[new_ready++] = insn;
3443 insn_queue[q_ptr] = 0;
3445 /* If there are no ready insns, stall until one is ready and add all
3446 of the pending insns at that point to the ready list. */
3449 register int stalls;
3451 for (stalls = 1; stalls < INSN_QUEUE_SIZE; stalls++)
3452 if (insn = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)])
3454 for (; insn; insn = NEXT_INSN (insn))
3457 fprintf (file, ";; launching %d before %d with %d stalls at T-%d\n",
3458 INSN_UID (insn), INSN_UID (last), stalls, clock);
3459 ready[new_ready++] = insn;
3462 insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = 0;
3466 q_ptr = NEXT_Q_AFTER (q_ptr, stalls); clock += stalls;
3469 /* There should be some instructions waiting to fire. */
3475 fprintf (file, ";; ready list at T-%d:", clock);
3476 for (i = 0; i < new_ready; i++)
3477 fprintf (file, " %d (%x)",
3478 INSN_UID (ready[i]), INSN_PRIORITY (ready[i]));
3481 /* Sort the ready list and choose the best insn to schedule. Select
3482 which insn should issue in this cycle and queue those that are
3483 blocked by function unit hazards.
3485 N_READY holds the number of items that were scheduled the last time,
3486 minus the one instruction scheduled on the last loop iteration; it
3487 is not modified for any other reason in this loop. */
3489 SCHED_SORT (ready, new_ready, n_ready);
3490 if (MAX_BLOCKAGE > 1)
3492 new_ready = schedule_select (ready, new_ready, clock, file);
3496 fprintf (file, "\n");
3497 /* We must set n_ready here, to ensure that sorting always
3498 occurs when we come back to the SCHED_SORT line above. */
3503 n_ready = new_ready;
3504 last_scheduled_insn = insn = ready[0];
3506 /* The first insn scheduled becomes the new tail. */
3512 fprintf (file, ", now");
3513 for (i = 0; i < n_ready; i++)
3514 fprintf (file, " %d", INSN_UID (ready[i]));
3515 fprintf (file, "\n");
3518 if (DONE_PRIORITY_P (insn))
3521 if (reload_completed == 0)
3523 /* Process this insn, and each insn linked to this one which must
3524 be immediately output after this insn. */
3527 /* First we kill registers set by this insn, and then we
3528 make registers used by this insn live. This is the opposite
3529 order used above because we are traversing the instructions
3532 /* Strictly speaking, we should scan REG_UNUSED notes and make
3533 every register mentioned there live, however, we will just
3534 kill them again immediately below, so there doesn't seem to
3535 be any reason why we bother to do this. */
3537 /* See if this is the last notice we must take of a register. */
3538 if (GET_CODE (PATTERN (insn)) == SET
3539 || GET_CODE (PATTERN (insn)) == CLOBBER)
3540 sched_note_set (b, PATTERN (insn), 1);
3541 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
3544 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
3545 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
3546 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
3547 sched_note_set (b, XVECEXP (PATTERN (insn), 0, j), 1);
3550 /* This code keeps life analysis information up to date. */
3551 if (GET_CODE (insn) == CALL_INSN)
3553 register struct sometimes *p;
3555 /* A call kills all call used and global registers, except
3556 for those mentioned in the call pattern which will be
3557 made live again later. */
3558 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3559 if (call_used_regs[i] || global_regs[i])
3561 register int offset = i / REGSET_ELT_BITS;
3562 register REGSET_ELT_TYPE bit
3563 = (REGSET_ELT_TYPE) 1 << (i % REGSET_ELT_BITS);
3565 bb_live_regs[offset] &= ~bit;
3566 bb_dead_regs[offset] |= bit;
3569 /* Regs live at the time of a call instruction must not
3570 go in a register clobbered by calls. Record this for
3571 all regs now live. Note that insns which are born or
3572 die in a call do not cross a call, so this must be done
3573 after the killings (above) and before the births
3575 p = regs_sometimes_live;
3576 for (i = 0; i < sometimes_max; i++, p++)
3577 if (bb_live_regs[p->offset]
3578 & ((REGSET_ELT_TYPE) 1 << p->bit))
3579 p->calls_crossed += 1;
3582 /* Make every register used live, and add REG_DEAD notes for
3583 registers which were not live before we started. */
3584 attach_deaths_insn (insn);
3586 /* Find registers now made live by that instruction. */
3587 for (i = 0; i < regset_size; i++)
3589 REGSET_ELT_TYPE diff = bb_live_regs[i] & ~old_live_regs[i];
3593 old_live_regs[i] |= diff;
3594 for (bit = 0; bit < REGSET_ELT_BITS; bit++)
3595 if (diff & ((REGSET_ELT_TYPE) 1 << bit))
3597 = new_sometimes_live (regs_sometimes_live, i, bit,
3602 /* Count lengths of all regs we are worrying about now,
3603 and handle registers no longer live. */
3605 for (i = 0; i < sometimes_max; i++)
3607 register struct sometimes *p = ®s_sometimes_live[i];
3608 int regno = p->offset*REGSET_ELT_BITS + p->bit;
3610 p->live_length += 1;
3612 if ((bb_live_regs[p->offset]
3613 & ((REGSET_ELT_TYPE) 1 << p->bit)) == 0)
3615 /* This is the end of one of this register's lifetime
3616 segments. Save the lifetime info collected so far,
3617 and clear its bit in the old_live_regs entry. */
3618 sched_reg_live_length[regno] += p->live_length;
3619 sched_reg_n_calls_crossed[regno] += p->calls_crossed;
3620 old_live_regs[p->offset]
3621 &= ~((REGSET_ELT_TYPE) 1 << p->bit);
3623 /* Delete the reg_sometimes_live entry for this reg by
3624 copying the last entry over top of it. */
3625 *p = regs_sometimes_live[--sometimes_max];
3626 /* ...and decrement i so that this newly copied entry
3627 will be processed. */
3633 insn = PREV_INSN (insn);
3635 while (SCHED_GROUP_P (link));
3637 /* Set INSN back to the insn we are scheduling now. */
3641 /* Schedule INSN. Remove it from the ready list. */
3646 NEXT_INSN (insn) = last;
3647 PREV_INSN (last) = insn;
3650 /* Everything that precedes INSN now either becomes "ready", if
3651 it can execute immediately before INSN, or "pending", if
3652 there must be a delay. Give INSN high enough priority that
3653 at least one (maybe more) reg-killing insns can be launched
3654 ahead of all others. Mark INSN as scheduled by changing its
3656 INSN_PRIORITY (insn) = LAUNCH_PRIORITY;
3657 new_ready = schedule_insn (insn, ready, n_ready, clock);
3658 INSN_PRIORITY (insn) = DONE_PRIORITY;
3660 /* Schedule all prior insns that must not be moved. */
3661 if (SCHED_GROUP_P (insn))
3663 /* Disable these insns from being launched. */
3665 while (SCHED_GROUP_P (link))
3667 /* Disable these insns from being launched by anybody. */
3668 link = PREV_INSN (link);
3669 INSN_REF_COUNT (link) = 0;
3672 /* None of these insns can move forward into delay slots. */
3673 while (SCHED_GROUP_P (insn))
3675 insn = PREV_INSN (insn);
3676 new_ready = schedule_insn (insn, ready, new_ready, clock);
3677 INSN_PRIORITY (insn) = DONE_PRIORITY;
3680 NEXT_INSN (insn) = last;
3681 PREV_INSN (last) = insn;
3689 if (reload_completed == 0)
3690 finish_sometimes_live (regs_sometimes_live, sometimes_max);
3692 /* HEAD is now the first insn in the chain of insns that
3693 been scheduled by the loop above.
3694 TAIL is the last of those insns. */
3697 /* NOTE_LIST is the end of a chain of notes previously found
3698 among the insns. Insert them at the beginning of the insns. */
3701 rtx note_head = note_list;
3702 while (PREV_INSN (note_head))
3703 note_head = PREV_INSN (note_head);
3705 PREV_INSN (head) = note_list;
3706 NEXT_INSN (note_list) = head;
3710 /* There should be no REG_DEAD notes leftover at the end.
3711 In practice, this can occur as the result of bugs in flow, combine.c,
3712 and/or sched.c. The values of the REG_DEAD notes remaining are
3713 meaningless, because dead_notes is just used as a free list. */
3715 if (dead_notes != 0)
3719 if (new_needs & NEED_HEAD)
3720 basic_block_head[b] = head;
3721 PREV_INSN (head) = prev_head;
3722 NEXT_INSN (prev_head) = head;
3724 if (new_needs & NEED_TAIL)
3725 basic_block_end[b] = tail;
3726 NEXT_INSN (tail) = next_tail;
3727 PREV_INSN (next_tail) = tail;
3729 /* Restore the line-number notes of each insn. */
3730 if (write_symbols != NO_DEBUG)
3732 rtx line, note, prev, new;
3735 head = basic_block_head[b];
3736 next_tail = NEXT_INSN (basic_block_end[b]);
3738 /* Determine the current line-number. We want to know the current
3739 line number of the first insn of the block here, in case it is
3740 different from the true line number that was saved earlier. If
3741 different, then we need a line number note before the first insn
3742 of this block. If it happens to be the same, then we don't want to
3743 emit another line number note here. */
3744 for (line = head; line; line = PREV_INSN (line))
3745 if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
3748 /* Walk the insns keeping track of the current line-number and inserting
3749 the line-number notes as needed. */
3750 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
3751 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
3753 /* This used to emit line number notes before every non-deleted note.
3754 However, this confuses a debugger, because line notes not separated
3755 by real instructions all end up at the same address. I can find no
3756 use for line number notes before other notes, so none are emitted. */
3757 else if (GET_CODE (insn) != NOTE
3758 && (note = LINE_NOTE (insn)) != 0
3761 || NOTE_LINE_NUMBER (note) != NOTE_LINE_NUMBER (line)
3762 || NOTE_SOURCE_FILE (note) != NOTE_SOURCE_FILE (line)))
3765 prev = PREV_INSN (insn);
3766 if (LINE_NOTE (note))
3768 /* Re-use the original line-number note. */
3769 LINE_NOTE (note) = 0;
3770 PREV_INSN (note) = prev;
3771 NEXT_INSN (prev) = note;
3772 PREV_INSN (insn) = note;
3773 NEXT_INSN (note) = insn;
3778 new = emit_note_after (NOTE_LINE_NUMBER (note), prev);
3779 NOTE_SOURCE_FILE (new) = NOTE_SOURCE_FILE (note);
3783 fprintf (file, ";; added %d line-number notes\n", notes);
3788 fprintf (file, ";; total time = %d\n;; new basic block head = %d\n;; new basic block end = %d\n\n",
3789 clock, INSN_UID (basic_block_head[b]), INSN_UID (basic_block_end[b]));
3792 /* Yow! We're done! */
3793 free_pending_lists ();
3798 /* Subroutine of split_hard_reg_notes. Searches X for any reference to
3799 REGNO, returning the rtx of the reference found if any. Otherwise,
3803 regno_use_in (regno, x)
3811 if (GET_CODE (x) == REG && REGNO (x) == regno)
3814 fmt = GET_RTX_FORMAT (GET_CODE (x));
3815 for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
3819 if (tem = regno_use_in (regno, XEXP (x, i)))
3822 else if (fmt[i] == 'E')
3823 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3824 if (tem = regno_use_in (regno , XVECEXP (x, i, j)))
3831 /* Subroutine of update_flow_info. Determines whether any new REG_NOTEs are
3832 needed for the hard register mentioned in the note. This can happen
3833 if the reference to the hard register in the original insn was split into
3834 several smaller hard register references in the split insns. */
3837 split_hard_reg_notes (note, first, last, orig_insn)
3838 rtx note, first, last, orig_insn;
3840 rtx reg, temp, link;
3841 int n_regs, i, new_reg;
3844 /* Assume that this is a REG_DEAD note. */
3845 if (REG_NOTE_KIND (note) != REG_DEAD)
3848 reg = XEXP (note, 0);
3850 n_regs = HARD_REGNO_NREGS (REGNO (reg), GET_MODE (reg));
3852 for (i = 0; i < n_regs; i++)
3854 new_reg = REGNO (reg) + i;
3856 /* Check for references to new_reg in the split insns. */
3857 for (insn = last; ; insn = PREV_INSN (insn))
3859 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
3860 && (temp = regno_use_in (new_reg, PATTERN (insn))))
3862 /* Create a new reg dead note here. */
3863 link = rtx_alloc (EXPR_LIST);
3864 PUT_REG_NOTE_KIND (link, REG_DEAD);
3865 XEXP (link, 0) = temp;
3866 XEXP (link, 1) = REG_NOTES (insn);
3867 REG_NOTES (insn) = link;
3869 /* If killed multiple registers here, then add in the excess. */
3870 i += HARD_REGNO_NREGS (REGNO (temp), GET_MODE (temp)) - 1;
3874 /* It isn't mentioned anywhere, so no new reg note is needed for
3882 /* Subroutine of update_flow_info. Determines whether a SET or CLOBBER in an
3883 insn created by splitting needs a REG_DEAD or REG_UNUSED note added. */
3886 new_insn_dead_notes (pat, insn, last, orig_insn)
3887 rtx pat, insn, last, orig_insn;
3891 /* PAT is either a CLOBBER or a SET here. */
3892 dest = XEXP (pat, 0);
3894 while (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SUBREG
3895 || GET_CODE (dest) == STRICT_LOW_PART
3896 || GET_CODE (dest) == SIGN_EXTRACT)
3897 dest = XEXP (dest, 0);
3899 if (GET_CODE (dest) == REG)
3901 for (tem = last; tem != insn; tem = PREV_INSN (tem))
3903 if (GET_RTX_CLASS (GET_CODE (tem)) == 'i'
3904 && reg_overlap_mentioned_p (dest, PATTERN (tem))
3905 && (set = single_set (tem)))
3907 rtx tem_dest = SET_DEST (set);
3909 while (GET_CODE (tem_dest) == ZERO_EXTRACT
3910 || GET_CODE (tem_dest) == SUBREG
3911 || GET_CODE (tem_dest) == STRICT_LOW_PART
3912 || GET_CODE (tem_dest) == SIGN_EXTRACT)
3913 tem_dest = XEXP (tem_dest, 0);
3915 if (tem_dest != dest)
3917 /* Use the same scheme as combine.c, don't put both REG_DEAD
3918 and REG_UNUSED notes on the same insn. */
3919 if (! find_regno_note (tem, REG_UNUSED, REGNO (dest))
3920 && ! find_regno_note (tem, REG_DEAD, REGNO (dest)))
3922 rtx note = rtx_alloc (EXPR_LIST);
3923 PUT_REG_NOTE_KIND (note, REG_DEAD);
3924 XEXP (note, 0) = dest;
3925 XEXP (note, 1) = REG_NOTES (tem);
3926 REG_NOTES (tem) = note;
3928 /* The reg only dies in one insn, the last one that uses
3932 else if (reg_overlap_mentioned_p (dest, SET_SRC (set)))
3933 /* We found an instruction that both uses the register,
3934 and sets it, so no new REG_NOTE is needed for this set. */
3938 /* If this is a set, it must die somewhere, unless it is the dest of
3939 the original insn, and hence is live after the original insn. Abort
3940 if it isn't supposed to be live after the original insn.
3942 If this is a clobber, then just add a REG_UNUSED note. */
3945 int live_after_orig_insn = 0;
3946 rtx pattern = PATTERN (orig_insn);
3949 if (GET_CODE (pat) == CLOBBER)
3951 rtx note = rtx_alloc (EXPR_LIST);
3952 PUT_REG_NOTE_KIND (note, REG_UNUSED);
3953 XEXP (note, 0) = dest;
3954 XEXP (note, 1) = REG_NOTES (insn);
3955 REG_NOTES (insn) = note;
3959 /* The original insn could have multiple sets, so search the
3960 insn for all sets. */
3961 if (GET_CODE (pattern) == SET)
3963 if (reg_overlap_mentioned_p (dest, SET_DEST (pattern)))
3964 live_after_orig_insn = 1;
3966 else if (GET_CODE (pattern) == PARALLEL)
3968 for (i = 0; i < XVECLEN (pattern, 0); i++)
3969 if (GET_CODE (XVECEXP (pattern, 0, i)) == SET
3970 && reg_overlap_mentioned_p (dest,
3971 SET_DEST (XVECEXP (pattern,
3973 live_after_orig_insn = 1;
3976 if (! live_after_orig_insn)
3982 /* Subroutine of update_flow_info. Update the value of reg_n_sets for all
3983 registers modified by X. INC is -1 if the containing insn is being deleted,
3984 and is 1 if the containing insn is a newly generated insn. */
3987 update_n_sets (x, inc)
3991 rtx dest = SET_DEST (x);
3993 while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
3994 || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
3995 dest = SUBREG_REG (dest);
3997 if (GET_CODE (dest) == REG)
3999 int regno = REGNO (dest);
4001 if (regno < FIRST_PSEUDO_REGISTER)
4004 int endregno = regno + HARD_REGNO_NREGS (regno, GET_MODE (dest));
4006 for (i = regno; i < endregno; i++)
4007 reg_n_sets[i] += inc;
4010 reg_n_sets[regno] += inc;
4014 /* Updates all flow-analysis related quantities (including REG_NOTES) for
4015 the insns from FIRST to LAST inclusive that were created by splitting
4016 ORIG_INSN. NOTES are the original REG_NOTES. */
4019 update_flow_info (notes, first, last, orig_insn)
4026 rtx orig_dest, temp;
4029 /* Get and save the destination set by the original insn. */
4031 orig_dest = single_set (orig_insn);
4033 orig_dest = SET_DEST (orig_dest);
4035 /* Move REG_NOTES from the original insn to where they now belong. */
4037 for (note = notes; note; note = next)
4039 next = XEXP (note, 1);
4040 switch (REG_NOTE_KIND (note))
4044 /* Move these notes from the original insn to the last new insn where
4045 the register is now set. */
4047 for (insn = last; ; insn = PREV_INSN (insn))
4049 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
4050 && reg_mentioned_p (XEXP (note, 0), PATTERN (insn)))
4052 /* If this note refers to a multiple word hard register, it
4053 may have been split into several smaller hard register
4054 references, so handle it specially. */
4055 temp = XEXP (note, 0);
4056 if (REG_NOTE_KIND (note) == REG_DEAD
4057 && GET_CODE (temp) == REG
4058 && REGNO (temp) < FIRST_PSEUDO_REGISTER
4059 && HARD_REGNO_NREGS (REGNO (temp), GET_MODE (temp)) > 1)
4060 split_hard_reg_notes (note, first, last, orig_insn);
4063 XEXP (note, 1) = REG_NOTES (insn);
4064 REG_NOTES (insn) = note;
4067 /* Sometimes need to convert REG_UNUSED notes to REG_DEAD
4069 /* ??? This won't handle multiple word registers correctly,
4070 but should be good enough for now. */
4071 if (REG_NOTE_KIND (note) == REG_UNUSED
4072 && ! dead_or_set_p (insn, XEXP (note, 0)))
4073 PUT_REG_NOTE_KIND (note, REG_DEAD);
4075 /* The reg only dies in one insn, the last one that uses
4079 /* It must die somewhere, fail it we couldn't find where it died.
4081 If this is a REG_UNUSED note, then it must be a temporary
4082 register that was not needed by this instantiation of the
4083 pattern, so we can safely ignore it. */
4086 if (REG_NOTE_KIND (note) != REG_UNUSED)
4095 /* This note applies to the dest of the original insn. Find the
4096 first new insn that now has the same dest, and move the note
4102 for (insn = first; ; insn = NEXT_INSN (insn))
4104 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
4105 && (temp = single_set (insn))
4106 && rtx_equal_p (SET_DEST (temp), orig_dest))
4108 XEXP (note, 1) = REG_NOTES (insn);
4109 REG_NOTES (insn) = note;
4110 /* The reg is only zero before one insn, the first that
4114 /* It must be set somewhere, fail if we couldn't find where it
4123 /* A REG_EQUIV or REG_EQUAL note on an insn with more than one
4124 set is meaningless. Just drop the note. */
4128 case REG_NO_CONFLICT:
4129 /* These notes apply to the dest of the original insn. Find the last
4130 new insn that now has the same dest, and move the note there. */
4135 for (insn = last; ; insn = PREV_INSN (insn))
4137 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
4138 && (temp = single_set (insn))
4139 && rtx_equal_p (SET_DEST (temp), orig_dest))
4141 XEXP (note, 1) = REG_NOTES (insn);
4142 REG_NOTES (insn) = note;
4143 /* Only put this note on one of the new insns. */
4147 /* The original dest must still be set someplace. Abort if we
4148 couldn't find it. */
4155 /* Move a REG_LIBCALL note to the first insn created, and update
4156 the corresponding REG_RETVAL note. */
4157 XEXP (note, 1) = REG_NOTES (first);
4158 REG_NOTES (first) = note;
4160 insn = XEXP (note, 0);
4161 note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
4163 XEXP (note, 0) = first;
4167 /* Move a REG_RETVAL note to the last insn created, and update
4168 the corresponding REG_LIBCALL note. */
4169 XEXP (note, 1) = REG_NOTES (last);
4170 REG_NOTES (last) = note;
4172 insn = XEXP (note, 0);
4173 note = find_reg_note (insn, REG_LIBCALL, NULL_RTX);
4175 XEXP (note, 0) = last;
4179 /* This should be moved to whichever instruction is a JUMP_INSN. */
4181 for (insn = last; ; insn = PREV_INSN (insn))
4183 if (GET_CODE (insn) == JUMP_INSN)
4185 XEXP (note, 1) = REG_NOTES (insn);
4186 REG_NOTES (insn) = note;
4187 /* Only put this note on one of the new insns. */
4190 /* Fail if we couldn't find a JUMP_INSN. */
4197 /* This should be moved to whichever instruction now has the
4198 increment operation. */
4202 /* Should be moved to the new insn(s) which use the label. */
4203 for (insn = first; insn != NEXT_INSN (last); insn = NEXT_INSN (insn))
4204 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
4205 && reg_mentioned_p (XEXP (note, 0), PATTERN (insn)))
4206 REG_NOTES (insn) = gen_rtx (EXPR_LIST, REG_LABEL,
4207 XEXP (note, 0), REG_NOTES (insn));
4212 /* These two notes will never appear until after reorg, so we don't
4213 have to handle them here. */
4219 /* Each new insn created, except the last, has a new set. If the destination
4220 is a register, then this reg is now live across several insns, whereas
4221 previously the dest reg was born and died within the same insn. To
4222 reflect this, we now need a REG_DEAD note on the insn where this
4225 Similarly, the new insns may have clobbers that need REG_UNUSED notes. */
4227 for (insn = first; insn != last; insn = NEXT_INSN (insn))
4232 pat = PATTERN (insn);
4233 if (GET_CODE (pat) == SET || GET_CODE (pat) == CLOBBER)
4234 new_insn_dead_notes (pat, insn, last, orig_insn);
4235 else if (GET_CODE (pat) == PARALLEL)
4237 for (i = 0; i < XVECLEN (pat, 0); i++)
4238 if (GET_CODE (XVECEXP (pat, 0, i)) == SET
4239 || GET_CODE (XVECEXP (pat, 0, i)) == CLOBBER)
4240 new_insn_dead_notes (XVECEXP (pat, 0, i), insn, last, orig_insn);
4244 /* If any insn, except the last, uses the register set by the last insn,
4245 then we need a new REG_DEAD note on that insn. In this case, there
4246 would not have been a REG_DEAD note for this register in the original
4247 insn because it was used and set within one insn.
4249 There is no new REG_DEAD note needed if the last insn uses the register
4250 that it is setting. */
4252 set = single_set (last);
4255 rtx dest = SET_DEST (set);
4257 while (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SUBREG
4258 || GET_CODE (dest) == STRICT_LOW_PART
4259 || GET_CODE (dest) == SIGN_EXTRACT)
4260 dest = XEXP (dest, 0);
4262 if (GET_CODE (dest) == REG
4263 && ! reg_overlap_mentioned_p (dest, SET_SRC (set)))
4265 for (insn = PREV_INSN (last); ; insn = PREV_INSN (insn))
4267 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
4268 && reg_mentioned_p (dest, PATTERN (insn))
4269 && (set = single_set (insn)))
4271 rtx insn_dest = SET_DEST (set);
4273 while (GET_CODE (insn_dest) == ZERO_EXTRACT
4274 || GET_CODE (insn_dest) == SUBREG
4275 || GET_CODE (insn_dest) == STRICT_LOW_PART
4276 || GET_CODE (insn_dest) == SIGN_EXTRACT)
4277 insn_dest = XEXP (insn_dest, 0);
4279 if (insn_dest != dest)
4281 note = rtx_alloc (EXPR_LIST);
4282 PUT_REG_NOTE_KIND (note, REG_DEAD);
4283 XEXP (note, 0) = dest;
4284 XEXP (note, 1) = REG_NOTES (insn);
4285 REG_NOTES (insn) = note;
4286 /* The reg only dies in one insn, the last one
4297 /* If the original dest is modifying a multiple register target, and the
4298 original instruction was split such that the original dest is now set
4299 by two or more SUBREG sets, then the split insns no longer kill the
4300 destination of the original insn.
4302 In this case, if there exists an instruction in the same basic block,
4303 before the split insn, which uses the original dest, and this use is
4304 killed by the original insn, then we must remove the REG_DEAD note on
4305 this insn, because it is now superfluous.
4307 This does not apply when a hard register gets split, because the code
4308 knows how to handle overlapping hard registers properly. */
4309 if (orig_dest && GET_CODE (orig_dest) == REG)
4311 int found_orig_dest = 0;
4312 int found_split_dest = 0;
4314 for (insn = first; ; insn = NEXT_INSN (insn))
4316 set = single_set (insn);
4319 if (GET_CODE (SET_DEST (set)) == REG
4320 && REGNO (SET_DEST (set)) == REGNO (orig_dest))
4322 found_orig_dest = 1;
4325 else if (GET_CODE (SET_DEST (set)) == SUBREG
4326 && SUBREG_REG (SET_DEST (set)) == orig_dest)
4328 found_split_dest = 1;
4337 if (found_split_dest)
4339 /* Search backwards from FIRST, looking for the first insn that uses
4340 the original dest. Stop if we pass a CODE_LABEL or a JUMP_INSN.
4341 If we find an insn, and it has a REG_DEAD note, then delete the
4344 for (insn = first; insn; insn = PREV_INSN (insn))
4346 if (GET_CODE (insn) == CODE_LABEL
4347 || GET_CODE (insn) == JUMP_INSN)
4349 else if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
4350 && reg_mentioned_p (orig_dest, insn))
4352 note = find_regno_note (insn, REG_DEAD, REGNO (orig_dest));
4354 remove_note (insn, note);
4358 else if (! found_orig_dest)
4360 /* This should never happen. */
4365 /* Update reg_n_sets. This is necessary to prevent local alloc from
4366 converting REG_EQUAL notes to REG_EQUIV when splitting has modified
4367 a reg from set once to set multiple times. */
4370 rtx x = PATTERN (orig_insn);
4371 RTX_CODE code = GET_CODE (x);
4373 if (code == SET || code == CLOBBER)
4374 update_n_sets (x, -1);
4375 else if (code == PARALLEL)
4378 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
4380 code = GET_CODE (XVECEXP (x, 0, i));
4381 if (code == SET || code == CLOBBER)
4382 update_n_sets (XVECEXP (x, 0, i), -1);
4386 for (insn = first; ; insn = NEXT_INSN (insn))
4389 code = GET_CODE (x);
4391 if (code == SET || code == CLOBBER)
4392 update_n_sets (x, 1);
4393 else if (code == PARALLEL)
4396 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
4398 code = GET_CODE (XVECEXP (x, 0, i));
4399 if (code == SET || code == CLOBBER)
4400 update_n_sets (XVECEXP (x, 0, i), 1);
4410 /* The one entry point in this file. DUMP_FILE is the dump file for
4414 schedule_insns (dump_file)
4417 int max_uid = MAX_INSNS_PER_SPLIT * (get_max_uid () + 1);
4421 /* Taking care of this degenerate case makes the rest of
4422 this code simpler. */
4423 if (n_basic_blocks == 0)
4426 /* Create an insn here so that we can hang dependencies off of it later. */
4427 sched_before_next_call
4428 = gen_rtx (INSN, VOIDmode, 0, NULL_RTX, NULL_RTX,
4429 NULL_RTX, 0, NULL_RTX, 0);
4431 /* Initialize the unused_*_lists. We can't use the ones left over from
4432 the previous function, because gcc has freed that memory. We can use
4433 the ones left over from the first sched pass in the second pass however,
4434 so only clear them on the first sched pass. The first pass is before
4435 reload if flag_schedule_insns is set, otherwise it is afterwards. */
4437 if (reload_completed == 0 || ! flag_schedule_insns)
4439 unused_insn_list = 0;
4440 unused_expr_list = 0;
4443 /* We create no insns here, only reorder them, so we
4444 remember how far we can cut back the stack on exit. */
4446 /* Allocate data for this pass. See comments, above,
4447 for what these vectors do. */
4448 insn_luid = (int *) alloca (max_uid * sizeof (int));
4449 insn_priority = (int *) alloca (max_uid * sizeof (int));
4450 insn_tick = (int *) alloca (max_uid * sizeof (int));
4451 insn_costs = (short *) alloca (max_uid * sizeof (short));
4452 insn_units = (short *) alloca (max_uid * sizeof (short));
4453 insn_blockage = (unsigned int *) alloca (max_uid * sizeof (unsigned int));
4454 insn_ref_count = (int *) alloca (max_uid * sizeof (int));
4456 if (reload_completed == 0)
4458 sched_reg_n_deaths = (short *) alloca (max_regno * sizeof (short));
4459 sched_reg_n_calls_crossed = (int *) alloca (max_regno * sizeof (int));
4460 sched_reg_live_length = (int *) alloca (max_regno * sizeof (int));
4461 bb_dead_regs = (regset) alloca (regset_bytes);
4462 bb_live_regs = (regset) alloca (regset_bytes);
4463 bzero (sched_reg_n_calls_crossed, max_regno * sizeof (int));
4464 bzero (sched_reg_live_length, max_regno * sizeof (int));
4465 bcopy (reg_n_deaths, sched_reg_n_deaths, max_regno * sizeof (short));
4466 init_alias_analysis ();
4470 sched_reg_n_deaths = 0;
4471 sched_reg_n_calls_crossed = 0;
4472 sched_reg_live_length = 0;
4475 if (! flag_schedule_insns)
4476 init_alias_analysis ();
4479 if (write_symbols != NO_DEBUG)
4483 line_note = (rtx *) alloca (max_uid * sizeof (rtx));
4484 bzero (line_note, max_uid * sizeof (rtx));
4485 line_note_head = (rtx *) alloca (n_basic_blocks * sizeof (rtx));
4486 bzero (line_note_head, n_basic_blocks * sizeof (rtx));
4488 /* Determine the line-number at the start of each basic block.
4489 This must be computed and saved now, because after a basic block's
4490 predecessor has been scheduled, it is impossible to accurately
4491 determine the correct line number for the first insn of the block. */
4493 for (b = 0; b < n_basic_blocks; b++)
4494 for (line = basic_block_head[b]; line; line = PREV_INSN (line))
4495 if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
4497 line_note_head[b] = line;
4502 bzero (insn_luid, max_uid * sizeof (int));
4503 bzero (insn_priority, max_uid * sizeof (int));
4504 bzero (insn_tick, max_uid * sizeof (int));
4505 bzero (insn_costs, max_uid * sizeof (short));
4506 bzero (insn_units, max_uid * sizeof (short));
4507 bzero (insn_blockage, max_uid * sizeof (unsigned int));
4508 bzero (insn_ref_count, max_uid * sizeof (int));
4510 /* Schedule each basic block, block by block. */
4512 /* ??? Add a NOTE after the last insn of the last basic block. It is not
4513 known why this is done. */
4515 insn = basic_block_end[n_basic_blocks-1];
4516 if (NEXT_INSN (insn) == 0
4517 || (GET_CODE (insn) != NOTE
4518 && GET_CODE (insn) != CODE_LABEL
4519 /* Don't emit a NOTE if it would end up between an unconditional
4520 jump and a BARRIER. */
4521 && ! (GET_CODE (insn) == JUMP_INSN
4522 && GET_CODE (NEXT_INSN (insn)) == BARRIER)))
4523 emit_note_after (NOTE_INSN_DELETED, basic_block_end[n_basic_blocks-1]);
4525 for (b = 0; b < n_basic_blocks; b++)
4532 for (insn = basic_block_head[b]; ; insn = next)
4537 /* Can't use `next_real_insn' because that
4538 might go across CODE_LABELS and short-out basic blocks. */
4539 next = NEXT_INSN (insn);
4540 if (GET_CODE (insn) != INSN)
4542 if (insn == basic_block_end[b])
4548 /* Don't split no-op move insns. These should silently disappear
4549 later in final. Splitting such insns would break the code
4550 that handles REG_NO_CONFLICT blocks. */
4551 set = single_set (insn);
4552 if (set && rtx_equal_p (SET_SRC (set), SET_DEST (set)))
4554 if (insn == basic_block_end[b])
4557 /* Nops get in the way while scheduling, so delete them now if
4558 register allocation has already been done. It is too risky
4559 to try to do this before register allocation, and there are
4560 unlikely to be very many nops then anyways. */
4561 if (reload_completed)
4563 PUT_CODE (insn, NOTE);
4564 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
4565 NOTE_SOURCE_FILE (insn) = 0;
4571 /* Split insns here to get max fine-grain parallelism. */
4572 prev = PREV_INSN (insn);
4573 if (reload_completed == 0)
4575 rtx last, first = PREV_INSN (insn);
4576 rtx notes = REG_NOTES (insn);
4578 last = try_split (PATTERN (insn), insn, 1);
4581 /* try_split returns the NOTE that INSN became. */
4582 first = NEXT_INSN (first);
4583 update_flow_info (notes, first, last, insn);
4585 PUT_CODE (insn, NOTE);
4586 NOTE_SOURCE_FILE (insn) = 0;
4587 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
4588 if (insn == basic_block_head[b])
4589 basic_block_head[b] = first;
4590 if (insn == basic_block_end[b])
4592 basic_block_end[b] = last;
4598 if (insn == basic_block_end[b])
4602 schedule_block (b, dump_file);
4609 /* Reposition the prologue and epilogue notes in case we moved the
4610 prologue/epilogue insns. */
4611 if (reload_completed)
4612 reposition_prologue_and_epilogue_notes (get_insns ());
4614 if (write_symbols != NO_DEBUG)
4617 rtx insn = get_insns ();
4618 int active_insn = 0;
4621 /* Walk the insns deleting redundant line-number notes. Many of these
4622 are already present. The remainder tend to occur at basic
4623 block boundaries. */
4624 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
4625 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
4627 /* If there are no active insns following, INSN is redundant. */
4628 if (active_insn == 0)
4631 NOTE_SOURCE_FILE (insn) = 0;
4632 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
4634 /* If the line number is unchanged, LINE is redundant. */
4636 && NOTE_LINE_NUMBER (line) == NOTE_LINE_NUMBER (insn)
4637 && NOTE_SOURCE_FILE (line) == NOTE_SOURCE_FILE (insn))
4640 NOTE_SOURCE_FILE (line) = 0;
4641 NOTE_LINE_NUMBER (line) = NOTE_INSN_DELETED;
4648 else if (! ((GET_CODE (insn) == NOTE
4649 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED)
4650 || (GET_CODE (insn) == INSN
4651 && (GET_CODE (PATTERN (insn)) == USE
4652 || GET_CODE (PATTERN (insn)) == CLOBBER))))
4655 if (dump_file && notes)
4656 fprintf (dump_file, ";; deleted %d line-number notes\n", notes);
4659 if (reload_completed == 0)
4662 for (regno = 0; regno < max_regno; regno++)
4663 if (sched_reg_live_length[regno])
4667 if (reg_live_length[regno] > sched_reg_live_length[regno])
4669 ";; register %d life shortened from %d to %d\n",
4670 regno, reg_live_length[regno],
4671 sched_reg_live_length[regno]);
4672 /* Negative values are special; don't overwrite the current
4673 reg_live_length value if it is negative. */
4674 else if (reg_live_length[regno] < sched_reg_live_length[regno]
4675 && reg_live_length[regno] >= 0)
4677 ";; register %d life extended from %d to %d\n",
4678 regno, reg_live_length[regno],
4679 sched_reg_live_length[regno]);
4681 if (reg_n_calls_crossed[regno]
4682 && ! sched_reg_n_calls_crossed[regno])
4684 ";; register %d no longer crosses calls\n", regno);
4685 else if (! reg_n_calls_crossed[regno]
4686 && sched_reg_n_calls_crossed[regno])
4688 ";; register %d now crosses calls\n", regno);
4690 /* Negative values are special; don't overwrite the current
4691 reg_live_length value if it is negative. */
4692 if (reg_live_length[regno] >= 0)
4693 reg_live_length[regno] = sched_reg_live_length[regno];
4694 reg_n_calls_crossed[regno] = sched_reg_n_calls_crossed[regno];
4698 #endif /* INSN_SCHEDULING */