1 /* Instruction scheduling pass.
2 Copyright (C) 1992 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 == stack_pointer_rtx)
570 y = x; ysize = xsize;
571 x = t; xsize = tsize;
574 if (x == frame_pointer_rtx || x == stack_pointer_rtx)
581 if (GET_CODE (y) == PLUS
582 && canon_rtx (XEXP (y, 0)) == x
583 && (y1 = canon_rtx (XEXP (y, 1)))
584 && GET_CODE (y1) == CONST_INT)
587 return (xsize == 0 || ysize == 0
588 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
591 if (GET_CODE (y) == PLUS
592 && (y1 = canon_rtx (XEXP (y, 0)))
599 if (GET_CODE (x) == PLUS)
601 /* The fact that X is canonicalized means that this
602 PLUS rtx is canonicalized. */
603 rtx x0 = XEXP (x, 0);
604 rtx x1 = XEXP (x, 1);
606 if (GET_CODE (y) == PLUS)
608 /* The fact that Y is canonicalized means that this
609 PLUS rtx is canonicalized. */
610 rtx y0 = XEXP (y, 0);
611 rtx y1 = XEXP (y, 1);
613 if (rtx_equal_for_memref_p (x1, y1))
614 return memrefs_conflict_p (xsize, x0, ysize, y0, c);
615 if (rtx_equal_for_memref_p (x0, y0))
616 return memrefs_conflict_p (xsize, x1, ysize, y1, c);
617 if (GET_CODE (x1) == CONST_INT)
618 if (GET_CODE (y1) == CONST_INT)
619 return memrefs_conflict_p (xsize, x0, ysize, y0,
620 c - INTVAL (x1) + INTVAL (y1));
622 return memrefs_conflict_p (xsize, x0, ysize, y, c - INTVAL (x1));
623 else if (GET_CODE (y1) == CONST_INT)
624 return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1));
626 /* Handle case where we cannot understand iteration operators,
627 but we notice that the base addresses are distinct objects. */
628 x = find_symbolic_term (x);
631 y = find_symbolic_term (y);
634 return rtx_equal_for_memref_p (x, y);
636 else if (GET_CODE (x1) == CONST_INT)
637 return memrefs_conflict_p (xsize, x0, ysize, y, c - INTVAL (x1));
639 else if (GET_CODE (y) == PLUS)
641 /* The fact that Y is canonicalized means that this
642 PLUS rtx is canonicalized. */
643 rtx y0 = XEXP (y, 0);
644 rtx y1 = XEXP (y, 1);
646 if (GET_CODE (y1) == CONST_INT)
647 return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1));
652 if (GET_CODE (x) == GET_CODE (y))
653 switch (GET_CODE (x))
657 /* Handle cases where we expect the second operands to be the
658 same, and check only whether the first operand would conflict
661 rtx x1 = canon_rtx (XEXP (x, 1));
662 rtx y1 = canon_rtx (XEXP (y, 1));
663 if (! rtx_equal_for_memref_p (x1, y1))
665 x0 = canon_rtx (XEXP (x, 0));
666 y0 = canon_rtx (XEXP (y, 0));
667 if (rtx_equal_for_memref_p (x0, y0))
668 return (xsize == 0 || ysize == 0
669 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
671 /* Can't properly adjust our sizes. */
672 if (GET_CODE (x1) != CONST_INT)
674 xsize /= INTVAL (x1);
675 ysize /= INTVAL (x1);
677 return memrefs_conflict_p (xsize, x0, ysize, y0, c);
683 if (GET_CODE (x) == CONST_INT && GET_CODE (y) == CONST_INT)
685 c += (INTVAL (y) - INTVAL (x));
686 return (xsize == 0 || ysize == 0
687 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
690 if (GET_CODE (x) == CONST)
692 if (GET_CODE (y) == CONST)
693 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
694 ysize, canon_rtx (XEXP (y, 0)), c);
696 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
699 if (GET_CODE (y) == CONST)
700 return memrefs_conflict_p (xsize, x, ysize,
701 canon_rtx (XEXP (y, 0)), c);
704 return (rtx_equal_for_memref_p (x, y)
705 && (xsize == 0 || ysize == 0
706 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0)));
713 /* Functions to compute memory dependencies.
715 Since we process the insns in execution order, we can build tables
716 to keep track of what registers are fixed (and not aliased), what registers
717 are varying in known ways, and what registers are varying in unknown
720 If both memory references are volatile, then there must always be a
721 dependence between the two references, since their order can not be
722 changed. A volatile and non-volatile reference can be interchanged
725 A MEM_IN_STRUCT reference at a non-QImode varying address can never
726 conflict with a non-MEM_IN_STRUCT reference at a fixed address. We must
727 allow QImode aliasing because the ANSI C standard allows character
728 pointers to alias anything. We are assuming that characters are
729 always QImode here. */
731 /* Read dependence: X is read after read in MEM takes place. There can
732 only be a dependence here if both reads are volatile. */
735 read_dependence (mem, x)
739 return MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem);
742 /* True dependence: X is read after store in MEM takes place. */
745 true_dependence (mem, x)
749 /* If X is an unchanging read, then it can't possibly conflict with any
750 non-unchanging store. It may conflict with an unchanging write though,
751 because there may be a single store to this address to initialize it.
752 Just fall through to the code below to resolve the case where we have
753 both an unchanging read and an unchanging write. This won't handle all
754 cases optimally, but the possible performance loss should be
756 if (RTX_UNCHANGING_P (x) && ! RTX_UNCHANGING_P (mem))
759 return ((MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
760 || (memrefs_conflict_p (SIZE_FOR_MODE (mem), XEXP (mem, 0),
761 SIZE_FOR_MODE (x), XEXP (x, 0), 0)
762 && ! (MEM_IN_STRUCT_P (mem) && rtx_addr_varies_p (mem)
763 && GET_MODE (mem) != QImode
764 && ! MEM_IN_STRUCT_P (x) && ! rtx_addr_varies_p (x))
765 && ! (MEM_IN_STRUCT_P (x) && rtx_addr_varies_p (x)
766 && GET_MODE (x) != QImode
767 && ! MEM_IN_STRUCT_P (mem) && ! rtx_addr_varies_p (mem))));
770 /* Anti dependence: X is written after read in MEM takes place. */
773 anti_dependence (mem, x)
777 /* If MEM is an unchanging read, then it can't possibly conflict with
778 the store to X, because there is at most one store to MEM, and it must
779 have occured somewhere before MEM. */
780 if (RTX_UNCHANGING_P (mem))
783 return ((MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
784 || (memrefs_conflict_p (SIZE_FOR_MODE (mem), XEXP (mem, 0),
785 SIZE_FOR_MODE (x), XEXP (x, 0), 0)
786 && ! (MEM_IN_STRUCT_P (mem) && rtx_addr_varies_p (mem)
787 && GET_MODE (mem) != QImode
788 && ! MEM_IN_STRUCT_P (x) && ! rtx_addr_varies_p (x))
789 && ! (MEM_IN_STRUCT_P (x) && rtx_addr_varies_p (x)
790 && GET_MODE (x) != QImode
791 && ! MEM_IN_STRUCT_P (mem) && ! rtx_addr_varies_p (mem))));
794 /* Output dependence: X is written after store in MEM takes place. */
797 output_dependence (mem, x)
801 return ((MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
802 || (memrefs_conflict_p (SIZE_FOR_MODE (mem), XEXP (mem, 0),
803 SIZE_FOR_MODE (x), XEXP (x, 0), 0)
804 && ! (MEM_IN_STRUCT_P (mem) && rtx_addr_varies_p (mem)
805 && GET_MODE (mem) != QImode
806 && ! MEM_IN_STRUCT_P (x) && ! rtx_addr_varies_p (x))
807 && ! (MEM_IN_STRUCT_P (x) && rtx_addr_varies_p (x)
808 && GET_MODE (x) != QImode
809 && ! MEM_IN_STRUCT_P (mem) && ! rtx_addr_varies_p (mem))));
812 /* Helper functions for instruction scheduling. */
814 /* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the
815 LOG_LINKS of INSN, if not already there. DEP_TYPE indicates the type
816 of dependence that this link represents. */
819 add_dependence (insn, elem, dep_type)
822 enum reg_note dep_type;
826 /* Don't depend an insn on itself. */
830 /* If elem is part of a sequence that must be scheduled together, then
831 make the dependence point to the last insn of the sequence.
832 When HAVE_cc0, it is possible for NOTEs to exist between users and
833 setters of the condition codes, so we must skip past notes here.
834 Otherwise, NOTEs are impossible here. */
836 next = NEXT_INSN (elem);
839 while (next && GET_CODE (next) == NOTE)
840 next = NEXT_INSN (next);
843 if (next && SCHED_GROUP_P (next))
845 /* Notes will never intervene here though, so don't bother checking
847 /* We must reject CODE_LABELs, so that we don't get confused by one
848 that has LABEL_PRESERVE_P set, which is represented by the same
849 bit in the rtl as SCHED_GROUP_P. A CODE_LABEL can never be
851 while (NEXT_INSN (next) && SCHED_GROUP_P (NEXT_INSN (next))
852 && GET_CODE (NEXT_INSN (next)) != CODE_LABEL)
853 next = NEXT_INSN (next);
855 /* Again, don't depend an insn on itself. */
859 /* Make the dependence to NEXT, the last insn of the group, instead
860 of the original ELEM. */
864 /* Check that we don't already have this dependence. */
865 for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
866 if (XEXP (link, 0) == elem)
868 /* If this is a more restrictive type of dependence than the existing
869 one, then change the existing dependence to this type. */
870 if ((int) dep_type < (int) REG_NOTE_KIND (link))
871 PUT_REG_NOTE_KIND (link, dep_type);
874 /* Might want to check one level of transitivity to save conses. */
876 link = rtx_alloc (INSN_LIST);
877 /* Insn dependency, not data dependency. */
878 PUT_REG_NOTE_KIND (link, dep_type);
879 XEXP (link, 0) = elem;
880 XEXP (link, 1) = LOG_LINKS (insn);
881 LOG_LINKS (insn) = link;
884 /* Remove ELEM wrapped in an INSN_LIST from the LOG_LINKS
885 of INSN. Abort if not found. */
887 remove_dependence (insn, elem)
894 for (prev = 0, link = LOG_LINKS (insn); link;
895 prev = link, link = XEXP (link, 1))
897 if (XEXP (link, 0) == elem)
900 XEXP (prev, 1) = XEXP (link, 1);
902 LOG_LINKS (insn) = XEXP (link, 1);
912 #ifndef INSN_SCHEDULING
913 void schedule_insns () {}
919 /* Computation of memory dependencies. */
921 /* The *_insns and *_mems are paired lists. Each pending memory operation
922 will have a pointer to the MEM rtx on one list and a pointer to the
923 containing insn on the other list in the same place in the list. */
925 /* We can't use add_dependence like the old code did, because a single insn
926 may have multiple memory accesses, and hence needs to be on the list
927 once for each memory access. Add_dependence won't let you add an insn
928 to a list more than once. */
930 /* An INSN_LIST containing all insns with pending read operations. */
931 static rtx pending_read_insns;
933 /* An EXPR_LIST containing all MEM rtx's which are pending reads. */
934 static rtx pending_read_mems;
936 /* An INSN_LIST containing all insns with pending write operations. */
937 static rtx pending_write_insns;
939 /* An EXPR_LIST containing all MEM rtx's which are pending writes. */
940 static rtx pending_write_mems;
942 /* Indicates the combined length of the two pending lists. We must prevent
943 these lists from ever growing too large since the number of dependencies
944 produced is at least O(N*N), and execution time is at least O(4*N*N), as
945 a function of the length of these pending lists. */
947 static int pending_lists_length;
949 /* An INSN_LIST containing all INSN_LISTs allocated but currently unused. */
951 static rtx unused_insn_list;
953 /* An EXPR_LIST containing all EXPR_LISTs allocated but currently unused. */
955 static rtx unused_expr_list;
957 /* The last insn upon which all memory references must depend.
958 This is an insn which flushed the pending lists, creating a dependency
959 between it and all previously pending memory references. This creates
960 a barrier (or a checkpoint) which no memory reference is allowed to cross.
962 This includes all non constant CALL_INSNs. When we do interprocedural
963 alias analysis, this restriction can be relaxed.
964 This may also be an INSN that writes memory if the pending lists grow
967 static rtx last_pending_memory_flush;
969 /* The last function call we have seen. All hard regs, and, of course,
970 the last function call, must depend on this. */
972 static rtx last_function_call;
974 /* The LOG_LINKS field of this is a list of insns which use a pseudo register
975 that does not already cross a call. We create dependencies between each
976 of those insn and the next call insn, to ensure that they won't cross a call
977 after scheduling is done. */
979 static rtx sched_before_next_call;
981 /* Pointer to the last instruction scheduled. Used by rank_for_schedule,
982 so that insns independent of the last scheduled insn will be preferred
983 over dependent instructions. */
985 static rtx last_scheduled_insn;
987 /* Process an insn's memory dependencies. There are four kinds of
990 (0) read dependence: read follows read
991 (1) true dependence: read follows write
992 (2) anti dependence: write follows read
993 (3) output dependence: write follows write
995 We are careful to build only dependencies which actually exist, and
996 use transitivity to avoid building too many links. */
998 /* Return the INSN_LIST containing INSN in LIST, or NULL
999 if LIST does not contain INSN. */
1002 find_insn_list (insn, list)
1008 if (XEXP (list, 0) == insn)
1010 list = XEXP (list, 1);
1015 /* Compute the function units used by INSN. This caches the value
1016 returned by function_units_used. A function unit is encoded as the
1017 unit number if the value is non-negative and the compliment of a
1018 mask if the value is negative. A function unit index is the
1019 non-negative encoding. */
1025 register int unit = INSN_UNIT (insn);
1029 recog_memoized (insn);
1031 /* A USE insn, or something else we don't need to understand.
1032 We can't pass these directly to function_units_used because it will
1033 trigger a fatal error for unrecognizable insns. */
1034 if (INSN_CODE (insn) < 0)
1038 unit = function_units_used (insn);
1039 /* Increment non-negative values so we can cache zero. */
1040 if (unit >= 0) unit++;
1042 /* We only cache 16 bits of the result, so if the value is out of
1043 range, don't cache it. */
1044 if (FUNCTION_UNITS_SIZE < HOST_BITS_PER_SHORT
1046 || (~unit & ((1 << (HOST_BITS_PER_SHORT - 1)) - 1)) == 0)
1047 INSN_UNIT (insn) = unit;
1049 return (unit > 0 ? unit - 1 : unit);
1052 /* Compute the blockage range for executing INSN on UNIT. This caches
1053 the value returned by the blockage_range_function for the unit.
1054 These values are encoded in an int where the upper half gives the
1055 minimum value and the lower half gives the maximum value. */
1057 __inline static unsigned int
1058 blockage_range (unit, insn)
1062 unsigned int blockage = INSN_BLOCKAGE (insn);
1065 if (UNIT_BLOCKED (blockage) != unit + 1)
1067 range = function_units[unit].blockage_range_function (insn);
1068 /* We only cache the blockage range for one unit and then only if
1070 if (HOST_BITS_PER_INT >= UNIT_BITS + 2 * BLOCKAGE_BITS)
1071 INSN_BLOCKAGE (insn) = ENCODE_BLOCKAGE (unit + 1, range);
1074 range = BLOCKAGE_RANGE (blockage);
1079 /* A vector indexed by function unit instance giving the last insn to use
1080 the unit. The value of the function unit instance index for unit U
1081 instance I is (U + I * FUNCTION_UNITS_SIZE). */
1082 static rtx unit_last_insn[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY];
1084 /* A vector indexed by function unit instance giving the minimum time when
1085 the unit will unblock based on the maximum blockage cost. */
1086 static int unit_tick[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY];
1088 /* A vector indexed by function unit number giving the number of insns
1089 that remain to use the unit. */
1090 static int unit_n_insns[FUNCTION_UNITS_SIZE];
1092 /* Reset the function unit state to the null state. */
1099 bzero (unit_last_insn, sizeof (unit_last_insn));
1100 bzero (unit_tick, sizeof (unit_tick));
1101 bzero (unit_n_insns, sizeof (unit_n_insns));
1104 /* Record an insn as one that will use the units encoded by UNIT. */
1106 __inline static void
1113 unit_n_insns[unit]++;
1115 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
1116 if ((unit & 1) != 0)
1120 /* Return the actual hazard cost of executing INSN on the unit UNIT,
1121 instance INSTANCE at time CLOCK if the previous actual hazard cost
1125 actual_hazard_this_instance (unit, instance, insn, clock, cost)
1126 int unit, instance, clock, cost;
1130 int tick = unit_tick[instance];
1132 if (tick - clock > cost)
1134 /* The scheduler is operating in reverse, so INSN is the executing
1135 insn and the unit's last insn is the candidate insn. We want a
1136 more exact measure of the blockage if we execute INSN at CLOCK
1137 given when we committed the execution of the unit's last insn.
1139 The blockage value is given by either the unit's max blockage
1140 constant, blockage range function, or blockage function. Use
1141 the most exact form for the given unit. */
1143 if (function_units[unit].blockage_range_function)
1145 if (function_units[unit].blockage_function)
1146 tick += (function_units[unit].blockage_function
1147 (insn, unit_last_insn[instance])
1148 - function_units[unit].max_blockage);
1150 tick += ((int) MAX_BLOCKAGE_COST (blockage_range (unit, insn))
1151 - function_units[unit].max_blockage);
1153 if (tick - clock > cost)
1154 cost = tick - clock;
1159 /* Record INSN as having begun execution on the units encoded by UNIT at
1162 __inline static void
1163 schedule_unit (unit, insn, clock)
1171 int instance = unit;
1172 #if MAX_MULTIPLICITY > 1
1173 /* Find the first free instance of the function unit and use that
1174 one. We assume that one is free. */
1175 for (i = function_units[unit].multiplicity - 1; i > 0; i--)
1177 if (! actual_hazard_this_instance (unit, instance, insn, clock, 0))
1179 instance += FUNCTION_UNITS_SIZE;
1182 unit_last_insn[instance] = insn;
1183 unit_tick[instance] = (clock + function_units[unit].max_blockage);
1186 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
1187 if ((unit & 1) != 0)
1188 schedule_unit (i, insn, clock);
1191 /* Return the actual hazard cost of executing INSN on the units encoded by
1192 UNIT at time CLOCK if the previous actual hazard cost was COST. */
1195 actual_hazard (unit, insn, clock, cost)
1196 int unit, clock, cost;
1203 /* Find the instance of the function unit with the minimum hazard. */
1204 int instance = unit;
1205 int best = instance;
1206 int best_cost = actual_hazard_this_instance (unit, instance, insn,
1210 #if MAX_MULTIPLICITY > 1
1211 if (best_cost > cost)
1213 for (i = function_units[unit].multiplicity - 1; i > 0; i--)
1215 instance += FUNCTION_UNITS_SIZE;
1216 this_cost = actual_hazard_this_instance (unit, instance, insn,
1218 if (this_cost < best_cost)
1221 best_cost = this_cost;
1222 if (this_cost <= cost)
1228 cost = MAX (cost, best_cost);
1231 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
1232 if ((unit & 1) != 0)
1233 cost = actual_hazard (i, insn, clock, cost);
1238 /* Return the potential hazard cost of executing an instruction on the
1239 units encoded by UNIT if the previous potential hazard cost was COST.
1240 An insn with a large blockage time is chosen in preference to one
1241 with a smaller time; an insn that uses a unit that is more likely
1242 to be used is chosen in preference to one with a unit that is less
1243 used. We are trying to minimize a subsequent actual hazard. */
1246 potential_hazard (unit, insn, cost)
1251 unsigned int minb, maxb;
1255 minb = maxb = function_units[unit].max_blockage;
1258 if (function_units[unit].blockage_range_function)
1260 maxb = minb = blockage_range (unit, insn);
1261 maxb = MAX_BLOCKAGE_COST (maxb);
1262 minb = MIN_BLOCKAGE_COST (minb);
1267 /* Make the number of instructions left dominate. Make the
1268 minimum delay dominate the maximum delay. If all these
1269 are the same, use the unit number to add an arbitrary
1270 ordering. Other terms can be added. */
1271 ncost = minb * 0x40 + maxb;
1272 ncost *= (unit_n_insns[unit] - 1) * 0x1000 + unit;
1279 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
1280 if ((unit & 1) != 0)
1281 cost = potential_hazard (i, insn, cost);
1286 /* Compute cost of executing INSN given the dependence LINK on the insn USED.
1287 This is the number of virtual cycles taken between instruction issue and
1288 instruction results. */
1291 insn_cost (insn, link, used)
1292 rtx insn, link, used;
1294 register int cost = INSN_COST (insn);
1298 recog_memoized (insn);
1300 /* A USE insn, or something else we don't need to understand.
1301 We can't pass these directly to result_ready_cost because it will
1302 trigger a fatal error for unrecognizable insns. */
1303 if (INSN_CODE (insn) < 0)
1305 INSN_COST (insn) = 1;
1310 cost = result_ready_cost (insn);
1315 INSN_COST (insn) = cost;
1319 /* A USE insn should never require the value used to be computed. This
1320 allows the computation of a function's result and parameter values to
1321 overlap the return and call. */
1322 recog_memoized (used);
1323 if (INSN_CODE (used) < 0)
1324 LINK_COST_FREE (link) = 1;
1326 /* If some dependencies vary the cost, compute the adjustment. Most
1327 commonly, the adjustment is complete: either the cost is ignored
1328 (in the case of an output- or anti-dependence), or the cost is
1329 unchanged. These values are cached in the link as LINK_COST_FREE
1330 and LINK_COST_ZERO. */
1332 if (LINK_COST_FREE (link))
1335 else if (! LINK_COST_ZERO (link))
1339 ADJUST_COST (used, link, insn, ncost);
1341 LINK_COST_FREE (link) = ncost = 1;
1343 LINK_COST_ZERO (link) = 1;
1350 /* Compute the priority number for INSN. */
1356 if (insn && GET_RTX_CLASS (GET_CODE (insn)) == 'i')
1360 int this_priority = INSN_PRIORITY (insn);
1363 if (this_priority > 0)
1364 return this_priority;
1368 /* Nonzero if these insns must be scheduled together. */
1369 if (SCHED_GROUP_P (insn))
1372 while (SCHED_GROUP_P (prev))
1374 prev = PREV_INSN (prev);
1375 INSN_REF_COUNT (prev) += 1;
1379 for (prev = LOG_LINKS (insn); prev; prev = XEXP (prev, 1))
1381 rtx x = XEXP (prev, 0);
1383 /* A dependence pointing to a note is always obsolete, because
1384 sched_analyze_insn will have created any necessary new dependences
1385 which replace it. Notes can be created when instructions are
1386 deleted by insn splitting, or by register allocation. */
1387 if (GET_CODE (x) == NOTE)
1389 remove_dependence (insn, x);
1393 /* Clear the link cost adjustment bits. */
1394 LINK_COST_FREE (prev) = 0;
1396 LINK_COST_ZERO (prev) = 0;
1399 /* This priority calculation was chosen because it results in the
1400 least instruction movement, and does not hurt the performance
1401 of the resulting code compared to the old algorithm.
1402 This makes the sched algorithm more stable, which results
1403 in better code, because there is less register pressure,
1404 cross jumping is more likely to work, and debugging is easier.
1406 When all instructions have a latency of 1, there is no need to
1407 move any instructions. Subtracting one here ensures that in such
1408 cases all instructions will end up with a priority of one, and
1409 hence no scheduling will be done.
1411 The original code did not subtract the one, and added the
1412 insn_cost of the current instruction to its priority (e.g.
1413 move the insn_cost call down to the end). */
1415 if (REG_NOTE_KIND (prev) == 0)
1416 /* Data dependence. */
1417 prev_priority = priority (x) + insn_cost (x, prev, insn) - 1;
1419 /* Anti or output dependence. Don't add the latency of this
1420 insn's result, because it isn't being used. */
1421 prev_priority = priority (x);
1423 if (prev_priority > max_priority)
1424 max_priority = prev_priority;
1425 INSN_REF_COUNT (x) += 1;
1428 prepare_unit (insn_unit (insn));
1429 INSN_PRIORITY (insn) = max_priority;
1430 return INSN_PRIORITY (insn);
1435 /* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
1436 them to the unused_*_list variables, so that they can be reused. */
1439 free_pending_lists ()
1441 register rtx link, prev_link;
1443 if (pending_read_insns)
1445 prev_link = pending_read_insns;
1446 link = XEXP (prev_link, 1);
1451 link = XEXP (link, 1);
1454 XEXP (prev_link, 1) = unused_insn_list;
1455 unused_insn_list = pending_read_insns;
1456 pending_read_insns = 0;
1459 if (pending_write_insns)
1461 prev_link = pending_write_insns;
1462 link = XEXP (prev_link, 1);
1467 link = XEXP (link, 1);
1470 XEXP (prev_link, 1) = unused_insn_list;
1471 unused_insn_list = pending_write_insns;
1472 pending_write_insns = 0;
1475 if (pending_read_mems)
1477 prev_link = pending_read_mems;
1478 link = XEXP (prev_link, 1);
1483 link = XEXP (link, 1);
1486 XEXP (prev_link, 1) = unused_expr_list;
1487 unused_expr_list = pending_read_mems;
1488 pending_read_mems = 0;
1491 if (pending_write_mems)
1493 prev_link = pending_write_mems;
1494 link = XEXP (prev_link, 1);
1499 link = XEXP (link, 1);
1502 XEXP (prev_link, 1) = unused_expr_list;
1503 unused_expr_list = pending_write_mems;
1504 pending_write_mems = 0;
1508 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
1509 The MEM is a memory reference contained within INSN, which we are saving
1510 so that we can do memory aliasing on it. */
1513 add_insn_mem_dependence (insn_list, mem_list, insn, mem)
1514 rtx *insn_list, *mem_list, insn, mem;
1518 if (unused_insn_list)
1520 link = unused_insn_list;
1521 unused_insn_list = XEXP (link, 1);
1524 link = rtx_alloc (INSN_LIST);
1525 XEXP (link, 0) = insn;
1526 XEXP (link, 1) = *insn_list;
1529 if (unused_expr_list)
1531 link = unused_expr_list;
1532 unused_expr_list = XEXP (link, 1);
1535 link = rtx_alloc (EXPR_LIST);
1536 XEXP (link, 0) = mem;
1537 XEXP (link, 1) = *mem_list;
1540 pending_lists_length++;
1543 /* Make a dependency between every memory reference on the pending lists
1544 and INSN, thus flushing the pending lists. */
1547 flush_pending_lists (insn)
1552 while (pending_read_insns)
1554 add_dependence (insn, XEXP (pending_read_insns, 0), REG_DEP_ANTI);
1556 link = pending_read_insns;
1557 pending_read_insns = XEXP (pending_read_insns, 1);
1558 XEXP (link, 1) = unused_insn_list;
1559 unused_insn_list = link;
1561 link = pending_read_mems;
1562 pending_read_mems = XEXP (pending_read_mems, 1);
1563 XEXP (link, 1) = unused_expr_list;
1564 unused_expr_list = link;
1566 while (pending_write_insns)
1568 add_dependence (insn, XEXP (pending_write_insns, 0), REG_DEP_ANTI);
1570 link = pending_write_insns;
1571 pending_write_insns = XEXP (pending_write_insns, 1);
1572 XEXP (link, 1) = unused_insn_list;
1573 unused_insn_list = link;
1575 link = pending_write_mems;
1576 pending_write_mems = XEXP (pending_write_mems, 1);
1577 XEXP (link, 1) = unused_expr_list;
1578 unused_expr_list = link;
1580 pending_lists_length = 0;
1582 if (last_pending_memory_flush)
1583 add_dependence (insn, last_pending_memory_flush, REG_DEP_ANTI);
1585 last_pending_memory_flush = insn;
1588 /* Analyze a single SET or CLOBBER rtx, X, creating all dependencies generated
1589 by the write to the destination of X, and reads of everything mentioned. */
1592 sched_analyze_1 (x, insn)
1597 register rtx dest = SET_DEST (x);
1602 while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
1603 || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
1605 if (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
1607 /* The second and third arguments are values read by this insn. */
1608 sched_analyze_2 (XEXP (dest, 1), insn);
1609 sched_analyze_2 (XEXP (dest, 2), insn);
1611 dest = SUBREG_REG (dest);
1614 if (GET_CODE (dest) == REG)
1616 register int offset, bit, i;
1618 regno = REGNO (dest);
1620 /* A hard reg in a wide mode may really be multiple registers.
1621 If so, mark all of them just like the first. */
1622 if (regno < FIRST_PSEUDO_REGISTER)
1624 i = HARD_REGNO_NREGS (regno, GET_MODE (dest));
1629 for (u = reg_last_uses[regno+i]; u; u = XEXP (u, 1))
1630 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
1631 reg_last_uses[regno + i] = 0;
1632 if (reg_last_sets[regno + i])
1633 add_dependence (insn, reg_last_sets[regno + i],
1635 reg_last_sets[regno + i] = insn;
1636 if ((call_used_regs[i] || global_regs[i])
1637 && last_function_call)
1638 /* Function calls clobber all call_used regs. */
1639 add_dependence (insn, last_function_call, REG_DEP_ANTI);
1646 for (u = reg_last_uses[regno]; u; u = XEXP (u, 1))
1647 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
1648 reg_last_uses[regno] = 0;
1649 if (reg_last_sets[regno])
1650 add_dependence (insn, reg_last_sets[regno], REG_DEP_OUTPUT);
1651 reg_last_sets[regno] = insn;
1653 /* Pseudos that are REG_EQUIV to something may be replaced
1654 by that during reloading. We need only add dependencies for
1655 the address in the REG_EQUIV note. */
1656 if (! reload_completed
1657 && reg_known_equiv_p[regno]
1658 && GET_CODE (reg_known_value[regno]) == MEM)
1659 sched_analyze_2 (XEXP (reg_known_value[regno], 0), insn);
1661 /* Don't let it cross a call after scheduling if it doesn't
1662 already cross one. */
1663 if (reg_n_calls_crossed[regno] == 0 && last_function_call)
1664 add_dependence (insn, last_function_call, REG_DEP_ANTI);
1667 else if (GET_CODE (dest) == MEM)
1669 /* Writing memory. */
1671 if (pending_lists_length > 32)
1673 /* Flush all pending reads and writes to prevent the pending lists
1674 from getting any larger. Insn scheduling runs too slowly when
1675 these lists get long. The number 32 was chosen because it
1676 seems like a reasonable number. When compiling GCC with itself,
1677 this flush occurs 8 times for sparc, and 10 times for m88k using
1679 flush_pending_lists (insn);
1683 rtx pending, pending_mem;
1685 pending = pending_read_insns;
1686 pending_mem = pending_read_mems;
1689 /* If a dependency already exists, don't create a new one. */
1690 if (! find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
1691 if (anti_dependence (XEXP (pending_mem, 0), dest))
1692 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
1694 pending = XEXP (pending, 1);
1695 pending_mem = XEXP (pending_mem, 1);
1698 pending = pending_write_insns;
1699 pending_mem = pending_write_mems;
1702 /* If a dependency already exists, don't create a new one. */
1703 if (! find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
1704 if (output_dependence (XEXP (pending_mem, 0), dest))
1705 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
1707 pending = XEXP (pending, 1);
1708 pending_mem = XEXP (pending_mem, 1);
1711 if (last_pending_memory_flush)
1712 add_dependence (insn, last_pending_memory_flush, REG_DEP_ANTI);
1714 add_insn_mem_dependence (&pending_write_insns, &pending_write_mems,
1717 sched_analyze_2 (XEXP (dest, 0), insn);
1720 /* Analyze reads. */
1721 if (GET_CODE (x) == SET)
1722 sched_analyze_2 (SET_SRC (x), insn);
1725 /* Analyze the uses of memory and registers in rtx X in INSN. */
1728 sched_analyze_2 (x, insn)
1734 register enum rtx_code code;
1740 code = GET_CODE (x);
1749 /* Ignore constants. Note that we must handle CONST_DOUBLE here
1750 because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but
1751 this does not mean that this insn is using cc0. */
1759 /* There may be a note before this insn now, but all notes will
1760 be removed before we actually try to schedule the insns, so
1761 it won't cause a problem later. We must avoid it here though. */
1763 /* User of CC0 depends on immediately preceding insn. */
1764 SCHED_GROUP_P (insn) = 1;
1766 /* Make a copy of all dependencies on the immediately previous insn,
1767 and add to this insn. This is so that all the dependencies will
1768 apply to the group. Remove an explicit dependence on this insn
1769 as SCHED_GROUP_P now represents it. */
1771 prev = PREV_INSN (insn);
1772 while (GET_CODE (prev) == NOTE)
1773 prev = PREV_INSN (prev);
1775 if (find_insn_list (prev, LOG_LINKS (insn)))
1776 remove_dependence (insn, prev);
1778 for (link = LOG_LINKS (prev); link; link = XEXP (link, 1))
1779 add_dependence (insn, XEXP (link, 0), REG_NOTE_KIND (link));
1787 int regno = REGNO (x);
1788 if (regno < FIRST_PSEUDO_REGISTER)
1792 i = HARD_REGNO_NREGS (regno, GET_MODE (x));
1795 reg_last_uses[regno + i]
1796 = gen_rtx (INSN_LIST, VOIDmode,
1797 insn, reg_last_uses[regno + i]);
1798 if (reg_last_sets[regno + i])
1799 add_dependence (insn, reg_last_sets[regno + i], 0);
1800 if ((call_used_regs[regno + i] || global_regs[regno + i])
1801 && last_function_call)
1802 /* Function calls clobber all call_used regs. */
1803 add_dependence (insn, last_function_call, REG_DEP_ANTI);
1808 reg_last_uses[regno]
1809 = gen_rtx (INSN_LIST, VOIDmode, insn, reg_last_uses[regno]);
1810 if (reg_last_sets[regno])
1811 add_dependence (insn, reg_last_sets[regno], 0);
1813 /* Pseudos that are REG_EQUIV to something may be replaced
1814 by that during reloading. We need only add dependencies for
1815 the address in the REG_EQUIV note. */
1816 if (! reload_completed
1817 && reg_known_equiv_p[regno]
1818 && GET_CODE (reg_known_value[regno]) == MEM)
1819 sched_analyze_2 (XEXP (reg_known_value[regno], 0), insn);
1821 /* If the register does not already cross any calls, then add this
1822 insn to the sched_before_next_call list so that it will still
1823 not cross calls after scheduling. */
1824 if (reg_n_calls_crossed[regno] == 0)
1825 add_dependence (sched_before_next_call, insn, REG_DEP_ANTI);
1832 /* Reading memory. */
1834 rtx pending, pending_mem;
1836 pending = pending_read_insns;
1837 pending_mem = pending_read_mems;
1840 /* If a dependency already exists, don't create a new one. */
1841 if (! find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
1842 if (read_dependence (XEXP (pending_mem, 0), x))
1843 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
1845 pending = XEXP (pending, 1);
1846 pending_mem = XEXP (pending_mem, 1);
1849 pending = pending_write_insns;
1850 pending_mem = pending_write_mems;
1853 /* If a dependency already exists, don't create a new one. */
1854 if (! find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
1855 if (true_dependence (XEXP (pending_mem, 0), x))
1856 add_dependence (insn, XEXP (pending, 0), 0);
1858 pending = XEXP (pending, 1);
1859 pending_mem = XEXP (pending_mem, 1);
1861 if (last_pending_memory_flush)
1862 add_dependence (insn, last_pending_memory_flush, REG_DEP_ANTI);
1864 /* Always add these dependencies to pending_reads, since
1865 this insn may be followed by a write. */
1866 add_insn_mem_dependence (&pending_read_insns, &pending_read_mems,
1869 /* Take advantage of tail recursion here. */
1870 sched_analyze_2 (XEXP (x, 0), insn);
1876 case UNSPEC_VOLATILE:
1881 /* Traditional and volatile asm instructions must be considered to use
1882 and clobber all hard registers and all of memory. So must
1883 TRAP_IF and UNSPEC_VOLATILE operations. */
1884 if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
1886 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1888 for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
1889 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
1890 reg_last_uses[i] = 0;
1891 if (reg_last_sets[i])
1892 add_dependence (insn, reg_last_sets[i], 0);
1893 reg_last_sets[i] = insn;
1896 flush_pending_lists (insn);
1899 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
1900 We can not just fall through here since then we would be confused
1901 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
1902 traditional asms unlike their normal usage. */
1904 if (code == ASM_OPERANDS)
1906 for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
1907 sched_analyze_2 (ASM_OPERANDS_INPUT (x, j), insn);
1917 /* These both read and modify the result. We must handle them as writes
1918 to get proper dependencies for following instructions. We must handle
1919 them as reads to get proper dependencies from this to previous
1920 instructions. Thus we need to pass them to both sched_analyze_1
1921 and sched_analyze_2. We must call sched_analyze_2 first in order
1922 to get the proper antecedent for the read. */
1923 sched_analyze_2 (XEXP (x, 0), insn);
1924 sched_analyze_1 (x, insn);
1928 /* Other cases: walk the insn. */
1929 fmt = GET_RTX_FORMAT (code);
1930 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1933 sched_analyze_2 (XEXP (x, i), insn);
1934 else if (fmt[i] == 'E')
1935 for (j = 0; j < XVECLEN (x, i); j++)
1936 sched_analyze_2 (XVECEXP (x, i, j), insn);
1940 /* Analyze an INSN with pattern X to find all dependencies. */
1943 sched_analyze_insn (x, insn)
1946 register RTX_CODE code = GET_CODE (x);
1949 if (code == SET || code == CLOBBER)
1950 sched_analyze_1 (x, insn);
1951 else if (code == PARALLEL)
1954 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
1956 code = GET_CODE (XVECEXP (x, 0, i));
1957 if (code == SET || code == CLOBBER)
1958 sched_analyze_1 (XVECEXP (x, 0, i), insn);
1960 sched_analyze_2 (XVECEXP (x, 0, i), insn);
1964 sched_analyze_2 (x, insn);
1966 /* Handle function calls. */
1967 if (GET_CODE (insn) == CALL_INSN)
1972 /* When scheduling instructions, we make sure calls don't lose their
1973 accompanying USE insns by depending them one on another in order. */
1975 prev_dep_insn = insn;
1976 dep_insn = PREV_INSN (insn);
1977 while (GET_CODE (dep_insn) == INSN
1978 && GET_CODE (PATTERN (dep_insn)) == USE)
1980 SCHED_GROUP_P (prev_dep_insn) = 1;
1982 /* Make a copy of all dependencies on dep_insn, and add to insn.
1983 This is so that all of the dependencies will apply to the
1986 for (link = LOG_LINKS (dep_insn); link; link = XEXP (link, 1))
1987 add_dependence (insn, XEXP (link, 0), REG_NOTE_KIND (link));
1989 prev_dep_insn = dep_insn;
1990 dep_insn = PREV_INSN (dep_insn);
1995 /* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
1996 for every dependency. */
1999 sched_analyze (head, tail)
2003 register int n_insns = 0;
2005 register int luid = 0;
2007 for (insn = head; ; insn = NEXT_INSN (insn))
2009 INSN_LUID (insn) = luid++;
2011 if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
2013 sched_analyze_insn (PATTERN (insn), insn);
2016 else if (GET_CODE (insn) == CALL_INSN)
2022 /* Any instruction using a hard register which may get clobbered
2023 by a call needs to be marked as dependent on this call.
2024 This prevents a use of a hard return reg from being moved
2025 past a void call (i.e. it does not explicitly set the hard
2028 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2029 if (call_used_regs[i] || global_regs[i])
2031 for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
2032 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
2033 reg_last_uses[i] = 0;
2034 if (reg_last_sets[i])
2035 add_dependence (insn, reg_last_sets[i], REG_DEP_ANTI);
2036 reg_last_sets[i] = insn;
2037 /* Insn, being a CALL_INSN, magically depends on
2038 `last_function_call' already. */
2041 /* For each insn which shouldn't cross a call, add a dependence
2042 between that insn and this call insn. */
2043 x = LOG_LINKS (sched_before_next_call);
2046 add_dependence (insn, XEXP (x, 0), REG_DEP_ANTI);
2049 LOG_LINKS (sched_before_next_call) = 0;
2051 sched_analyze_insn (PATTERN (insn), insn);
2053 /* We don't need to flush memory for a function call which does
2054 not involve memory. */
2055 if (! CONST_CALL_P (insn))
2057 /* In the absence of interprocedural alias analysis,
2058 we must flush all pending reads and writes, and
2059 start new dependencies starting from here. */
2060 flush_pending_lists (insn);
2063 /* Depend this function call (actually, the user of this
2064 function call) on all hard register clobberage. */
2065 last_function_call = insn;
2074 /* Called when we see a set of a register. If death is true, then we are
2075 scanning backwards. Mark that register as unborn. If nobody says
2076 otherwise, that is how things will remain. If death is false, then we
2077 are scanning forwards. Mark that register as being born. */
2080 sched_note_set (b, x, death)
2085 register int regno, j;
2086 register rtx reg = SET_DEST (x);
2092 while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == STRICT_LOW_PART
2093 || GET_CODE (reg) == SIGN_EXTRACT || GET_CODE (reg) == ZERO_EXTRACT)
2095 /* Must treat modification of just one hardware register of a multi-reg
2096 value or just a byte field of a register exactly the same way that
2097 mark_set_1 in flow.c does, i.e. anything except a paradoxical subreg
2098 does not kill the entire register. */
2099 if (GET_CODE (reg) != SUBREG
2100 || REG_SIZE (SUBREG_REG (reg)) > REG_SIZE (reg))
2103 reg = SUBREG_REG (reg);
2106 if (GET_CODE (reg) != REG)
2109 /* Global registers are always live, so the code below does not apply
2112 regno = REGNO (reg);
2113 if (regno >= FIRST_PSEUDO_REGISTER || ! global_regs[regno])
2115 register int offset = regno / REGSET_ELT_BITS;
2116 register REGSET_ELT_TYPE bit
2117 = (REGSET_ELT_TYPE) 1 << (regno % REGSET_ELT_BITS);
2121 /* If we only set part of the register, then this set does not
2126 /* Try killing this register. */
2127 if (regno < FIRST_PSEUDO_REGISTER)
2129 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
2132 offset = (regno + j) / REGSET_ELT_BITS;
2133 bit = (REGSET_ELT_TYPE) 1 << ((regno + j) % REGSET_ELT_BITS);
2135 bb_live_regs[offset] &= ~bit;
2136 bb_dead_regs[offset] |= bit;
2141 bb_live_regs[offset] &= ~bit;
2142 bb_dead_regs[offset] |= bit;
2147 /* Make the register live again. */
2148 if (regno < FIRST_PSEUDO_REGISTER)
2150 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
2153 offset = (regno + j) / REGSET_ELT_BITS;
2154 bit = (REGSET_ELT_TYPE) 1 << ((regno + j) % REGSET_ELT_BITS);
2156 bb_live_regs[offset] |= bit;
2157 bb_dead_regs[offset] &= ~bit;
2162 bb_live_regs[offset] |= bit;
2163 bb_dead_regs[offset] &= ~bit;
2169 /* Macros and functions for keeping the priority queue sorted, and
2170 dealing with queueing and unqueueing of instructions. */
2172 #define SCHED_SORT(READY, NEW_READY, OLD_READY) \
2173 do { if ((NEW_READY) - (OLD_READY) == 1) \
2174 swap_sort (READY, NEW_READY); \
2175 else if ((NEW_READY) - (OLD_READY) > 1) \
2176 qsort (READY, NEW_READY, sizeof (rtx), rank_for_schedule); } \
2179 /* Returns a positive value if y is preferred; returns a negative value if
2180 x is preferred. Should never return 0, since that will make the sort
2184 rank_for_schedule (x, y)
2190 int tmp_class, tmp2_class;
2193 /* Choose the instruction with the highest priority, if different. */
2194 if (value = INSN_PRIORITY (tmp) - INSN_PRIORITY (tmp2))
2197 if (last_scheduled_insn)
2199 /* Classify the instructions into three classes:
2200 1) Data dependent on last schedule insn.
2201 2) Anti/Output dependent on last scheduled insn.
2202 3) Independent of last scheduled insn, or has latency of one.
2203 Choose the insn from the highest numbered class if different. */
2204 link = find_insn_list (tmp, LOG_LINKS (last_scheduled_insn));
2205 if (link == 0 || insn_cost (tmp, link, last_scheduled_insn) == 1)
2207 else if (REG_NOTE_KIND (link) == 0) /* Data dependence. */
2212 link = find_insn_list (tmp2, LOG_LINKS (last_scheduled_insn));
2213 if (link == 0 || insn_cost (tmp2, link, last_scheduled_insn) == 1)
2215 else if (REG_NOTE_KIND (link) == 0) /* Data dependence. */
2220 if (value = tmp_class - tmp2_class)
2224 /* If insns are equally good, sort by INSN_LUID (original insn order),
2225 so that we make the sort stable. This minimizes instruction movement,
2226 thus minimizing sched's effect on debugging and cross-jumping. */
2227 return INSN_LUID (tmp) - INSN_LUID (tmp2);
2230 /* Resort the array A in which only element at index N may be out of order. */
2232 __inline static void
2240 while (i >= 0 && rank_for_schedule (a+i, &insn) >= 0)
2248 static int max_priority;
2250 /* Add INSN to the insn queue so that it fires at least N_CYCLES
2251 before the currently executing insn. */
2253 __inline static void
2254 queue_insn (insn, n_cycles)
2258 int next_q = NEXT_Q_AFTER (q_ptr, n_cycles);
2259 NEXT_INSN (insn) = insn_queue[next_q];
2260 insn_queue[next_q] = insn;
2264 /* Return nonzero if PAT is the pattern of an insn which makes a
2268 birthing_insn_p (pat)
2273 if (reload_completed == 1)
2276 if (GET_CODE (pat) == SET
2277 && GET_CODE (SET_DEST (pat)) == REG)
2279 rtx dest = SET_DEST (pat);
2280 int i = REGNO (dest);
2281 int offset = i / REGSET_ELT_BITS;
2282 REGSET_ELT_TYPE bit = (REGSET_ELT_TYPE) 1 << (i % REGSET_ELT_BITS);
2284 /* It would be more accurate to use refers_to_regno_p or
2285 reg_mentioned_p to determine when the dest is not live before this
2288 if (bb_live_regs[offset] & bit)
2289 return (reg_n_sets[i] == 1);
2293 if (GET_CODE (pat) == PARALLEL)
2295 for (j = 0; j < XVECLEN (pat, 0); j++)
2296 if (birthing_insn_p (XVECEXP (pat, 0, j)))
2302 /* PREV is an insn that is ready to execute. Adjust its priority if that
2303 will help shorten register lifetimes. */
2305 __inline static void
2306 adjust_priority (prev)
2309 /* Trying to shorten register lives after reload has completed
2310 is useless and wrong. It gives inaccurate schedules. */
2311 if (reload_completed == 0)
2316 /* ??? This code has no effect, because REG_DEAD notes are removed
2317 before we ever get here. */
2318 for (note = REG_NOTES (prev); note; note = XEXP (note, 1))
2319 if (REG_NOTE_KIND (note) == REG_DEAD)
2322 /* Defer scheduling insns which kill registers, since that
2323 shortens register lives. Prefer scheduling insns which
2324 make registers live for the same reason. */
2328 INSN_PRIORITY (prev) >>= 3;
2331 INSN_PRIORITY (prev) >>= 2;
2335 INSN_PRIORITY (prev) >>= 1;
2338 if (birthing_insn_p (PATTERN (prev)))
2340 int max = max_priority;
2342 if (max > INSN_PRIORITY (prev))
2343 INSN_PRIORITY (prev) = max;
2350 /* INSN is the "currently executing insn". Launch each insn which was
2351 waiting on INSN (in the backwards dataflow sense). READY is a
2352 vector of insns which are ready to fire. N_READY is the number of
2353 elements in READY. CLOCK is the current virtual cycle. */
2356 schedule_insn (insn, ready, n_ready, clock)
2363 int new_ready = n_ready;
2365 if (MAX_BLOCKAGE > 1)
2366 schedule_unit (insn_unit (insn), insn, clock);
2368 if (LOG_LINKS (insn) == 0)
2371 /* This is used by the function adjust_priority above. */
2373 max_priority = MAX (INSN_PRIORITY (ready[0]), INSN_PRIORITY (insn));
2375 max_priority = INSN_PRIORITY (insn);
2377 for (link = LOG_LINKS (insn); link != 0; link = XEXP (link, 1))
2379 rtx prev = XEXP (link, 0);
2380 int cost = insn_cost (prev, link, insn);
2382 if ((INSN_REF_COUNT (prev) -= 1) != 0)
2384 /* We satisfied one requirement to fire PREV. Record the earliest
2385 time when PREV can fire. No need to do this if the cost is 1,
2386 because PREV can fire no sooner than the next cycle. */
2388 INSN_TICK (prev) = MAX (INSN_TICK (prev), clock + cost);
2392 /* We satisfied the last requirement to fire PREV. Ensure that all
2393 timing requirements are satisfied. */
2394 if (INSN_TICK (prev) - clock > cost)
2395 cost = INSN_TICK (prev) - clock;
2397 /* Adjust the priority of PREV and either put it on the ready
2398 list or queue it. */
2399 adjust_priority (prev);
2401 ready[new_ready++] = prev;
2403 queue_insn (prev, cost);
2410 /* Given N_READY insns in the ready list READY at time CLOCK, queue
2411 those that are blocked due to function unit hazards and rearrange
2412 the remaining ones to minimize subsequent function unit hazards. */
2415 schedule_select (ready, n_ready, clock, file)
2420 int pri = INSN_PRIORITY (ready[0]);
2421 int i, j, k, q, cost, best_cost, best_insn = 0, new_ready = n_ready;
2424 /* Work down the ready list in groups of instructions with the same
2425 priority value. Queue insns in the group that are blocked and
2426 select among those that remain for the one with the largest
2427 potential hazard. */
2428 for (i = 0; i < n_ready; i = j)
2431 for (j = i + 1; j < n_ready; j++)
2432 if ((pri = INSN_PRIORITY (ready[j])) != opri)
2435 /* Queue insns in the group that are blocked. */
2436 for (k = i, q = 0; k < j; k++)
2439 if ((cost = actual_hazard (insn_unit (insn), insn, clock, 0)) != 0)
2443 queue_insn (insn, cost);
2445 fprintf (file, "\n;; blocking insn %d for %d cycles",
2446 INSN_UID (insn), cost);
2451 /* Check the next group if all insns were queued. */
2455 /* If more than one remains, select the first one with the largest
2456 potential hazard. */
2457 else if (j - i - q > 1)
2460 for (k = i; k < j; k++)
2462 if ((insn = ready[k]) == 0)
2464 if ((cost = potential_hazard (insn_unit (insn), insn, 0))
2472 /* We have found a suitable insn to schedule. */
2476 /* Move the best insn to be front of the ready list. */
2481 fprintf (file, ", now");
2482 for (i = 0; i < n_ready; i++)
2484 fprintf (file, " %d", INSN_UID (ready[i]));
2485 fprintf (file, "\n;; insn %d has a greater potential hazard",
2486 INSN_UID (ready[best_insn]));
2488 for (i = best_insn; i > 0; i--)
2491 ready[i-1] = ready[i];
2496 /* Compact the ready list. */
2497 if (new_ready < n_ready)
2498 for (i = j = 0; i < n_ready; i++)
2500 ready[j++] = ready[i];
2505 /* Add a REG_DEAD note for REG to INSN, reusing a REG_DEAD note from the
2509 create_reg_dead_note (reg, insn)
2514 /* The number of registers killed after scheduling must be the same as the
2515 number of registers killed before scheduling. The number of REG_DEAD
2516 notes may not be conserved, i.e. two SImode hard register REG_DEAD notes
2517 might become one DImode hard register REG_DEAD note, but the number of
2518 registers killed will be conserved.
2520 We carefully remove REG_DEAD notes from the dead_notes list, so that
2521 there will be none left at the end. If we run out early, then there
2522 is a bug somewhere in flow, combine and/or sched. */
2524 if (dead_notes == 0)
2529 link = rtx_alloc (EXPR_LIST);
2530 PUT_REG_NOTE_KIND (link, REG_DEAD);
2535 /* Number of regs killed by REG. */
2536 int regs_killed = (REGNO (reg) >= FIRST_PSEUDO_REGISTER ? 1
2537 : HARD_REGNO_NREGS (REGNO (reg), GET_MODE (reg)));
2538 /* Number of regs killed by REG_DEAD notes taken off the list. */
2542 reg_note_regs = (REGNO (XEXP (link, 0)) >= FIRST_PSEUDO_REGISTER ? 1
2543 : HARD_REGNO_NREGS (REGNO (XEXP (link, 0)),
2544 GET_MODE (XEXP (link, 0))));
2545 while (reg_note_regs < regs_killed)
2547 link = XEXP (link, 1);
2548 reg_note_regs += (REGNO (XEXP (link, 0)) >= FIRST_PSEUDO_REGISTER ? 1
2549 : HARD_REGNO_NREGS (REGNO (XEXP (link, 0)),
2550 GET_MODE (XEXP (link, 0))));
2552 dead_notes = XEXP (link, 1);
2554 /* If we took too many regs kills off, put the extra ones back. */
2555 while (reg_note_regs > regs_killed)
2557 rtx temp_reg, temp_link;
2559 temp_reg = gen_rtx (REG, word_mode, 0);
2560 temp_link = rtx_alloc (EXPR_LIST);
2561 PUT_REG_NOTE_KIND (temp_link, REG_DEAD);
2562 XEXP (temp_link, 0) = temp_reg;
2563 XEXP (temp_link, 1) = dead_notes;
2564 dead_notes = temp_link;
2569 XEXP (link, 0) = reg;
2570 XEXP (link, 1) = REG_NOTES (insn);
2571 REG_NOTES (insn) = link;
2574 /* Subroutine on attach_deaths_insn--handles the recursive search
2575 through INSN. If SET_P is true, then x is being modified by the insn. */
2578 attach_deaths (x, insn, set_p)
2585 register enum rtx_code code;
2591 code = GET_CODE (x);
2603 /* Get rid of the easy cases first. */
2608 /* If the register dies in this insn, queue that note, and mark
2609 this register as needing to die. */
2610 /* This code is very similar to mark_used_1 (if set_p is false)
2611 and mark_set_1 (if set_p is true) in flow.c. */
2613 register int regno = REGNO (x);
2614 register int offset = regno / REGSET_ELT_BITS;
2615 register REGSET_ELT_TYPE bit
2616 = (REGSET_ELT_TYPE) 1 << (regno % REGSET_ELT_BITS);
2617 REGSET_ELT_TYPE all_needed = (old_live_regs[offset] & bit);
2618 REGSET_ELT_TYPE some_needed = (old_live_regs[offset] & bit);
2623 if (regno < FIRST_PSEUDO_REGISTER)
2627 n = HARD_REGNO_NREGS (regno, GET_MODE (x));
2630 some_needed |= (old_live_regs[(regno + n) / REGSET_ELT_BITS]
2631 & ((REGSET_ELT_TYPE) 1
2632 << ((regno + n) % REGSET_ELT_BITS)));
2633 all_needed &= (old_live_regs[(regno + n) / REGSET_ELT_BITS]
2634 & ((REGSET_ELT_TYPE) 1
2635 << ((regno + n) % REGSET_ELT_BITS)));
2639 /* If it wasn't live before we started, then add a REG_DEAD note.
2640 We must check the previous lifetime info not the current info,
2641 because we may have to execute this code several times, e.g.
2642 once for a clobber (which doesn't add a note) and later
2643 for a use (which does add a note).
2645 Always make the register live. We must do this even if it was
2646 live before, because this may be an insn which sets and uses
2647 the same register, in which case the register has already been
2648 killed, so we must make it live again.
2650 Global registers are always live, and should never have a REG_DEAD
2651 note added for them, so none of the code below applies to them. */
2653 if (regno >= FIRST_PSEUDO_REGISTER || ! global_regs[regno])
2655 /* Never add REG_DEAD notes for the FRAME_POINTER_REGNUM or the
2656 STACK_POINTER_REGNUM, since these are always considered to be
2657 live. Similarly for ARG_POINTER_REGNUM if it is fixed. */
2658 if (regno != FRAME_POINTER_REGNUM
2659 #if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
2660 && ! (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
2662 && regno != STACK_POINTER_REGNUM)
2664 if (! all_needed && ! dead_or_set_p (insn, x))
2666 /* If none of the words in X is needed, make a REG_DEAD
2667 note. Otherwise, we must make partial REG_DEAD
2670 create_reg_dead_note (x, insn);
2675 /* Don't make a REG_DEAD note for a part of a
2676 register that is set in the insn. */
2677 for (i = HARD_REGNO_NREGS (regno, GET_MODE (x)) - 1;
2679 if ((old_live_regs[(regno + i) / REGSET_ELT_BITS]
2680 & ((REGSET_ELT_TYPE) 1
2681 << ((regno +i) % REGSET_ELT_BITS))) == 0
2682 && ! dead_or_set_regno_p (insn, regno + i))
2683 create_reg_dead_note (gen_rtx (REG, word_mode,
2690 if (regno < FIRST_PSEUDO_REGISTER)
2692 int j = HARD_REGNO_NREGS (regno, GET_MODE (x));
2695 offset = (regno + j) / REGSET_ELT_BITS;
2697 = (REGSET_ELT_TYPE) 1 << ((regno + j) % REGSET_ELT_BITS);
2699 bb_dead_regs[offset] &= ~bit;
2700 bb_live_regs[offset] |= bit;
2705 bb_dead_regs[offset] &= ~bit;
2706 bb_live_regs[offset] |= bit;
2713 /* Handle tail-recursive case. */
2714 attach_deaths (XEXP (x, 0), insn, 0);
2718 case STRICT_LOW_PART:
2719 /* These two cases preserve the value of SET_P, so handle them
2721 attach_deaths (XEXP (x, 0), insn, set_p);
2726 /* This case preserves the value of SET_P for the first operand, but
2727 clears it for the other two. */
2728 attach_deaths (XEXP (x, 0), insn, set_p);
2729 attach_deaths (XEXP (x, 1), insn, 0);
2730 attach_deaths (XEXP (x, 2), insn, 0);
2734 /* Other cases: walk the insn. */
2735 fmt = GET_RTX_FORMAT (code);
2736 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2739 attach_deaths (XEXP (x, i), insn, 0);
2740 else if (fmt[i] == 'E')
2741 for (j = 0; j < XVECLEN (x, i); j++)
2742 attach_deaths (XVECEXP (x, i, j), insn, 0);
2747 /* After INSN has executed, add register death notes for each register
2748 that is dead after INSN. */
2751 attach_deaths_insn (insn)
2754 rtx x = PATTERN (insn);
2755 register RTX_CODE code = GET_CODE (x);
2759 attach_deaths (SET_SRC (x), insn, 0);
2761 /* A register might die here even if it is the destination, e.g.
2762 it is the target of a volatile read and is otherwise unused.
2763 Hence we must always call attach_deaths for the SET_DEST. */
2764 attach_deaths (SET_DEST (x), insn, 1);
2766 else if (code == PARALLEL)
2769 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
2771 code = GET_CODE (XVECEXP (x, 0, i));
2774 attach_deaths (SET_SRC (XVECEXP (x, 0, i)), insn, 0);
2776 attach_deaths (SET_DEST (XVECEXP (x, 0, i)), insn, 1);
2778 /* Flow does not add REG_DEAD notes to registers that die in
2779 clobbers, so we can't either. */
2780 else if (code != CLOBBER)
2781 attach_deaths (XVECEXP (x, 0, i), insn, 0);
2784 /* Flow does not add REG_DEAD notes to registers that die in
2785 clobbers, so we can't either. */
2786 else if (code != CLOBBER)
2787 attach_deaths (x, insn, 0);
2790 /* Delete notes beginning with INSN and maybe put them in the chain
2791 of notes ended by NOTE_LIST.
2792 Returns the insn following the notes. */
2795 unlink_notes (insn, tail)
2798 rtx prev = PREV_INSN (insn);
2800 while (insn != tail && GET_CODE (insn) == NOTE)
2802 rtx next = NEXT_INSN (insn);
2803 /* Delete the note from its current position. */
2805 NEXT_INSN (prev) = next;
2807 PREV_INSN (next) = prev;
2809 if (write_symbols != NO_DEBUG && NOTE_LINE_NUMBER (insn) > 0)
2810 /* Record line-number notes so they can be reused. */
2811 LINE_NOTE (insn) = insn;
2814 /* Insert the note at the end of the notes list. */
2815 PREV_INSN (insn) = note_list;
2817 NEXT_INSN (note_list) = insn;
2826 /* Data structure for keeping track of register information
2827 during that register's life. */
2831 short offset; short bit;
2832 short live_length; short calls_crossed;
2835 /* Constructor for `sometimes' data structure. */
2838 new_sometimes_live (regs_sometimes_live, offset, bit, sometimes_max)
2839 struct sometimes *regs_sometimes_live;
2843 register struct sometimes *p;
2844 register int regno = offset * REGSET_ELT_BITS + bit;
2847 /* There should never be a register greater than max_regno here. If there
2848 is, it means that a define_split has created a new pseudo reg. This
2849 is not allowed, since there will not be flow info available for any
2850 new register, so catch the error here. */
2851 if (regno >= max_regno)
2854 p = ®s_sometimes_live[sometimes_max];
2858 p->calls_crossed = 0;
2860 return sometimes_max;
2863 /* Count lengths of all regs we are currently tracking,
2864 and find new registers no longer live. */
2867 finish_sometimes_live (regs_sometimes_live, sometimes_max)
2868 struct sometimes *regs_sometimes_live;
2873 for (i = 0; i < sometimes_max; i++)
2875 register struct sometimes *p = ®s_sometimes_live[i];
2878 regno = p->offset * REGSET_ELT_BITS + p->bit;
2880 sched_reg_live_length[regno] += p->live_length;
2881 sched_reg_n_calls_crossed[regno] += p->calls_crossed;
2885 /* Use modified list scheduling to rearrange insns in basic block
2886 B. FILE, if nonzero, is where we dump interesting output about
2890 schedule_block (b, file)
2897 int i, j, n_ready = 0, new_ready, n_insns = 0;
2898 int sched_n_insns = 0;
2900 #define NEED_NOTHING 0
2905 /* HEAD and TAIL delimit the region being scheduled. */
2906 rtx head = basic_block_head[b];
2907 rtx tail = basic_block_end[b];
2908 /* PREV_HEAD and NEXT_TAIL are the boundaries of the insns
2909 being scheduled. When the insns have been ordered,
2910 these insns delimit where the new insns are to be
2911 spliced back into the insn chain. */
2915 /* Keep life information accurate. */
2916 register struct sometimes *regs_sometimes_live;
2920 fprintf (file, ";;\t -- basic block number %d from %d to %d --\n",
2921 b, INSN_UID (basic_block_head[b]), INSN_UID (basic_block_end[b]));
2924 reg_last_uses = (rtx *) alloca (i * sizeof (rtx));
2925 bzero (reg_last_uses, i * sizeof (rtx));
2926 reg_last_sets = (rtx *) alloca (i * sizeof (rtx));
2927 bzero (reg_last_sets, i * sizeof (rtx));
2930 /* Remove certain insns at the beginning from scheduling,
2931 by advancing HEAD. */
2933 /* At the start of a function, before reload has run, don't delay getting
2934 parameters from hard registers into pseudo registers. */
2935 if (reload_completed == 0 && b == 0)
2938 && GET_CODE (head) == NOTE
2939 && NOTE_LINE_NUMBER (head) != NOTE_INSN_FUNCTION_BEG)
2940 head = NEXT_INSN (head);
2942 && GET_CODE (head) == INSN
2943 && GET_CODE (PATTERN (head)) == SET)
2945 rtx src = SET_SRC (PATTERN (head));
2946 while (GET_CODE (src) == SUBREG
2947 || GET_CODE (src) == SIGN_EXTEND
2948 || GET_CODE (src) == ZERO_EXTEND
2949 || GET_CODE (src) == SIGN_EXTRACT
2950 || GET_CODE (src) == ZERO_EXTRACT)
2951 src = XEXP (src, 0);
2952 if (GET_CODE (src) != REG
2953 || REGNO (src) >= FIRST_PSEUDO_REGISTER)
2955 /* Keep this insn from ever being scheduled. */
2956 INSN_REF_COUNT (head) = 1;
2957 head = NEXT_INSN (head);
2961 /* Don't include any notes or labels at the beginning of the
2962 basic block, or notes at the ends of basic blocks. */
2963 while (head != tail)
2965 if (GET_CODE (head) == NOTE)
2966 head = NEXT_INSN (head);
2967 else if (GET_CODE (tail) == NOTE)
2968 tail = PREV_INSN (tail);
2969 else if (GET_CODE (head) == CODE_LABEL)
2970 head = NEXT_INSN (head);
2973 /* If the only insn left is a NOTE or a CODE_LABEL, then there is no need
2974 to schedule this block. */
2976 && (GET_CODE (head) == NOTE || GET_CODE (head) == CODE_LABEL))
2980 /* This short-cut doesn't work. It does not count call insns crossed by
2981 registers in reg_sometimes_live. It does not mark these registers as
2982 dead if they die in this block. It does not mark these registers live
2983 (or create new reg_sometimes_live entries if necessary) if they are born
2986 The easy solution is to just always schedule a block. This block only
2987 has one insn, so this won't slow down this pass by much. */
2993 /* Now HEAD through TAIL are the insns actually to be rearranged;
2994 Let PREV_HEAD and NEXT_TAIL enclose them. */
2995 prev_head = PREV_INSN (head);
2996 next_tail = NEXT_INSN (tail);
2998 /* Initialize basic block data structures. */
3000 pending_read_insns = 0;
3001 pending_read_mems = 0;
3002 pending_write_insns = 0;
3003 pending_write_mems = 0;
3004 pending_lists_length = 0;
3005 last_pending_memory_flush = 0;
3006 last_function_call = 0;
3007 last_scheduled_insn = 0;
3009 LOG_LINKS (sched_before_next_call) = 0;
3011 n_insns += sched_analyze (head, tail);
3014 free_pending_lists ();
3018 /* Allocate vector to hold insns to be rearranged (except those
3019 insns which are controlled by an insn with SCHED_GROUP_P set).
3020 All these insns are included between ORIG_HEAD and ORIG_TAIL,
3021 as those variables ultimately are set up. */
3022 ready = (rtx *) alloca ((n_insns+1) * sizeof (rtx));
3024 /* TAIL is now the last of the insns to be rearranged.
3025 Put those insns into the READY vector. */
3028 /* For all branches, calls, uses, and cc0 setters, force them to remain
3029 in order at the end of the block by adding dependencies and giving
3030 the last a high priority. There may be notes present, and prev_head
3033 Branches must obviously remain at the end. Calls should remain at the
3034 end since moving them results in worse register allocation. Uses remain
3035 at the end to ensure proper register allocation. cc0 setters remaim
3036 at the end because they can't be moved away from their cc0 user. */
3038 while (GET_CODE (insn) == CALL_INSN || GET_CODE (insn) == JUMP_INSN
3039 || (GET_CODE (insn) == INSN
3040 && (GET_CODE (PATTERN (insn)) == USE
3042 || sets_cc0_p (PATTERN (insn))
3045 || GET_CODE (insn) == NOTE)
3047 if (GET_CODE (insn) != NOTE)
3052 ready[n_ready++] = insn;
3053 INSN_PRIORITY (insn) = TAIL_PRIORITY - i;
3054 INSN_REF_COUNT (insn) = 0;
3056 else if (! find_insn_list (insn, LOG_LINKS (last)))
3058 add_dependence (last, insn, REG_DEP_ANTI);
3059 INSN_REF_COUNT (insn)++;
3063 /* Skip over insns that are part of a group. */
3064 while (SCHED_GROUP_P (insn))
3066 insn = prev_nonnote_insn (insn);
3071 insn = PREV_INSN (insn);
3072 /* Don't overrun the bounds of the basic block. */
3073 if (insn == prev_head)
3077 /* Assign priorities to instructions. Also check whether they
3078 are in priority order already. If so then I will be nonnegative.
3079 We use this shortcut only before reloading. */
3081 i = reload_completed ? DONE_PRIORITY : MAX_PRIORITY;
3084 for (; insn != prev_head; insn = PREV_INSN (insn))
3086 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
3089 if (INSN_REF_COUNT (insn) == 0)
3092 ready[n_ready++] = insn;
3095 /* Make this dependent on the last of the instructions
3096 that must remain in order at the end of the block. */
3097 add_dependence (last, insn, REG_DEP_ANTI);
3098 INSN_REF_COUNT (insn) = 1;
3101 if (SCHED_GROUP_P (insn))
3103 while (SCHED_GROUP_P (insn))
3105 insn = PREV_INSN (insn);
3106 while (GET_CODE (insn) == NOTE)
3107 insn = PREV_INSN (insn);
3115 if (INSN_PRIORITY (insn) < i)
3116 i = INSN_PRIORITY (insn);
3117 else if (INSN_PRIORITY (insn) > i)
3124 /* This short-cut doesn't work. It does not count call insns crossed by
3125 registers in reg_sometimes_live. It does not mark these registers as
3126 dead if they die in this block. It does not mark these registers live
3127 (or create new reg_sometimes_live entries if necessary) if they are born
3130 The easy solution is to just always schedule a block. These blocks tend
3131 to be very short, so this doesn't slow down this pass by much. */
3133 /* If existing order is good, don't bother to reorder. */
3134 if (i != DONE_PRIORITY)
3137 fprintf (file, ";; already scheduled\n");
3139 if (reload_completed == 0)
3141 for (i = 0; i < sometimes_max; i++)
3142 regs_sometimes_live[i].live_length += n_insns;
3144 finish_sometimes_live (regs_sometimes_live, sometimes_max);
3146 free_pending_lists ();
3151 /* Scan all the insns to be scheduled, removing NOTE insns
3152 and register death notes.
3153 Line number NOTE insns end up in NOTE_LIST.
3154 Register death notes end up in DEAD_NOTES.
3156 Recreate the register life information for the end of this basic
3159 if (reload_completed == 0)
3161 bcopy (basic_block_live_at_start[b], bb_live_regs, regset_bytes);
3162 bzero (bb_dead_regs, regset_bytes);
3166 /* This is the first block in the function. There may be insns
3167 before head that we can't schedule. We still need to examine
3168 them though for accurate register lifetime analysis. */
3170 /* We don't want to remove any REG_DEAD notes as the code below
3173 for (insn = basic_block_head[b]; insn != head;
3174 insn = NEXT_INSN (insn))
3175 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
3177 /* See if the register gets born here. */
3178 /* We must check for registers being born before we check for
3179 registers dying. It is possible for a register to be born
3180 and die in the same insn, e.g. reading from a volatile
3181 memory location into an otherwise unused register. Such
3182 a register must be marked as dead after this insn. */
3183 if (GET_CODE (PATTERN (insn)) == SET
3184 || GET_CODE (PATTERN (insn)) == CLOBBER)
3185 sched_note_set (b, PATTERN (insn), 0);
3186 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
3189 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
3190 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
3191 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
3192 sched_note_set (b, XVECEXP (PATTERN (insn), 0, j), 0);
3194 /* ??? This code is obsolete and should be deleted. It
3195 is harmless though, so we will leave it in for now. */
3196 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
3197 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == USE)
3198 sched_note_set (b, XVECEXP (PATTERN (insn), 0, j), 0);
3201 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
3203 if ((REG_NOTE_KIND (link) == REG_DEAD
3204 || REG_NOTE_KIND (link) == REG_UNUSED)
3205 /* Verify that the REG_NOTE has a legal value. */
3206 && GET_CODE (XEXP (link, 0)) == REG)
3208 register int regno = REGNO (XEXP (link, 0));
3209 register int offset = regno / REGSET_ELT_BITS;
3210 register REGSET_ELT_TYPE bit
3211 = (REGSET_ELT_TYPE) 1 << (regno % REGSET_ELT_BITS);
3213 if (regno < FIRST_PSEUDO_REGISTER)
3215 int j = HARD_REGNO_NREGS (regno,
3216 GET_MODE (XEXP (link, 0)));
3219 offset = (regno + j) / REGSET_ELT_BITS;
3220 bit = ((REGSET_ELT_TYPE) 1
3221 << ((regno + j) % REGSET_ELT_BITS));
3223 bb_live_regs[offset] &= ~bit;
3224 bb_dead_regs[offset] |= bit;
3229 bb_live_regs[offset] &= ~bit;
3230 bb_dead_regs[offset] |= bit;
3238 /* If debugging information is being produced, keep track of the line
3239 number notes for each insn. */
3240 if (write_symbols != NO_DEBUG)
3242 /* We must use the true line number for the first insn in the block
3243 that was computed and saved at the start of this pass. We can't
3244 use the current line number, because scheduling of the previous
3245 block may have changed the current line number. */
3246 rtx line = line_note_head[b];
3248 for (insn = basic_block_head[b];
3250 insn = NEXT_INSN (insn))
3251 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
3254 LINE_NOTE (insn) = line;
3257 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
3259 rtx prev, next, link;
3261 /* Farm out notes. This is needed to keep the debugger from
3262 getting completely deranged. */
3263 if (GET_CODE (insn) == NOTE)
3266 insn = unlink_notes (insn, next_tail);
3271 if (insn == next_tail)
3275 if (reload_completed == 0
3276 && GET_RTX_CLASS (GET_CODE (insn)) == 'i')
3278 /* See if the register gets born here. */
3279 /* We must check for registers being born before we check for
3280 registers dying. It is possible for a register to be born and
3281 die in the same insn, e.g. reading from a volatile memory
3282 location into an otherwise unused register. Such a register
3283 must be marked as dead after this insn. */
3284 if (GET_CODE (PATTERN (insn)) == SET
3285 || GET_CODE (PATTERN (insn)) == CLOBBER)
3286 sched_note_set (b, PATTERN (insn), 0);
3287 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
3290 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
3291 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
3292 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
3293 sched_note_set (b, XVECEXP (PATTERN (insn), 0, j), 0);
3295 /* ??? This code is obsolete and should be deleted. It
3296 is harmless though, so we will leave it in for now. */
3297 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
3298 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == USE)
3299 sched_note_set (b, XVECEXP (PATTERN (insn), 0, j), 0);
3302 /* Need to know what registers this insn kills. */
3303 for (prev = 0, link = REG_NOTES (insn); link; link = next)
3307 next = XEXP (link, 1);
3308 if ((REG_NOTE_KIND (link) == REG_DEAD
3309 || REG_NOTE_KIND (link) == REG_UNUSED)
3310 /* Verify that the REG_NOTE has a legal value. */
3311 && GET_CODE (XEXP (link, 0)) == REG)
3313 register int regno = REGNO (XEXP (link, 0));
3314 register int offset = regno / REGSET_ELT_BITS;
3315 register REGSET_ELT_TYPE bit
3316 = (REGSET_ELT_TYPE) 1 << (regno % REGSET_ELT_BITS);
3318 /* Only unlink REG_DEAD notes; leave REG_UNUSED notes
3320 if (REG_NOTE_KIND (link) == REG_DEAD)
3323 XEXP (prev, 1) = next;
3325 REG_NOTES (insn) = next;
3326 XEXP (link, 1) = dead_notes;
3332 if (regno < FIRST_PSEUDO_REGISTER)
3334 int j = HARD_REGNO_NREGS (regno,
3335 GET_MODE (XEXP (link, 0)));
3338 offset = (regno + j) / REGSET_ELT_BITS;
3339 bit = ((REGSET_ELT_TYPE) 1
3340 << ((regno + j) % REGSET_ELT_BITS));
3342 bb_live_regs[offset] &= ~bit;
3343 bb_dead_regs[offset] |= bit;
3348 bb_live_regs[offset] &= ~bit;
3349 bb_dead_regs[offset] |= bit;
3358 if (reload_completed == 0)
3360 /* Keep track of register lives. */
3361 old_live_regs = (regset) alloca (regset_bytes);
3363 = (struct sometimes *) alloca (max_regno * sizeof (struct sometimes));
3366 /* Start with registers live at end. */
3367 for (j = 0; j < regset_size; j++)
3369 REGSET_ELT_TYPE live = bb_live_regs[j];
3370 old_live_regs[j] = live;
3373 register REGSET_ELT_TYPE bit;
3374 for (bit = 0; bit < REGSET_ELT_BITS; bit++)
3375 if (live & ((REGSET_ELT_TYPE) 1 << bit))
3376 sometimes_max = new_sometimes_live (regs_sometimes_live, j,
3377 bit, sometimes_max);
3382 SCHED_SORT (ready, n_ready, 1);
3386 fprintf (file, ";; ready list initially:\n;; ");
3387 for (i = 0; i < n_ready; i++)
3388 fprintf (file, "%d ", INSN_UID (ready[i]));
3389 fprintf (file, "\n\n");
3391 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
3392 if (INSN_PRIORITY (insn) > 0)
3393 fprintf (file, ";; insn[%4d]: priority = %4d, ref_count = %4d\n",
3394 INSN_UID (insn), INSN_PRIORITY (insn),
3395 INSN_REF_COUNT (insn));
3398 /* Now HEAD and TAIL are going to become disconnected
3399 entirely from the insn chain. */
3402 /* Q_SIZE will always be zero here. */
3403 q_ptr = 0; clock = 0;
3404 bzero (insn_queue, sizeof (insn_queue));
3406 /* Now, perform list scheduling. */
3408 /* Where we start inserting insns is after TAIL. */
3411 new_needs = (NEXT_INSN (prev_head) == basic_block_head[b]
3412 ? NEED_HEAD : NEED_NOTHING);
3413 if (PREV_INSN (next_tail) == basic_block_end[b])
3414 new_needs |= NEED_TAIL;
3416 new_ready = n_ready;
3417 while (sched_n_insns < n_insns)
3419 q_ptr = NEXT_Q (q_ptr); clock++;
3421 /* Add all pending insns that can be scheduled without stalls to the
3423 for (insn = insn_queue[q_ptr]; insn; insn = NEXT_INSN (insn))
3426 fprintf (file, ";; launching %d before %d with no stalls at T-%d\n",
3427 INSN_UID (insn), INSN_UID (last), clock);
3428 ready[new_ready++] = insn;
3431 insn_queue[q_ptr] = 0;
3433 /* If there are no ready insns, stall until one is ready and add all
3434 of the pending insns at that point to the ready list. */
3437 register int stalls;
3439 for (stalls = 1; stalls < INSN_QUEUE_SIZE; stalls++)
3440 if (insn = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)])
3442 for (; insn; insn = NEXT_INSN (insn))
3445 fprintf (file, ";; launching %d before %d with %d stalls at T-%d\n",
3446 INSN_UID (insn), INSN_UID (last), stalls, clock);
3447 ready[new_ready++] = insn;
3450 insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = 0;
3454 q_ptr = NEXT_Q_AFTER (q_ptr, stalls); clock += stalls;
3457 /* There should be some instructions waiting to fire. */
3463 fprintf (file, ";; ready list at T-%d:", clock);
3464 for (i = 0; i < new_ready; i++)
3465 fprintf (file, " %d (%x)",
3466 INSN_UID (ready[i]), INSN_PRIORITY (ready[i]));
3469 /* Sort the ready list and choose the best insn to schedule. Select
3470 which insn should issue in this cycle and queue those that are
3471 blocked by function unit hazards.
3473 N_READY holds the number of items that were scheduled the last time,
3474 minus the one instruction scheduled on the last loop iteration; it
3475 is not modified for any other reason in this loop. */
3477 SCHED_SORT (ready, new_ready, n_ready);
3478 if (MAX_BLOCKAGE > 1)
3480 new_ready = schedule_select (ready, new_ready, clock, file);
3484 fprintf (file, "\n");
3485 /* We must set n_ready here, to ensure that sorting always
3486 occurs when we come back to the SCHED_SORT line above. */
3491 n_ready = new_ready;
3492 last_scheduled_insn = insn = ready[0];
3494 /* The first insn scheduled becomes the new tail. */
3500 fprintf (file, ", now");
3501 for (i = 0; i < n_ready; i++)
3502 fprintf (file, " %d", INSN_UID (ready[i]));
3503 fprintf (file, "\n");
3506 if (DONE_PRIORITY_P (insn))
3509 if (reload_completed == 0)
3511 /* Process this insn, and each insn linked to this one which must
3512 be immediately output after this insn. */
3515 /* First we kill registers set by this insn, and then we
3516 make registers used by this insn live. This is the opposite
3517 order used above because we are traversing the instructions
3520 /* Strictly speaking, we should scan REG_UNUSED notes and make
3521 every register mentioned there live, however, we will just
3522 kill them again immediately below, so there doesn't seem to
3523 be any reason why we bother to do this. */
3525 /* See if this is the last notice we must take of a register. */
3526 if (GET_CODE (PATTERN (insn)) == SET
3527 || GET_CODE (PATTERN (insn)) == CLOBBER)
3528 sched_note_set (b, PATTERN (insn), 1);
3529 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
3532 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
3533 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
3534 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
3535 sched_note_set (b, XVECEXP (PATTERN (insn), 0, j), 1);
3538 /* This code keeps life analysis information up to date. */
3539 if (GET_CODE (insn) == CALL_INSN)
3541 register struct sometimes *p;
3543 /* A call kills all call used and global registers, except
3544 for those mentioned in the call pattern which will be
3545 made live again later. */
3546 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3547 if (call_used_regs[i] || global_regs[i])
3549 register int offset = i / REGSET_ELT_BITS;
3550 register REGSET_ELT_TYPE bit
3551 = (REGSET_ELT_TYPE) 1 << (i % REGSET_ELT_BITS);
3553 bb_live_regs[offset] &= ~bit;
3554 bb_dead_regs[offset] |= bit;
3557 /* Regs live at the time of a call instruction must not
3558 go in a register clobbered by calls. Record this for
3559 all regs now live. Note that insns which are born or
3560 die in a call do not cross a call, so this must be done
3561 after the killings (above) and before the births
3563 p = regs_sometimes_live;
3564 for (i = 0; i < sometimes_max; i++, p++)
3565 if (bb_live_regs[p->offset]
3566 & ((REGSET_ELT_TYPE) 1 << p->bit))
3567 p->calls_crossed += 1;
3570 /* Make every register used live, and add REG_DEAD notes for
3571 registers which were not live before we started. */
3572 attach_deaths_insn (insn);
3574 /* Find registers now made live by that instruction. */
3575 for (i = 0; i < regset_size; i++)
3577 REGSET_ELT_TYPE diff = bb_live_regs[i] & ~old_live_regs[i];
3581 old_live_regs[i] |= diff;
3582 for (bit = 0; bit < REGSET_ELT_BITS; bit++)
3583 if (diff & ((REGSET_ELT_TYPE) 1 << bit))
3585 = new_sometimes_live (regs_sometimes_live, i, bit,
3590 /* Count lengths of all regs we are worrying about now,
3591 and handle registers no longer live. */
3593 for (i = 0; i < sometimes_max; i++)
3595 register struct sometimes *p = ®s_sometimes_live[i];
3596 int regno = p->offset*REGSET_ELT_BITS + p->bit;
3598 p->live_length += 1;
3600 if ((bb_live_regs[p->offset]
3601 & ((REGSET_ELT_TYPE) 1 << p->bit)) == 0)
3603 /* This is the end of one of this register's lifetime
3604 segments. Save the lifetime info collected so far,
3605 and clear its bit in the old_live_regs entry. */
3606 sched_reg_live_length[regno] += p->live_length;
3607 sched_reg_n_calls_crossed[regno] += p->calls_crossed;
3608 old_live_regs[p->offset]
3609 &= ~((REGSET_ELT_TYPE) 1 << p->bit);
3611 /* Delete the reg_sometimes_live entry for this reg by
3612 copying the last entry over top of it. */
3613 *p = regs_sometimes_live[--sometimes_max];
3614 /* ...and decrement i so that this newly copied entry
3615 will be processed. */
3621 insn = PREV_INSN (insn);
3623 while (SCHED_GROUP_P (link));
3625 /* Set INSN back to the insn we are scheduling now. */
3629 /* Schedule INSN. Remove it from the ready list. */
3634 NEXT_INSN (insn) = last;
3635 PREV_INSN (last) = insn;
3638 /* Everything that precedes INSN now either becomes "ready", if
3639 it can execute immediately before INSN, or "pending", if
3640 there must be a delay. Give INSN high enough priority that
3641 at least one (maybe more) reg-killing insns can be launched
3642 ahead of all others. Mark INSN as scheduled by changing its
3644 INSN_PRIORITY (insn) = LAUNCH_PRIORITY;
3645 new_ready = schedule_insn (insn, ready, n_ready, clock);
3646 INSN_PRIORITY (insn) = DONE_PRIORITY;
3648 /* Schedule all prior insns that must not be moved. */
3649 if (SCHED_GROUP_P (insn))
3651 /* Disable these insns from being launched. */
3653 while (SCHED_GROUP_P (link))
3655 /* Disable these insns from being launched by anybody. */
3656 link = PREV_INSN (link);
3657 INSN_REF_COUNT (link) = 0;
3660 /* None of these insns can move forward into delay slots. */
3661 while (SCHED_GROUP_P (insn))
3663 insn = PREV_INSN (insn);
3664 new_ready = schedule_insn (insn, ready, new_ready, clock);
3665 INSN_PRIORITY (insn) = DONE_PRIORITY;
3668 NEXT_INSN (insn) = last;
3669 PREV_INSN (last) = insn;
3677 if (reload_completed == 0)
3678 finish_sometimes_live (regs_sometimes_live, sometimes_max);
3680 /* HEAD is now the first insn in the chain of insns that
3681 been scheduled by the loop above.
3682 TAIL is the last of those insns. */
3685 /* NOTE_LIST is the end of a chain of notes previously found
3686 among the insns. Insert them at the beginning of the insns. */
3689 rtx note_head = note_list;
3690 while (PREV_INSN (note_head))
3691 note_head = PREV_INSN (note_head);
3693 PREV_INSN (head) = note_list;
3694 NEXT_INSN (note_list) = head;
3698 /* There should be no REG_DEAD notes leftover at the end.
3699 In practice, this can occur as the result of bugs in flow, combine.c,
3700 and/or sched.c. The values of the REG_DEAD notes remaining are
3701 meaningless, because dead_notes is just used as a free list. */
3703 if (dead_notes != 0)
3707 if (new_needs & NEED_HEAD)
3708 basic_block_head[b] = head;
3709 PREV_INSN (head) = prev_head;
3710 NEXT_INSN (prev_head) = head;
3712 if (new_needs & NEED_TAIL)
3713 basic_block_end[b] = tail;
3714 NEXT_INSN (tail) = next_tail;
3715 PREV_INSN (next_tail) = tail;
3717 /* Restore the line-number notes of each insn. */
3718 if (write_symbols != NO_DEBUG)
3720 rtx line, note, prev, new;
3723 head = basic_block_head[b];
3724 next_tail = NEXT_INSN (basic_block_end[b]);
3726 /* Determine the current line-number. We want to know the current
3727 line number of the first insn of the block here, in case it is
3728 different from the true line number that was saved earlier. If
3729 different, then we need a line number note before the first insn
3730 of this block. If it happens to be the same, then we don't want to
3731 emit another line number note here. */
3732 for (line = head; line; line = PREV_INSN (line))
3733 if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
3736 /* Walk the insns keeping track of the current line-number and inserting
3737 the line-number notes as needed. */
3738 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
3739 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
3741 else if (! (GET_CODE (insn) == NOTE
3742 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED)
3743 && (note = LINE_NOTE (insn)) != 0
3746 || NOTE_LINE_NUMBER (note) != NOTE_LINE_NUMBER (line)
3747 || NOTE_SOURCE_FILE (note) != NOTE_SOURCE_FILE (line)))
3750 prev = PREV_INSN (insn);
3751 if (LINE_NOTE (note))
3753 /* Re-use the original line-number note. */
3754 LINE_NOTE (note) = 0;
3755 PREV_INSN (note) = prev;
3756 NEXT_INSN (prev) = note;
3757 PREV_INSN (insn) = note;
3758 NEXT_INSN (note) = insn;
3763 new = emit_note_after (NOTE_LINE_NUMBER (note), prev);
3764 NOTE_SOURCE_FILE (new) = NOTE_SOURCE_FILE (note);
3768 fprintf (file, ";; added %d line-number notes\n", notes);
3773 fprintf (file, ";; total time = %d\n;; new basic block head = %d\n;; new basic block end = %d\n\n",
3774 clock, INSN_UID (basic_block_head[b]), INSN_UID (basic_block_end[b]));
3777 /* Yow! We're done! */
3778 free_pending_lists ();
3783 /* Subroutine of split_hard_reg_notes. Searches X for any reference to
3784 REGNO, returning the rtx of the reference found if any. Otherwise,
3788 regno_use_in (regno, x)
3796 if (GET_CODE (x) == REG && REGNO (x) == regno)
3799 fmt = GET_RTX_FORMAT (GET_CODE (x));
3800 for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
3804 if (tem = regno_use_in (regno, XEXP (x, i)))
3807 else if (fmt[i] == 'E')
3808 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3809 if (tem = regno_use_in (regno , XVECEXP (x, i, j)))
3816 /* Subroutine of update_flow_info. Determines whether any new REG_NOTEs are
3817 needed for the hard register mentioned in the note. This can happen
3818 if the reference to the hard register in the original insn was split into
3819 several smaller hard register references in the split insns. */
3822 split_hard_reg_notes (note, first, last, orig_insn)
3823 rtx note, first, last, orig_insn;
3825 rtx reg, temp, link;
3826 int n_regs, i, new_reg;
3829 /* Assume that this is a REG_DEAD note. */
3830 if (REG_NOTE_KIND (note) != REG_DEAD)
3833 reg = XEXP (note, 0);
3835 n_regs = HARD_REGNO_NREGS (REGNO (reg), GET_MODE (reg));
3837 for (i = 0; i < n_regs; i++)
3839 new_reg = REGNO (reg) + i;
3841 /* Check for references to new_reg in the split insns. */
3842 for (insn = last; ; insn = PREV_INSN (insn))
3844 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
3845 && (temp = regno_use_in (new_reg, PATTERN (insn))))
3847 /* Create a new reg dead note here. */
3848 link = rtx_alloc (EXPR_LIST);
3849 PUT_REG_NOTE_KIND (link, REG_DEAD);
3850 XEXP (link, 0) = temp;
3851 XEXP (link, 1) = REG_NOTES (insn);
3852 REG_NOTES (insn) = link;
3854 /* If killed multiple registers here, then add in the excess. */
3855 i += HARD_REGNO_NREGS (REGNO (temp), GET_MODE (temp)) - 1;
3859 /* It isn't mentioned anywhere, so no new reg note is needed for
3867 /* Subroutine of update_flow_info. Determines whether a SET or CLOBBER in an
3868 insn created by splitting needs a REG_DEAD or REG_UNUSED note added. */
3871 new_insn_dead_notes (pat, insn, last, orig_insn)
3872 rtx pat, insn, last, orig_insn;
3876 /* PAT is either a CLOBBER or a SET here. */
3877 dest = XEXP (pat, 0);
3879 while (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SUBREG
3880 || GET_CODE (dest) == STRICT_LOW_PART
3881 || GET_CODE (dest) == SIGN_EXTRACT)
3882 dest = XEXP (dest, 0);
3884 if (GET_CODE (dest) == REG)
3886 for (tem = last; tem != insn; tem = PREV_INSN (tem))
3888 if (GET_RTX_CLASS (GET_CODE (tem)) == 'i'
3889 && reg_overlap_mentioned_p (dest, PATTERN (tem))
3890 && (set = single_set (tem)))
3892 rtx tem_dest = SET_DEST (set);
3894 while (GET_CODE (tem_dest) == ZERO_EXTRACT
3895 || GET_CODE (tem_dest) == SUBREG
3896 || GET_CODE (tem_dest) == STRICT_LOW_PART
3897 || GET_CODE (tem_dest) == SIGN_EXTRACT)
3898 tem_dest = XEXP (tem_dest, 0);
3900 if (tem_dest != dest)
3902 /* Use the same scheme as combine.c, don't put both REG_DEAD
3903 and REG_UNUSED notes on the same insn. */
3904 if (! find_regno_note (tem, REG_UNUSED, REGNO (dest))
3905 && ! find_regno_note (tem, REG_DEAD, REGNO (dest)))
3907 rtx note = rtx_alloc (EXPR_LIST);
3908 PUT_REG_NOTE_KIND (note, REG_DEAD);
3909 XEXP (note, 0) = dest;
3910 XEXP (note, 1) = REG_NOTES (tem);
3911 REG_NOTES (tem) = note;
3913 /* The reg only dies in one insn, the last one that uses
3917 else if (reg_overlap_mentioned_p (dest, SET_SRC (set)))
3918 /* We found an instruction that both uses the register,
3919 and sets it, so no new REG_NOTE is needed for this set. */
3923 /* If this is a set, it must die somewhere, unless it is the dest of
3924 the original insn, and hence is live after the original insn. Abort
3925 if it isn't supposed to be live after the original insn.
3927 If this is a clobber, then just add a REG_UNUSED note. */
3930 int live_after_orig_insn = 0;
3931 rtx pattern = PATTERN (orig_insn);
3934 if (GET_CODE (pat) == CLOBBER)
3936 rtx note = rtx_alloc (EXPR_LIST);
3937 PUT_REG_NOTE_KIND (note, REG_UNUSED);
3938 XEXP (note, 0) = dest;
3939 XEXP (note, 1) = REG_NOTES (insn);
3940 REG_NOTES (insn) = note;
3944 /* The original insn could have multiple sets, so search the
3945 insn for all sets. */
3946 if (GET_CODE (pattern) == SET)
3948 if (reg_overlap_mentioned_p (dest, SET_DEST (pattern)))
3949 live_after_orig_insn = 1;
3951 else if (GET_CODE (pattern) == PARALLEL)
3953 for (i = 0; i < XVECLEN (pattern, 0); i++)
3954 if (GET_CODE (XVECEXP (pattern, 0, i)) == SET
3955 && reg_overlap_mentioned_p (dest,
3956 SET_DEST (XVECEXP (pattern,
3958 live_after_orig_insn = 1;
3961 if (! live_after_orig_insn)
3967 /* Subroutine of update_flow_info. Update the value of reg_n_sets for all
3968 registers modified by X. INC is -1 if the containing insn is being deleted,
3969 and is 1 if the containing insn is a newly generated insn. */
3972 update_n_sets (x, inc)
3976 rtx dest = SET_DEST (x);
3978 while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
3979 || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
3980 dest = SUBREG_REG (dest);
3982 if (GET_CODE (dest) == REG)
3984 int regno = REGNO (dest);
3986 if (regno < FIRST_PSEUDO_REGISTER)
3989 int endregno = regno + HARD_REGNO_NREGS (regno, GET_MODE (dest));
3991 for (i = regno; i < endregno; i++)
3992 reg_n_sets[i] += inc;
3995 reg_n_sets[regno] += inc;
3999 /* Updates all flow-analysis related quantities (including REG_NOTES) for
4000 the insns from FIRST to LAST inclusive that were created by splitting
4001 ORIG_INSN. NOTES are the original REG_NOTES. */
4004 update_flow_info (notes, first, last, orig_insn)
4011 rtx orig_dest, temp;
4014 /* Get and save the destination set by the original insn. */
4016 orig_dest = single_set (orig_insn);
4018 orig_dest = SET_DEST (orig_dest);
4020 /* Move REG_NOTES from the original insn to where they now belong. */
4022 for (note = notes; note; note = next)
4024 next = XEXP (note, 1);
4025 switch (REG_NOTE_KIND (note))
4029 /* Move these notes from the original insn to the last new insn where
4030 the register is now set. */
4032 for (insn = last; ; insn = PREV_INSN (insn))
4034 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
4035 && reg_mentioned_p (XEXP (note, 0), PATTERN (insn)))
4037 /* If this note refers to a multiple word hard register, it
4038 may have been split into several smaller hard register
4039 references, so handle it specially. */
4040 temp = XEXP (note, 0);
4041 if (REG_NOTE_KIND (note) == REG_DEAD
4042 && GET_CODE (temp) == REG
4043 && REGNO (temp) < FIRST_PSEUDO_REGISTER
4044 && HARD_REGNO_NREGS (REGNO (temp), GET_MODE (temp)) > 1)
4045 split_hard_reg_notes (note, first, last, orig_insn);
4048 XEXP (note, 1) = REG_NOTES (insn);
4049 REG_NOTES (insn) = note;
4052 /* Sometimes need to convert REG_UNUSED notes to REG_DEAD
4054 /* ??? This won't handle multiple word registers correctly,
4055 but should be good enough for now. */
4056 if (REG_NOTE_KIND (note) == REG_UNUSED
4057 && ! dead_or_set_p (insn, XEXP (note, 0)))
4058 PUT_REG_NOTE_KIND (note, REG_DEAD);
4060 /* The reg only dies in one insn, the last one that uses
4064 /* It must die somewhere, fail it we couldn't find where it died.
4066 If this is a REG_UNUSED note, then it must be a temporary
4067 register that was not needed by this instantiation of the
4068 pattern, so we can safely ignore it. */
4071 if (REG_NOTE_KIND (note) != REG_UNUSED)
4080 /* This note applies to the dest of the original insn. Find the
4081 first new insn that now has the same dest, and move the note
4087 for (insn = first; ; insn = NEXT_INSN (insn))
4089 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
4090 && (temp = single_set (insn))
4091 && rtx_equal_p (SET_DEST (temp), orig_dest))
4093 XEXP (note, 1) = REG_NOTES (insn);
4094 REG_NOTES (insn) = note;
4095 /* The reg is only zero before one insn, the first that
4099 /* It must be set somewhere, fail if we couldn't find where it
4108 /* A REG_EQUIV or REG_EQUAL note on an insn with more than one
4109 set is meaningless. Just drop the note. */
4113 case REG_NO_CONFLICT:
4114 /* These notes apply to the dest of the original insn. Find the last
4115 new insn that now has the same dest, and move the note there. */
4120 for (insn = last; ; insn = PREV_INSN (insn))
4122 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
4123 && (temp = single_set (insn))
4124 && rtx_equal_p (SET_DEST (temp), orig_dest))
4126 XEXP (note, 1) = REG_NOTES (insn);
4127 REG_NOTES (insn) = note;
4128 /* Only put this note on one of the new insns. */
4132 /* The original dest must still be set someplace. Abort if we
4133 couldn't find it. */
4140 /* Move a REG_LIBCALL note to the first insn created, and update
4141 the corresponding REG_RETVAL note. */
4142 XEXP (note, 1) = REG_NOTES (first);
4143 REG_NOTES (first) = note;
4145 insn = XEXP (note, 0);
4146 note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
4148 XEXP (note, 0) = first;
4152 /* Move a REG_RETVAL note to the last insn created, and update
4153 the corresponding REG_LIBCALL note. */
4154 XEXP (note, 1) = REG_NOTES (last);
4155 REG_NOTES (last) = note;
4157 insn = XEXP (note, 0);
4158 note = find_reg_note (insn, REG_LIBCALL, NULL_RTX);
4160 XEXP (note, 0) = last;
4164 /* This should be moved to whichever instruction is a JUMP_INSN. */
4166 for (insn = last; ; insn = PREV_INSN (insn))
4168 if (GET_CODE (insn) == JUMP_INSN)
4170 XEXP (note, 1) = REG_NOTES (insn);
4171 REG_NOTES (insn) = note;
4172 /* Only put this note on one of the new insns. */
4175 /* Fail if we couldn't find a JUMP_INSN. */
4182 /* This should be moved to whichever instruction now has the
4183 increment operation. */
4187 /* Should be moved to the new insn(s) which use the label. */
4188 for (insn = first; insn != NEXT_INSN (last); insn = NEXT_INSN (insn))
4189 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
4190 && reg_mentioned_p (XEXP (note, 0), PATTERN (insn)))
4191 REG_NOTES (insn) = gen_rtx (EXPR_LIST, REG_LABEL,
4192 XEXP (note, 0), REG_NOTES (insn));
4197 /* These two notes will never appear until after reorg, so we don't
4198 have to handle them here. */
4204 /* Each new insn created, except the last, has a new set. If the destination
4205 is a register, then this reg is now live across several insns, whereas
4206 previously the dest reg was born and died within the same insn. To
4207 reflect this, we now need a REG_DEAD note on the insn where this
4210 Similarly, the new insns may have clobbers that need REG_UNUSED notes. */
4212 for (insn = first; insn != last; insn = NEXT_INSN (insn))
4217 pat = PATTERN (insn);
4218 if (GET_CODE (pat) == SET || GET_CODE (pat) == CLOBBER)
4219 new_insn_dead_notes (pat, insn, last, orig_insn);
4220 else if (GET_CODE (pat) == PARALLEL)
4222 for (i = 0; i < XVECLEN (pat, 0); i++)
4223 if (GET_CODE (XVECEXP (pat, 0, i)) == SET
4224 || GET_CODE (XVECEXP (pat, 0, i)) == CLOBBER)
4225 new_insn_dead_notes (XVECEXP (pat, 0, i), insn, last, orig_insn);
4229 /* If any insn, except the last, uses the register set by the last insn,
4230 then we need a new REG_DEAD note on that insn. In this case, there
4231 would not have been a REG_DEAD note for this register in the original
4232 insn because it was used and set within one insn.
4234 There is no new REG_DEAD note needed if the last insn uses the register
4235 that it is setting. */
4237 set = single_set (last);
4240 rtx dest = SET_DEST (set);
4242 while (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SUBREG
4243 || GET_CODE (dest) == STRICT_LOW_PART
4244 || GET_CODE (dest) == SIGN_EXTRACT)
4245 dest = XEXP (dest, 0);
4247 if (GET_CODE (dest) == REG
4248 && ! reg_overlap_mentioned_p (dest, SET_SRC (set)))
4250 for (insn = PREV_INSN (last); ; insn = PREV_INSN (insn))
4252 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
4253 && reg_mentioned_p (dest, PATTERN (insn))
4254 && (set = single_set (insn)))
4256 rtx insn_dest = SET_DEST (set);
4258 while (GET_CODE (insn_dest) == ZERO_EXTRACT
4259 || GET_CODE (insn_dest) == SUBREG
4260 || GET_CODE (insn_dest) == STRICT_LOW_PART
4261 || GET_CODE (insn_dest) == SIGN_EXTRACT)
4262 insn_dest = XEXP (insn_dest, 0);
4264 if (insn_dest != dest)
4266 note = rtx_alloc (EXPR_LIST);
4267 PUT_REG_NOTE_KIND (note, REG_DEAD);
4268 XEXP (note, 0) = dest;
4269 XEXP (note, 1) = REG_NOTES (insn);
4270 REG_NOTES (insn) = note;
4271 /* The reg only dies in one insn, the last one
4282 /* If the original dest is modifying a multiple register target, and the
4283 original instruction was split such that the original dest is now set
4284 by two or more SUBREG sets, then the split insns no longer kill the
4285 destination of the original insn.
4287 In this case, if there exists an instruction in the same basic block,
4288 before the split insn, which uses the original dest, and this use is
4289 killed by the original insn, then we must remove the REG_DEAD note on
4290 this insn, because it is now superfluous.
4292 This does not apply when a hard register gets split, because the code
4293 knows how to handle overlapping hard registers properly. */
4294 if (orig_dest && GET_CODE (orig_dest) == REG)
4296 int found_orig_dest = 0;
4297 int found_split_dest = 0;
4299 for (insn = first; ; insn = NEXT_INSN (insn))
4301 set = single_set (insn);
4304 if (GET_CODE (SET_DEST (set)) == REG
4305 && REGNO (SET_DEST (set)) == REGNO (orig_dest))
4307 found_orig_dest = 1;
4310 else if (GET_CODE (SET_DEST (set)) == SUBREG
4311 && SUBREG_REG (SET_DEST (set)) == orig_dest)
4313 found_split_dest = 1;
4322 if (found_split_dest)
4324 /* Search backwards from FIRST, looking for the first insn that uses
4325 the original dest. Stop if we pass a CODE_LABEL or a JUMP_INSN.
4326 If we find an insn, and it has a REG_DEAD note, then delete the
4329 for (insn = first; insn; insn = PREV_INSN (insn))
4331 if (GET_CODE (insn) == CODE_LABEL
4332 || GET_CODE (insn) == JUMP_INSN)
4334 else if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
4335 && reg_mentioned_p (orig_dest, insn))
4337 note = find_regno_note (insn, REG_DEAD, REGNO (orig_dest));
4339 remove_note (insn, note);
4343 else if (! found_orig_dest)
4345 /* This should never happen. */
4350 /* Update reg_n_sets. This is necessary to prevent local alloc from
4351 converting REG_EQUAL notes to REG_EQUIV when splitting has modified
4352 a reg from set once to set multiple times. */
4355 rtx x = PATTERN (orig_insn);
4356 RTX_CODE code = GET_CODE (x);
4358 if (code == SET || code == CLOBBER)
4359 update_n_sets (x, -1);
4360 else if (code == PARALLEL)
4363 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
4365 code = GET_CODE (XVECEXP (x, 0, i));
4366 if (code == SET || code == CLOBBER)
4367 update_n_sets (XVECEXP (x, 0, i), -1);
4371 for (insn = first; ; insn = NEXT_INSN (insn))
4374 code = GET_CODE (x);
4376 if (code == SET || code == CLOBBER)
4377 update_n_sets (x, 1);
4378 else if (code == PARALLEL)
4381 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
4383 code = GET_CODE (XVECEXP (x, 0, i));
4384 if (code == SET || code == CLOBBER)
4385 update_n_sets (XVECEXP (x, 0, i), 1);
4395 /* The one entry point in this file. DUMP_FILE is the dump file for
4399 schedule_insns (dump_file)
4402 int max_uid = MAX_INSNS_PER_SPLIT * (get_max_uid () + 1);
4406 /* Taking care of this degenerate case makes the rest of
4407 this code simpler. */
4408 if (n_basic_blocks == 0)
4411 /* Create an insn here so that we can hang dependencies off of it later. */
4412 sched_before_next_call
4413 = gen_rtx (INSN, VOIDmode, 0, NULL_RTX, NULL_RTX,
4414 NULL_RTX, 0, NULL_RTX, 0);
4416 /* Initialize the unused_*_lists. We can't use the ones left over from
4417 the previous function, because gcc has freed that memory. We can use
4418 the ones left over from the first sched pass in the second pass however,
4419 so only clear them on the first sched pass. The first pass is before
4420 reload if flag_schedule_insns is set, otherwise it is afterwards. */
4422 if (reload_completed == 0 || ! flag_schedule_insns)
4424 unused_insn_list = 0;
4425 unused_expr_list = 0;
4428 /* We create no insns here, only reorder them, so we
4429 remember how far we can cut back the stack on exit. */
4431 /* Allocate data for this pass. See comments, above,
4432 for what these vectors do. */
4433 insn_luid = (int *) alloca (max_uid * sizeof (int));
4434 insn_priority = (int *) alloca (max_uid * sizeof (int));
4435 insn_tick = (int *) alloca (max_uid * sizeof (int));
4436 insn_costs = (short *) alloca (max_uid * sizeof (short));
4437 insn_units = (short *) alloca (max_uid * sizeof (short));
4438 insn_blockage = (unsigned int *) alloca (max_uid * sizeof (unsigned int));
4439 insn_ref_count = (int *) alloca (max_uid * sizeof (int));
4441 if (reload_completed == 0)
4443 sched_reg_n_deaths = (short *) alloca (max_regno * sizeof (short));
4444 sched_reg_n_calls_crossed = (int *) alloca (max_regno * sizeof (int));
4445 sched_reg_live_length = (int *) alloca (max_regno * sizeof (int));
4446 bb_dead_regs = (regset) alloca (regset_bytes);
4447 bb_live_regs = (regset) alloca (regset_bytes);
4448 bzero (sched_reg_n_calls_crossed, max_regno * sizeof (int));
4449 bzero (sched_reg_live_length, max_regno * sizeof (int));
4450 bcopy (reg_n_deaths, sched_reg_n_deaths, max_regno * sizeof (short));
4451 init_alias_analysis ();
4455 sched_reg_n_deaths = 0;
4456 sched_reg_n_calls_crossed = 0;
4457 sched_reg_live_length = 0;
4460 if (! flag_schedule_insns)
4461 init_alias_analysis ();
4464 if (write_symbols != NO_DEBUG)
4468 line_note = (rtx *) alloca (max_uid * sizeof (rtx));
4469 bzero (line_note, max_uid * sizeof (rtx));
4470 line_note_head = (rtx *) alloca (n_basic_blocks * sizeof (rtx));
4471 bzero (line_note_head, n_basic_blocks * sizeof (rtx));
4473 /* Determine the line-number at the start of each basic block.
4474 This must be computed and saved now, because after a basic block's
4475 predecessor has been scheduled, it is impossible to accurately
4476 determine the correct line number for the first insn of the block. */
4478 for (b = 0; b < n_basic_blocks; b++)
4479 for (line = basic_block_head[b]; line; line = PREV_INSN (line))
4480 if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
4482 line_note_head[b] = line;
4487 bzero (insn_luid, max_uid * sizeof (int));
4488 bzero (insn_priority, max_uid * sizeof (int));
4489 bzero (insn_tick, max_uid * sizeof (int));
4490 bzero (insn_costs, max_uid * sizeof (short));
4491 bzero (insn_units, max_uid * sizeof (short));
4492 bzero (insn_blockage, max_uid * sizeof (unsigned int));
4493 bzero (insn_ref_count, max_uid * sizeof (int));
4495 /* Schedule each basic block, block by block. */
4497 if (NEXT_INSN (basic_block_end[n_basic_blocks-1]) == 0
4498 || (GET_CODE (basic_block_end[n_basic_blocks-1]) != NOTE
4499 && GET_CODE (basic_block_end[n_basic_blocks-1]) != CODE_LABEL))
4500 emit_note_after (NOTE_INSN_DELETED, basic_block_end[n_basic_blocks-1]);
4502 for (b = 0; b < n_basic_blocks; b++)
4509 for (insn = basic_block_head[b]; ; insn = next)
4514 /* Can't use `next_real_insn' because that
4515 might go across CODE_LABELS and short-out basic blocks. */
4516 next = NEXT_INSN (insn);
4517 if (GET_CODE (insn) != INSN)
4519 if (insn == basic_block_end[b])
4525 /* Don't split no-op move insns. These should silently disappear
4526 later in final. Splitting such insns would break the code
4527 that handles REG_NO_CONFLICT blocks. */
4528 set = single_set (insn);
4529 if (set && rtx_equal_p (SET_SRC (set), SET_DEST (set)))
4531 if (insn == basic_block_end[b])
4534 /* Nops get in the way while scheduling, so delete them now if
4535 register allocation has already been done. It is too risky
4536 to try to do this before register allocation, and there are
4537 unlikely to be very many nops then anyways. */
4538 if (reload_completed)
4540 PUT_CODE (insn, NOTE);
4541 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
4542 NOTE_SOURCE_FILE (insn) = 0;
4548 /* Split insns here to get max fine-grain parallelism. */
4549 prev = PREV_INSN (insn);
4550 if (reload_completed == 0)
4552 rtx last, first = PREV_INSN (insn);
4553 rtx notes = REG_NOTES (insn);
4555 last = try_split (PATTERN (insn), insn, 1);
4558 /* try_split returns the NOTE that INSN became. */
4559 first = NEXT_INSN (first);
4560 update_flow_info (notes, first, last, insn);
4562 PUT_CODE (insn, NOTE);
4563 NOTE_SOURCE_FILE (insn) = 0;
4564 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
4565 if (insn == basic_block_head[b])
4566 basic_block_head[b] = first;
4567 if (insn == basic_block_end[b])
4569 basic_block_end[b] = last;
4575 if (insn == basic_block_end[b])
4579 schedule_block (b, dump_file);
4586 /* Reposition the prologue and epilogue notes in case we moved the
4587 prologue/epilogue insns. */
4588 if (reload_completed)
4589 reposition_prologue_and_epilogue_notes (get_insns ());
4591 if (write_symbols != NO_DEBUG)
4594 rtx insn = get_insns ();
4595 int active_insn = 0;
4598 /* Walk the insns deleting redundant line-number notes. Many of these
4599 are already present. The remainder tend to occur at basic
4600 block boundaries. */
4601 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
4602 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
4604 /* If there are no active insns following, INSN is redundant. */
4605 if (active_insn == 0)
4608 NOTE_SOURCE_FILE (insn) = 0;
4609 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
4611 /* If the line number is unchanged, LINE is redundant. */
4613 && NOTE_LINE_NUMBER (line) == NOTE_LINE_NUMBER (insn)
4614 && NOTE_SOURCE_FILE (line) == NOTE_SOURCE_FILE (insn))
4617 NOTE_SOURCE_FILE (line) = 0;
4618 NOTE_LINE_NUMBER (line) = NOTE_INSN_DELETED;
4625 else if (! ((GET_CODE (insn) == NOTE
4626 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED)
4627 || (GET_CODE (insn) == INSN
4628 && (GET_CODE (PATTERN (insn)) == USE
4629 || GET_CODE (PATTERN (insn)) == CLOBBER))))
4632 if (dump_file && notes)
4633 fprintf (dump_file, ";; deleted %d line-number notes\n", notes);
4636 if (reload_completed == 0)
4639 for (regno = 0; regno < max_regno; regno++)
4640 if (sched_reg_live_length[regno])
4644 if (reg_live_length[regno] > sched_reg_live_length[regno])
4646 ";; register %d life shortened from %d to %d\n",
4647 regno, reg_live_length[regno],
4648 sched_reg_live_length[regno]);
4649 /* Negative values are special; don't overwrite the current
4650 reg_live_length value if it is negative. */
4651 else if (reg_live_length[regno] < sched_reg_live_length[regno]
4652 && reg_live_length[regno] >= 0)
4654 ";; register %d life extended from %d to %d\n",
4655 regno, reg_live_length[regno],
4656 sched_reg_live_length[regno]);
4658 if (reg_n_calls_crossed[regno]
4659 && ! sched_reg_n_calls_crossed[regno])
4661 ";; register %d no longer crosses calls\n", regno);
4662 else if (! reg_n_calls_crossed[regno]
4663 && sched_reg_n_calls_crossed[regno])
4665 ";; register %d now crosses calls\n", regno);
4667 /* Negative values are special; don't overwrite the current
4668 reg_live_length value if it is negative. */
4669 if (reg_live_length[regno] >= 0)
4670 reg_live_length[regno] = sched_reg_live_length[regno];
4671 reg_n_calls_crossed[regno] = sched_reg_n_calls_crossed[regno];
4675 #endif /* INSN_SCHEDULING */