1 /* Instruction scheduling pass.
2 Copyright (C) 1992, 93-98, 1999 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, 59 Temple Place - Suite 330,
21 Boston, MA 02111-1307, USA. */
23 /* Instruction scheduling pass.
25 This pass implements list scheduling within basic blocks. It is
26 run after flow analysis, but before register allocation. The
27 scheduler works as follows:
29 We compute insn priorities based on data dependencies. Flow
30 analysis only creates a fraction of the data-dependencies we must
31 observe: namely, only those dependencies which the combiner can be
32 expected to use. For this pass, we must therefore create the
33 remaining dependencies we need to observe: register dependencies,
34 memory dependencies, dependencies to keep function calls in order,
35 and the dependence between a conditional branch and the setting of
36 condition codes are all dealt with here.
38 The scheduler first traverses the data flow graph, starting with
39 the last instruction, and proceeding to the first, assigning
40 values to insn_priority as it goes. This sorts the instructions
41 topologically by data dependence.
43 Once priorities have been established, we order the insns using
44 list scheduling. This works as follows: starting with a list of
45 all the ready insns, and sorted according to priority number, we
46 schedule the insn from the end of the list by placing its
47 predecessors in the list according to their priority order. We
48 consider this insn scheduled by setting the pointer to the "end" of
49 the list to point to the previous insn. When an insn has no
50 predecessors, we either queue it until sufficient time has elapsed
51 or add it to the ready list. As the instructions are scheduled or
52 when stalls are introduced, the queue advances and dumps insns into
53 the ready list. When all insns down to the lowest priority have
54 been scheduled, the critical path of the basic block has been made
55 as short as possible. The remaining insns are then scheduled in
58 Function unit conflicts are resolved during reverse list scheduling
59 by tracking the time when each insn is committed to the schedule
60 and from that, the time the function units it uses must be free.
61 As insns on the ready list are considered for scheduling, those
62 that would result in a blockage of the already committed insns are
63 queued until no blockage will result. Among the remaining insns on
64 the ready list to be considered, the first one with the largest
65 potential for causing a subsequent blockage is chosen.
67 The following list shows the order in which we want to break ties
68 among insns in the ready list:
70 1. choose insn with lowest conflict cost, ties broken by
71 2. choose insn with the longest path to end of bb, ties broken by
72 3. choose insn that kills the most registers, ties broken by
73 4. choose insn that conflicts with the most ready insns, or finally
74 5. choose insn with lowest UID.
76 Memory references complicate matters. Only if we can be certain
77 that memory references are not part of the data dependency graph
78 (via true, anti, or output dependence), can we move operations past
79 memory references. To first approximation, reads can be done
80 independently, while writes introduce dependencies. Better
81 approximations will yield fewer dependencies.
83 Dependencies set up by memory references are treated in exactly the
84 same way as other dependencies, by using LOG_LINKS.
86 Having optimized the critical path, we may have also unduly
87 extended the lifetimes of some registers. If an operation requires
88 that constants be loaded into registers, it is certainly desirable
89 to load those constants as early as necessary, but no earlier.
90 I.e., it will not do to load up a bunch of registers at the
91 beginning of a basic block only to use them at the end, if they
92 could be loaded later, since this may result in excessive register
95 Note that since branches are never in basic blocks, but only end
96 basic blocks, this pass will not do any branch scheduling. But
97 that is ok, since we can use GNU's delayed branch scheduling
98 pass to take care of this case.
100 Also note that no further optimizations based on algebraic identities
101 are performed, so this pass would be a good one to perform instruction
102 splitting, such as breaking up a multiply instruction into shifts
103 and adds where that is profitable.
105 Given the memory aliasing analysis that this pass should perform,
106 it should be possible to remove redundant stores to memory, and to
107 load values from registers instead of hitting memory.
109 This pass must update information that subsequent passes expect to be
110 correct. Namely: reg_n_refs, reg_n_sets, reg_n_deaths,
111 reg_n_calls_crossed, and reg_live_length. Also, BLOCK_HEAD,
114 The information in the line number notes is carefully retained by
115 this pass. Notes that refer to the starting and ending of
116 exception regions are also carefully retained by this pass. All
117 other NOTE insns are grouped in their same relative order at the
118 beginning of basic blocks that have been scheduled. */
124 #include "basic-block.h"
126 #include "hard-reg-set.h"
128 #include "insn-config.h"
129 #include "insn-attr.h"
132 #ifndef INSN_SCHEDULING
134 schedule_insns (dump_file)
135 FILE *dump_file ATTRIBUTE_UNUSED;
138 #else /* INSN_SCHEDULING -- rest of file */
140 extern char *reg_known_equiv_p;
141 extern rtx *reg_known_value;
143 /* Arrays set up by scheduling for the same respective purposes as
144 similar-named arrays set up by flow analysis. We work with these
145 arrays during the scheduling pass so we can compare values against
148 Values of these arrays are copied at the end of this pass into the
149 arrays set up by flow analysis. */
150 static int *sched_reg_n_calls_crossed;
151 static int *sched_reg_live_length;
153 /* Element N is the next insn that sets (hard or pseudo) register
154 N within the current basic block; or zero, if there is no
155 such insn. Needed for new registers which may be introduced
156 by splitting insns. */
157 static rtx *reg_last_uses;
158 static rtx *reg_last_sets;
159 static regset reg_pending_sets;
160 static int reg_pending_sets_all;
162 /* Vector indexed by INSN_UID giving the original ordering of the insns. */
163 static int *insn_luid;
164 #define INSN_LUID(INSN) (insn_luid[INSN_UID (INSN)])
166 /* Vector indexed by INSN_UID giving each instruction a priority. */
167 static int *insn_priority;
168 #define INSN_PRIORITY(INSN) (insn_priority[INSN_UID (INSN)])
170 static short *insn_costs;
171 #define INSN_COST(INSN) insn_costs[INSN_UID (INSN)]
173 /* Vector indexed by INSN_UID giving an encoding of the function units
175 static short *insn_units;
176 #define INSN_UNIT(INSN) insn_units[INSN_UID (INSN)]
178 /* Vector indexed by INSN_UID giving an encoding of the blockage range
179 function. The unit and the range are encoded. */
180 static unsigned int *insn_blockage;
181 #define INSN_BLOCKAGE(INSN) insn_blockage[INSN_UID (INSN)]
183 #define BLOCKAGE_MASK ((1 << BLOCKAGE_BITS) - 1)
184 #define ENCODE_BLOCKAGE(U,R) \
185 ((((U) << UNIT_BITS) << BLOCKAGE_BITS \
186 | MIN_BLOCKAGE_COST (R)) << BLOCKAGE_BITS \
187 | MAX_BLOCKAGE_COST (R))
188 #define UNIT_BLOCKED(B) ((B) >> (2 * BLOCKAGE_BITS))
189 #define BLOCKAGE_RANGE(B) \
190 (((((B) >> BLOCKAGE_BITS) & BLOCKAGE_MASK) << (HOST_BITS_PER_INT / 2)) \
191 | ((B) & BLOCKAGE_MASK))
193 /* Encodings of the `<name>_unit_blockage_range' function. */
194 #define MIN_BLOCKAGE_COST(R) ((R) >> (HOST_BITS_PER_INT / 2))
195 #define MAX_BLOCKAGE_COST(R) ((R) & ((1 << (HOST_BITS_PER_INT / 2)) - 1))
197 #define DONE_PRIORITY -1
198 #define MAX_PRIORITY 0x7fffffff
199 #define TAIL_PRIORITY 0x7ffffffe
200 #define LAUNCH_PRIORITY 0x7f000001
201 #define DONE_PRIORITY_P(INSN) (INSN_PRIORITY (INSN) < 0)
202 #define LOW_PRIORITY_P(INSN) ((INSN_PRIORITY (INSN) & 0x7f000000) == 0)
204 /* Vector indexed by INSN_UID giving number of insns referring to this insn. */
205 static int *insn_ref_count;
206 #define INSN_REF_COUNT(INSN) (insn_ref_count[INSN_UID (INSN)])
208 /* Vector indexed by INSN_UID giving line-number note in effect for each
209 insn. For line-number notes, this indicates whether the note may be
211 static rtx *line_note;
212 #define LINE_NOTE(INSN) (line_note[INSN_UID (INSN)])
214 /* Vector indexed by basic block number giving the starting line-number
215 for each basic block. */
216 static rtx *line_note_head;
218 /* List of important notes we must keep around. This is a pointer to the
219 last element in the list. */
220 static rtx note_list;
222 /* Regsets telling whether a given register is live or dead before the last
223 scheduled insn. Must scan the instructions once before scheduling to
224 determine what registers are live or dead at the end of the block. */
225 static regset bb_dead_regs;
226 static regset bb_live_regs;
228 /* Regset telling whether a given register is live after the insn currently
229 being scheduled. Before processing an insn, this is equal to bb_live_regs
230 above. This is used so that we can find registers that are newly born/dead
231 after processing an insn. */
232 static regset old_live_regs;
234 /* The chain of REG_DEAD notes. REG_DEAD notes are removed from all insns
235 during the initial scan and reused later. If there are not exactly as
236 many REG_DEAD notes in the post scheduled code as there were in the
237 prescheduled code then we trigger an abort because this indicates a bug. */
238 static rtx dead_notes;
242 /* An instruction is ready to be scheduled when all insns following it
243 have already been scheduled. It is important to ensure that all
244 insns which use its result will not be executed until its result
245 has been computed. An insn is maintained in one of four structures:
247 (P) the "Pending" set of insns which cannot be scheduled until
248 their dependencies have been satisfied.
249 (Q) the "Queued" set of insns that can be scheduled when sufficient
251 (R) the "Ready" list of unscheduled, uncommitted insns.
252 (S) the "Scheduled" list of insns.
254 Initially, all insns are either "Pending" or "Ready" depending on
255 whether their dependencies are satisfied.
257 Insns move from the "Ready" list to the "Scheduled" list as they
258 are committed to the schedule. As this occurs, the insns in the
259 "Pending" list have their dependencies satisfied and move to either
260 the "Ready" list or the "Queued" set depending on whether
261 sufficient time has passed to make them ready. As time passes,
262 insns move from the "Queued" set to the "Ready" list. Insns may
263 move from the "Ready" list to the "Queued" set if they are blocked
264 due to a function unit conflict.
266 The "Pending" list (P) are the insns in the LOG_LINKS of the unscheduled
267 insns, i.e., those that are ready, queued, and pending.
268 The "Queued" set (Q) is implemented by the variable `insn_queue'.
269 The "Ready" list (R) is implemented by the variables `ready' and
271 The "Scheduled" list (S) is the new insn chain built by this pass.
273 The transition (R->S) is implemented in the scheduling loop in
274 `schedule_block' when the best insn to schedule is chosen.
275 The transition (R->Q) is implemented in `schedule_select' when an
276 insn is found to have a function unit conflict with the already
278 The transitions (P->R and P->Q) are implemented in `schedule_insn' as
279 insns move from the ready list to the scheduled list.
280 The transition (Q->R) is implemented at the top of the scheduling
281 loop in `schedule_block' as time passes or stalls are introduced. */
283 /* Implement a circular buffer to delay instructions until sufficient
284 time has passed. INSN_QUEUE_SIZE is a power of two larger than
285 MAX_BLOCKAGE and MAX_READY_COST computed by genattr.c. This is the
286 longest time an isnsn may be queued. */
287 static rtx insn_queue[INSN_QUEUE_SIZE];
288 static int q_ptr = 0;
289 static int q_size = 0;
290 #define NEXT_Q(X) (((X)+1) & (INSN_QUEUE_SIZE-1))
291 #define NEXT_Q_AFTER(X,C) (((X)+C) & (INSN_QUEUE_SIZE-1))
293 /* Vector indexed by INSN_UID giving the minimum clock tick at which
294 the insn becomes ready. This is used to note timing constraints for
295 insns in the pending list. */
296 static int *insn_tick;
297 #define INSN_TICK(INSN) (insn_tick[INSN_UID (INSN)])
299 /* Data structure for keeping track of register information
300 during that register's life. */
309 /* Forward declarations. */
310 static void add_dependence PROTO((rtx, rtx, enum reg_note));
311 static void remove_dependence PROTO((rtx, rtx));
312 static rtx find_insn_list PROTO((rtx, rtx));
313 static int insn_unit PROTO((rtx));
314 static unsigned int blockage_range PROTO((int, rtx));
315 static void clear_units PROTO((void));
316 static void prepare_unit PROTO((int));
317 static int actual_hazard_this_instance PROTO((int, int, rtx, int, int));
318 static void schedule_unit PROTO((int, rtx, int));
319 static int actual_hazard PROTO((int, rtx, int, int));
320 static int potential_hazard PROTO((int, rtx, int));
321 static int insn_cost PROTO((rtx, rtx, rtx));
322 static int priority PROTO((rtx));
323 static void free_pending_lists PROTO((void));
324 static void add_insn_mem_dependence PROTO((rtx *, rtx *, rtx, rtx));
325 static void flush_pending_lists PROTO((rtx, int));
326 static void sched_analyze_1 PROTO((rtx, rtx));
327 static void sched_analyze_2 PROTO((rtx, rtx));
328 static void sched_analyze_insn PROTO((rtx, rtx, rtx));
329 static int sched_analyze PROTO((rtx, rtx));
330 static void sched_note_set PROTO((rtx, int));
331 static int rank_for_schedule PROTO((const GENERIC_PTR, const GENERIC_PTR));
332 static void swap_sort PROTO((rtx *, int));
333 static void queue_insn PROTO((rtx, int));
334 static int birthing_insn_p PROTO((rtx));
335 static void adjust_priority PROTO((rtx));
336 static int schedule_insn PROTO((rtx, rtx *, int, int));
337 static int schedule_select PROTO((rtx *, int, int, FILE *));
338 static void create_reg_dead_note PROTO((rtx, rtx));
339 static void attach_deaths PROTO((rtx, rtx, int));
340 static void attach_deaths_insn PROTO((rtx));
341 static rtx unlink_notes PROTO((rtx, rtx));
342 static int new_sometimes_live PROTO((struct sometimes *, int, int));
343 static void finish_sometimes_live PROTO((struct sometimes *, int));
344 static rtx reemit_notes PROTO((rtx, rtx));
345 static void schedule_block PROTO((int, FILE *));
346 static void split_hard_reg_notes PROTO((rtx, rtx, rtx));
347 static void new_insn_dead_notes PROTO((rtx, rtx, rtx, rtx));
348 static void update_n_sets PROTO((rtx, int));
350 /* Main entry point of this file. */
351 void schedule_insns PROTO((FILE *));
353 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
355 /* Helper functions for instruction scheduling. */
357 /* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the
358 LOG_LINKS of INSN, if not already there. DEP_TYPE indicates the type
359 of dependence that this link represents. */
362 add_dependence (insn, elem, dep_type)
365 enum reg_note dep_type;
369 /* Don't depend an insn on itself. */
373 /* If elem is part of a sequence that must be scheduled together, then
374 make the dependence point to the last insn of the sequence.
375 When HAVE_cc0, it is possible for NOTEs to exist between users and
376 setters of the condition codes, so we must skip past notes here.
377 Otherwise, NOTEs are impossible here. */
379 next = NEXT_INSN (elem);
382 while (next && GET_CODE (next) == NOTE)
383 next = NEXT_INSN (next);
386 if (next && SCHED_GROUP_P (next)
387 && GET_CODE (next) != CODE_LABEL)
389 /* Notes will never intervene here though, so don't bother checking
391 /* We must reject CODE_LABELs, so that we don't get confused by one
392 that has LABEL_PRESERVE_P set, which is represented by the same
393 bit in the rtl as SCHED_GROUP_P. A CODE_LABEL can never be
395 while (NEXT_INSN (next) && SCHED_GROUP_P (NEXT_INSN (next))
396 && GET_CODE (NEXT_INSN (next)) != CODE_LABEL)
397 next = NEXT_INSN (next);
399 /* Again, don't depend an insn on itself. */
403 /* Make the dependence to NEXT, the last insn of the group, instead
404 of the original ELEM. */
408 /* Check that we don't already have this dependence. */
409 for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
410 if (XEXP (link, 0) == elem)
412 /* If this is a more restrictive type of dependence than the existing
413 one, then change the existing dependence to this type. */
414 if ((int) dep_type < (int) REG_NOTE_KIND (link))
415 PUT_REG_NOTE_KIND (link, dep_type);
418 /* Might want to check one level of transitivity to save conses. */
420 link = rtx_alloc (INSN_LIST);
421 /* Insn dependency, not data dependency. */
422 PUT_REG_NOTE_KIND (link, dep_type);
423 XEXP (link, 0) = elem;
424 XEXP (link, 1) = LOG_LINKS (insn);
425 LOG_LINKS (insn) = link;
428 /* Remove ELEM wrapped in an INSN_LIST from the LOG_LINKS
429 of INSN. Abort if not found. */
432 remove_dependence (insn, elem)
439 for (prev = 0, link = LOG_LINKS (insn); link; link = XEXP (link, 1))
441 if (XEXP (link, 0) == elem)
443 RTX_INTEGRATED_P (link) = 1;
445 XEXP (prev, 1) = XEXP (link, 1);
447 LOG_LINKS (insn) = XEXP (link, 1);
463 /* Computation of memory dependencies. */
465 /* The *_insns and *_mems are paired lists. Each pending memory operation
466 will have a pointer to the MEM rtx on one list and a pointer to the
467 containing insn on the other list in the same place in the list. */
469 /* We can't use add_dependence like the old code did, because a single insn
470 may have multiple memory accesses, and hence needs to be on the list
471 once for each memory access. Add_dependence won't let you add an insn
472 to a list more than once. */
474 /* An INSN_LIST containing all insns with pending read operations. */
475 static rtx pending_read_insns;
477 /* An EXPR_LIST containing all MEM rtx's which are pending reads. */
478 static rtx pending_read_mems;
480 /* An INSN_LIST containing all insns with pending write operations. */
481 static rtx pending_write_insns;
483 /* An EXPR_LIST containing all MEM rtx's which are pending writes. */
484 static rtx pending_write_mems;
486 /* Indicates the combined length of the two pending lists. We must prevent
487 these lists from ever growing too large since the number of dependencies
488 produced is at least O(N*N), and execution time is at least O(4*N*N), as
489 a function of the length of these pending lists. */
491 static int pending_lists_length;
493 /* An INSN_LIST containing all INSN_LISTs allocated but currently unused. */
495 static rtx unused_insn_list;
497 /* An EXPR_LIST containing all EXPR_LISTs allocated but currently unused. */
499 static rtx unused_expr_list;
501 /* The last insn upon which all memory references must depend.
502 This is an insn which flushed the pending lists, creating a dependency
503 between it and all previously pending memory references. This creates
504 a barrier (or a checkpoint) which no memory reference is allowed to cross.
506 This includes all non constant CALL_INSNs. When we do interprocedural
507 alias analysis, this restriction can be relaxed.
508 This may also be an INSN that writes memory if the pending lists grow
511 static rtx last_pending_memory_flush;
513 /* The last function call we have seen. All hard regs, and, of course,
514 the last function call, must depend on this. */
516 static rtx last_function_call;
518 /* The LOG_LINKS field of this is a list of insns which use a pseudo register
519 that does not already cross a call. We create dependencies between each
520 of those insn and the next call insn, to ensure that they won't cross a call
521 after scheduling is done. */
523 static rtx sched_before_next_call;
525 /* Pointer to the last instruction scheduled. Used by rank_for_schedule,
526 so that insns independent of the last scheduled insn will be preferred
527 over dependent instructions. */
529 static rtx last_scheduled_insn;
531 /* Process an insn's memory dependencies. There are four kinds of
534 (0) read dependence: read follows read
535 (1) true dependence: read follows write
536 (2) anti dependence: write follows read
537 (3) output dependence: write follows write
539 We are careful to build only dependencies which actually exist, and
540 use transitivity to avoid building too many links. */
542 /* Return the INSN_LIST containing INSN in LIST, or NULL
543 if LIST does not contain INSN. */
546 find_insn_list (insn, list)
552 if (XEXP (list, 0) == insn)
554 list = XEXP (list, 1);
559 /* Compute the function units used by INSN. This caches the value
560 returned by function_units_used. A function unit is encoded as the
561 unit number if the value is non-negative and the compliment of a
562 mask if the value is negative. A function unit index is the
563 non-negative encoding. */
569 register int unit = INSN_UNIT (insn);
573 recog_memoized (insn);
575 /* A USE insn, or something else we don't need to understand.
576 We can't pass these directly to function_units_used because it will
577 trigger a fatal error for unrecognizable insns. */
578 if (INSN_CODE (insn) < 0)
582 unit = function_units_used (insn);
583 /* Increment non-negative values so we can cache zero. */
584 if (unit >= 0) unit++;
586 /* We only cache 16 bits of the result, so if the value is out of
587 range, don't cache it. */
588 if (FUNCTION_UNITS_SIZE < HOST_BITS_PER_SHORT
590 || (unit & ~((1 << (HOST_BITS_PER_SHORT - 1)) - 1)) == 0)
591 INSN_UNIT (insn) = unit;
593 return (unit > 0 ? unit - 1 : unit);
596 /* Compute the blockage range for executing INSN on UNIT. This caches
597 the value returned by the blockage_range_function for the unit.
598 These values are encoded in an int where the upper half gives the
599 minimum value and the lower half gives the maximum value. */
601 __inline static unsigned int
602 blockage_range (unit, insn)
606 unsigned int blockage = INSN_BLOCKAGE (insn);
609 if ((int) UNIT_BLOCKED (blockage) != unit + 1)
611 range = function_units[unit].blockage_range_function (insn);
612 /* We only cache the blockage range for one unit and then only if
614 if (HOST_BITS_PER_INT >= UNIT_BITS + 2 * BLOCKAGE_BITS)
615 INSN_BLOCKAGE (insn) = ENCODE_BLOCKAGE (unit + 1, range);
618 range = BLOCKAGE_RANGE (blockage);
623 /* A vector indexed by function unit instance giving the last insn to use
624 the unit. The value of the function unit instance index for unit U
625 instance I is (U + I * FUNCTION_UNITS_SIZE). */
626 static rtx unit_last_insn[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY];
628 /* A vector indexed by function unit instance giving the minimum time when
629 the unit will unblock based on the maximum blockage cost. */
630 static int unit_tick[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY];
632 /* A vector indexed by function unit number giving the number of insns
633 that remain to use the unit. */
634 static int unit_n_insns[FUNCTION_UNITS_SIZE];
636 /* Reset the function unit state to the null state. */
641 bzero ((char *) unit_last_insn, sizeof (unit_last_insn));
642 bzero ((char *) unit_tick, sizeof (unit_tick));
643 bzero ((char *) unit_n_insns, sizeof (unit_n_insns));
646 /* Record an insn as one that will use the units encoded by UNIT. */
655 unit_n_insns[unit]++;
657 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
662 /* Return the actual hazard cost of executing INSN on the unit UNIT,
663 instance INSTANCE at time CLOCK if the previous actual hazard cost
667 actual_hazard_this_instance (unit, instance, insn, clock, cost)
668 int unit, instance, clock, cost;
671 int tick = unit_tick[instance];
673 if (tick - clock > cost)
675 /* The scheduler is operating in reverse, so INSN is the executing
676 insn and the unit's last insn is the candidate insn. We want a
677 more exact measure of the blockage if we execute INSN at CLOCK
678 given when we committed the execution of the unit's last insn.
680 The blockage value is given by either the unit's max blockage
681 constant, blockage range function, or blockage function. Use
682 the most exact form for the given unit. */
684 if (function_units[unit].blockage_range_function)
686 if (function_units[unit].blockage_function)
687 tick += (function_units[unit].blockage_function
688 (insn, unit_last_insn[instance])
689 - function_units[unit].max_blockage);
691 tick += ((int) MAX_BLOCKAGE_COST (blockage_range (unit, insn))
692 - function_units[unit].max_blockage);
694 if (tick - clock > cost)
700 /* Record INSN as having begun execution on the units encoded by UNIT at
704 schedule_unit (unit, insn, clock)
713 #if MAX_MULTIPLICITY > 1
714 /* Find the first free instance of the function unit and use that
715 one. We assume that one is free. */
716 for (i = function_units[unit].multiplicity - 1; i > 0; i--)
718 if (! actual_hazard_this_instance (unit, instance, insn, clock, 0))
720 instance += FUNCTION_UNITS_SIZE;
723 unit_last_insn[instance] = insn;
724 unit_tick[instance] = (clock + function_units[unit].max_blockage);
727 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
729 schedule_unit (i, insn, clock);
732 /* Return the actual hazard cost of executing INSN on the units encoded by
733 UNIT at time CLOCK if the previous actual hazard cost was COST. */
736 actual_hazard (unit, insn, clock, cost)
737 int unit, clock, cost;
744 /* Find the instance of the function unit with the minimum hazard. */
746 int best_cost = actual_hazard_this_instance (unit, instance, insn,
748 #if MAX_MULTIPLICITY > 1
751 if (best_cost > cost)
753 for (i = function_units[unit].multiplicity - 1; i > 0; i--)
755 instance += FUNCTION_UNITS_SIZE;
756 this_cost = actual_hazard_this_instance (unit, instance, insn,
758 if (this_cost < best_cost)
760 best_cost = this_cost;
761 if (this_cost <= cost)
767 cost = MAX (cost, best_cost);
770 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
772 cost = actual_hazard (i, insn, clock, cost);
777 /* Return the potential hazard cost of executing an instruction on the
778 units encoded by UNIT if the previous potential hazard cost was COST.
779 An insn with a large blockage time is chosen in preference to one
780 with a smaller time; an insn that uses a unit that is more likely
781 to be used is chosen in preference to one with a unit that is less
782 used. We are trying to minimize a subsequent actual hazard. */
785 potential_hazard (unit, insn, cost)
790 unsigned int minb, maxb;
794 minb = maxb = function_units[unit].max_blockage;
797 if (function_units[unit].blockage_range_function)
799 maxb = minb = blockage_range (unit, insn);
800 maxb = MAX_BLOCKAGE_COST (maxb);
801 minb = MIN_BLOCKAGE_COST (minb);
806 /* Make the number of instructions left dominate. Make the
807 minimum delay dominate the maximum delay. If all these
808 are the same, use the unit number to add an arbitrary
809 ordering. Other terms can be added. */
810 ncost = minb * 0x40 + maxb;
811 ncost *= (unit_n_insns[unit] - 1) * 0x1000 + unit;
818 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
820 cost = potential_hazard (i, insn, cost);
825 /* Compute cost of executing INSN given the dependence LINK on the insn USED.
826 This is the number of virtual cycles taken between instruction issue and
827 instruction results. */
830 insn_cost (insn, link, used)
831 rtx insn, link, used;
833 register int cost = INSN_COST (insn);
837 recog_memoized (insn);
839 /* A USE insn, or something else we don't need to understand.
840 We can't pass these directly to result_ready_cost because it will
841 trigger a fatal error for unrecognizable insns. */
842 if (INSN_CODE (insn) < 0)
844 INSN_COST (insn) = 1;
849 cost = result_ready_cost (insn);
854 INSN_COST (insn) = cost;
858 /* A USE insn should never require the value used to be computed. This
859 allows the computation of a function's result and parameter values to
860 overlap the return and call. */
861 recog_memoized (used);
862 if (INSN_CODE (used) < 0)
863 LINK_COST_FREE (link) = 1;
865 /* If some dependencies vary the cost, compute the adjustment. Most
866 commonly, the adjustment is complete: either the cost is ignored
867 (in the case of an output- or anti-dependence), or the cost is
868 unchanged. These values are cached in the link as LINK_COST_FREE
869 and LINK_COST_ZERO. */
871 if (LINK_COST_FREE (link))
874 else if (! LINK_COST_ZERO (link))
878 ADJUST_COST (used, link, insn, ncost);
880 LINK_COST_FREE (link) = ncost = 1;
882 LINK_COST_ZERO (link) = 1;
889 /* Compute the priority number for INSN. */
895 if (insn && GET_RTX_CLASS (GET_CODE (insn)) == 'i')
899 int this_priority = INSN_PRIORITY (insn);
902 if (this_priority > 0)
903 return this_priority;
907 /* Nonzero if these insns must be scheduled together. */
908 if (SCHED_GROUP_P (insn))
911 while (SCHED_GROUP_P (prev))
913 prev = PREV_INSN (prev);
914 INSN_REF_COUNT (prev) += 1;
918 for (prev = LOG_LINKS (insn); prev; prev = XEXP (prev, 1))
920 rtx x = XEXP (prev, 0);
922 /* If this was a duplicate of a dependence we already deleted,
924 if (RTX_INTEGRATED_P (prev))
927 /* A dependence pointing to a note or deleted insn is always
928 obsolete, because sched_analyze_insn will have created any
929 necessary new dependences which replace it. Notes and deleted
930 insns can be created when instructions are deleted by insn
931 splitting, or by register allocation. */
932 if (GET_CODE (x) == NOTE || INSN_DELETED_P (x))
934 remove_dependence (insn, x);
938 /* Clear the link cost adjustment bits. */
939 LINK_COST_FREE (prev) = 0;
941 LINK_COST_ZERO (prev) = 0;
944 /* This priority calculation was chosen because it results in the
945 least instruction movement, and does not hurt the performance
946 of the resulting code compared to the old algorithm.
947 This makes the sched algorithm more stable, which results
948 in better code, because there is less register pressure,
949 cross jumping is more likely to work, and debugging is easier.
951 When all instructions have a latency of 1, there is no need to
952 move any instructions. Subtracting one here ensures that in such
953 cases all instructions will end up with a priority of one, and
954 hence no scheduling will be done.
956 The original code did not subtract the one, and added the
957 insn_cost of the current instruction to its priority (e.g.
958 move the insn_cost call down to the end). */
960 prev_priority = priority (x) + insn_cost (x, prev, insn) - 1;
962 if (prev_priority > max_priority)
963 max_priority = prev_priority;
964 INSN_REF_COUNT (x) += 1;
967 prepare_unit (insn_unit (insn));
968 INSN_PRIORITY (insn) = max_priority;
969 return INSN_PRIORITY (insn);
974 /* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
975 them to the unused_*_list variables, so that they can be reused. */
978 free_pending_lists ()
980 register rtx link, prev_link;
982 if (pending_read_insns)
984 prev_link = pending_read_insns;
985 link = XEXP (prev_link, 1);
990 link = XEXP (link, 1);
993 XEXP (prev_link, 1) = unused_insn_list;
994 unused_insn_list = pending_read_insns;
995 pending_read_insns = 0;
998 if (pending_write_insns)
1000 prev_link = pending_write_insns;
1001 link = XEXP (prev_link, 1);
1006 link = XEXP (link, 1);
1009 XEXP (prev_link, 1) = unused_insn_list;
1010 unused_insn_list = pending_write_insns;
1011 pending_write_insns = 0;
1014 if (pending_read_mems)
1016 prev_link = pending_read_mems;
1017 link = XEXP (prev_link, 1);
1022 link = XEXP (link, 1);
1025 XEXP (prev_link, 1) = unused_expr_list;
1026 unused_expr_list = pending_read_mems;
1027 pending_read_mems = 0;
1030 if (pending_write_mems)
1032 prev_link = pending_write_mems;
1033 link = XEXP (prev_link, 1);
1038 link = XEXP (link, 1);
1041 XEXP (prev_link, 1) = unused_expr_list;
1042 unused_expr_list = pending_write_mems;
1043 pending_write_mems = 0;
1047 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
1048 The MEM is a memory reference contained within INSN, which we are saving
1049 so that we can do memory aliasing on it. */
1052 add_insn_mem_dependence (insn_list, mem_list, insn, mem)
1053 rtx *insn_list, *mem_list, insn, mem;
1057 if (unused_insn_list)
1059 link = unused_insn_list;
1060 unused_insn_list = XEXP (link, 1);
1063 link = rtx_alloc (INSN_LIST);
1064 XEXP (link, 0) = insn;
1065 XEXP (link, 1) = *insn_list;
1068 if (unused_expr_list)
1070 link = unused_expr_list;
1071 unused_expr_list = XEXP (link, 1);
1074 link = rtx_alloc (EXPR_LIST);
1075 XEXP (link, 0) = mem;
1076 XEXP (link, 1) = *mem_list;
1079 pending_lists_length++;
1082 /* Make a dependency between every memory reference on the pending lists
1083 and INSN, thus flushing the pending lists. If ONLY_WRITE, don't flush
1087 flush_pending_lists (insn, only_write)
1093 while (pending_read_insns && ! only_write)
1095 add_dependence (insn, XEXP (pending_read_insns, 0), REG_DEP_ANTI);
1097 link = pending_read_insns;
1098 pending_read_insns = XEXP (pending_read_insns, 1);
1099 XEXP (link, 1) = unused_insn_list;
1100 unused_insn_list = link;
1102 link = pending_read_mems;
1103 pending_read_mems = XEXP (pending_read_mems, 1);
1104 XEXP (link, 1) = unused_expr_list;
1105 unused_expr_list = link;
1107 while (pending_write_insns)
1109 add_dependence (insn, XEXP (pending_write_insns, 0), REG_DEP_ANTI);
1111 link = pending_write_insns;
1112 pending_write_insns = XEXP (pending_write_insns, 1);
1113 XEXP (link, 1) = unused_insn_list;
1114 unused_insn_list = link;
1116 link = pending_write_mems;
1117 pending_write_mems = XEXP (pending_write_mems, 1);
1118 XEXP (link, 1) = unused_expr_list;
1119 unused_expr_list = link;
1121 pending_lists_length = 0;
1123 if (last_pending_memory_flush)
1124 add_dependence (insn, last_pending_memory_flush, REG_DEP_ANTI);
1126 last_pending_memory_flush = insn;
1129 /* Analyze a single SET or CLOBBER rtx, X, creating all dependencies generated
1130 by the write to the destination of X, and reads of everything mentioned. */
1133 sched_analyze_1 (x, insn)
1138 register rtx dest = SET_DEST (x);
1143 while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
1144 || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
1146 if (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
1148 /* The second and third arguments are values read by this insn. */
1149 sched_analyze_2 (XEXP (dest, 1), insn);
1150 sched_analyze_2 (XEXP (dest, 2), insn);
1152 dest = SUBREG_REG (dest);
1155 if (GET_CODE (dest) == REG)
1159 regno = REGNO (dest);
1161 /* A hard reg in a wide mode may really be multiple registers.
1162 If so, mark all of them just like the first. */
1163 if (regno < FIRST_PSEUDO_REGISTER)
1165 i = HARD_REGNO_NREGS (regno, GET_MODE (dest));
1170 for (u = reg_last_uses[regno+i]; u; u = XEXP (u, 1))
1171 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
1172 reg_last_uses[regno + i] = 0;
1173 if (reg_last_sets[regno + i])
1174 add_dependence (insn, reg_last_sets[regno + i],
1176 SET_REGNO_REG_SET (reg_pending_sets, regno + i);
1177 if ((call_used_regs[i] || global_regs[i])
1178 && last_function_call)
1179 /* Function calls clobber all call_used regs. */
1180 add_dependence (insn, last_function_call, REG_DEP_ANTI);
1187 for (u = reg_last_uses[regno]; u; u = XEXP (u, 1))
1188 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
1189 reg_last_uses[regno] = 0;
1190 if (reg_last_sets[regno])
1191 add_dependence (insn, reg_last_sets[regno], REG_DEP_OUTPUT);
1192 SET_REGNO_REG_SET (reg_pending_sets, regno);
1194 /* Pseudos that are REG_EQUIV to something may be replaced
1195 by that during reloading. We need only add dependencies for
1196 the address in the REG_EQUIV note. */
1197 if (! reload_completed
1198 && reg_known_equiv_p[regno]
1199 && GET_CODE (reg_known_value[regno]) == MEM)
1200 sched_analyze_2 (XEXP (reg_known_value[regno], 0), insn);
1202 /* Don't let it cross a call after scheduling if it doesn't
1203 already cross one. */
1204 if (REG_N_CALLS_CROSSED (regno) == 0 && last_function_call)
1205 add_dependence (insn, last_function_call, REG_DEP_ANTI);
1208 else if (GET_CODE (dest) == MEM)
1210 /* Writing memory. */
1212 if (pending_lists_length > 32)
1214 /* Flush all pending reads and writes to prevent the pending lists
1215 from getting any larger. Insn scheduling runs too slowly when
1216 these lists get long. The number 32 was chosen because it
1217 seems like a reasonable number. When compiling GCC with itself,
1218 this flush occurs 8 times for sparc, and 10 times for m88k using
1220 flush_pending_lists (insn, 0);
1224 rtx pending, pending_mem;
1226 pending = pending_read_insns;
1227 pending_mem = pending_read_mems;
1230 /* If a dependency already exists, don't create a new one. */
1231 if (! find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
1232 if (anti_dependence (XEXP (pending_mem, 0), dest))
1233 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
1235 pending = XEXP (pending, 1);
1236 pending_mem = XEXP (pending_mem, 1);
1239 pending = pending_write_insns;
1240 pending_mem = pending_write_mems;
1243 /* If a dependency already exists, don't create a new one. */
1244 if (! find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
1245 if (output_dependence (XEXP (pending_mem, 0), dest))
1246 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
1248 pending = XEXP (pending, 1);
1249 pending_mem = XEXP (pending_mem, 1);
1252 if (last_pending_memory_flush)
1253 add_dependence (insn, last_pending_memory_flush, REG_DEP_ANTI);
1255 add_insn_mem_dependence (&pending_write_insns, &pending_write_mems,
1258 sched_analyze_2 (XEXP (dest, 0), insn);
1261 /* Analyze reads. */
1262 if (GET_CODE (x) == SET)
1263 sched_analyze_2 (SET_SRC (x), insn);
1266 /* Analyze the uses of memory and registers in rtx X in INSN. */
1269 sched_analyze_2 (x, insn)
1275 register enum rtx_code code;
1281 code = GET_CODE (x);
1290 /* Ignore constants. Note that we must handle CONST_DOUBLE here
1291 because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but
1292 this does not mean that this insn is using cc0. */
1300 /* User of CC0 depends on immediately preceding insn. */
1301 SCHED_GROUP_P (insn) = 1;
1303 /* There may be a note before this insn now, but all notes will
1304 be removed before we actually try to schedule the insns, so
1305 it won't cause a problem later. We must avoid it here though. */
1306 prev = prev_nonnote_insn (insn);
1308 /* Make a copy of all dependencies on the immediately previous insn,
1309 and add to this insn. This is so that all the dependencies will
1310 apply to the group. Remove an explicit dependence on this insn
1311 as SCHED_GROUP_P now represents it. */
1313 if (find_insn_list (prev, LOG_LINKS (insn)))
1314 remove_dependence (insn, prev);
1316 for (link = LOG_LINKS (prev); link; link = XEXP (link, 1))
1317 add_dependence (insn, XEXP (link, 0), REG_NOTE_KIND (link));
1325 int regno = REGNO (x);
1326 if (regno < FIRST_PSEUDO_REGISTER)
1330 i = HARD_REGNO_NREGS (regno, GET_MODE (x));
1333 reg_last_uses[regno + i]
1334 = gen_rtx_INSN_LIST (VOIDmode,
1335 insn, reg_last_uses[regno + i]);
1336 if (reg_last_sets[regno + i])
1337 add_dependence (insn, reg_last_sets[regno + i], 0);
1338 if ((call_used_regs[regno + i] || global_regs[regno + i])
1339 && last_function_call)
1340 /* Function calls clobber all call_used regs. */
1341 add_dependence (insn, last_function_call, REG_DEP_ANTI);
1346 reg_last_uses[regno]
1347 = gen_rtx_INSN_LIST (VOIDmode, insn, reg_last_uses[regno]);
1348 if (reg_last_sets[regno])
1349 add_dependence (insn, reg_last_sets[regno], 0);
1351 /* Pseudos that are REG_EQUIV to something may be replaced
1352 by that during reloading. We need only add dependencies for
1353 the address in the REG_EQUIV note. */
1354 if (! reload_completed
1355 && reg_known_equiv_p[regno]
1356 && GET_CODE (reg_known_value[regno]) == MEM)
1357 sched_analyze_2 (XEXP (reg_known_value[regno], 0), insn);
1359 /* If the register does not already cross any calls, then add this
1360 insn to the sched_before_next_call list so that it will still
1361 not cross calls after scheduling. */
1362 if (REG_N_CALLS_CROSSED (regno) == 0)
1363 add_dependence (sched_before_next_call, insn, REG_DEP_ANTI);
1370 /* Reading memory. */
1372 rtx pending, pending_mem;
1374 pending = pending_read_insns;
1375 pending_mem = pending_read_mems;
1378 /* If a dependency already exists, don't create a new one. */
1379 if (! find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
1380 if (read_dependence (XEXP (pending_mem, 0), x))
1381 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
1383 pending = XEXP (pending, 1);
1384 pending_mem = XEXP (pending_mem, 1);
1387 pending = pending_write_insns;
1388 pending_mem = pending_write_mems;
1391 /* If a dependency already exists, don't create a new one. */
1392 if (! find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
1393 if (true_dependence (XEXP (pending_mem, 0), VOIDmode,
1395 add_dependence (insn, XEXP (pending, 0), 0);
1397 pending = XEXP (pending, 1);
1398 pending_mem = XEXP (pending_mem, 1);
1400 if (last_pending_memory_flush)
1401 add_dependence (insn, last_pending_memory_flush, REG_DEP_ANTI);
1403 /* Always add these dependencies to pending_reads, since
1404 this insn may be followed by a write. */
1405 add_insn_mem_dependence (&pending_read_insns, &pending_read_mems,
1408 /* Take advantage of tail recursion here. */
1409 sched_analyze_2 (XEXP (x, 0), insn);
1415 case UNSPEC_VOLATILE:
1420 /* Traditional and volatile asm instructions must be considered to use
1421 and clobber all hard registers, all pseudo-registers and all of
1422 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
1424 Consider for instance a volatile asm that changes the fpu rounding
1425 mode. An insn should not be moved across this even if it only uses
1426 pseudo-regs because it might give an incorrectly rounded result. */
1427 if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
1429 int max_reg = max_reg_num ();
1430 for (i = 0; i < max_reg; i++)
1432 for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
1433 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
1434 reg_last_uses[i] = 0;
1435 if (reg_last_sets[i])
1436 add_dependence (insn, reg_last_sets[i], 0);
1438 reg_pending_sets_all = 1;
1440 flush_pending_lists (insn, 0);
1443 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
1444 We can not just fall through here since then we would be confused
1445 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
1446 traditional asms unlike their normal usage. */
1448 if (code == ASM_OPERANDS)
1450 for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
1451 sched_analyze_2 (ASM_OPERANDS_INPUT (x, j), insn);
1461 /* These both read and modify the result. We must handle them as writes
1462 to get proper dependencies for following instructions. We must handle
1463 them as reads to get proper dependencies from this to previous
1464 instructions. Thus we need to pass them to both sched_analyze_1
1465 and sched_analyze_2. We must call sched_analyze_2 first in order
1466 to get the proper antecedent for the read. */
1467 sched_analyze_2 (XEXP (x, 0), insn);
1468 sched_analyze_1 (x, insn);
1475 /* Other cases: walk the insn. */
1476 fmt = GET_RTX_FORMAT (code);
1477 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1480 sched_analyze_2 (XEXP (x, i), insn);
1481 else if (fmt[i] == 'E')
1482 for (j = 0; j < XVECLEN (x, i); j++)
1483 sched_analyze_2 (XVECEXP (x, i, j), insn);
1487 /* Analyze an INSN with pattern X to find all dependencies. */
1490 sched_analyze_insn (x, insn, loop_notes)
1494 register RTX_CODE code = GET_CODE (x);
1496 int maxreg = max_reg_num ();
1499 if (code == SET || code == CLOBBER)
1500 sched_analyze_1 (x, insn);
1501 else if (code == PARALLEL)
1504 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
1506 code = GET_CODE (XVECEXP (x, 0, i));
1507 if (code == SET || code == CLOBBER)
1508 sched_analyze_1 (XVECEXP (x, 0, i), insn);
1510 sched_analyze_2 (XVECEXP (x, 0, i), insn);
1514 sched_analyze_2 (x, insn);
1516 /* Mark registers CLOBBERED or used by called function. */
1517 if (GET_CODE (insn) == CALL_INSN)
1518 for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
1520 if (GET_CODE (XEXP (link, 0)) == CLOBBER)
1521 sched_analyze_1 (XEXP (link, 0), insn);
1523 sched_analyze_2 (XEXP (link, 0), insn);
1526 /* If there is a {LOOP,EHREGION}_{BEG,END} note in the middle of a basic block, then
1527 we must be sure that no instructions are scheduled across it.
1528 Otherwise, the reg_n_refs info (which depends on loop_depth) would
1529 become incorrect. */
1533 int max_reg = max_reg_num ();
1536 for (i = 0; i < max_reg; i++)
1539 for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
1540 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
1541 reg_last_uses[i] = 0;
1542 if (reg_last_sets[i])
1543 add_dependence (insn, reg_last_sets[i], 0);
1545 reg_pending_sets_all = 1;
1547 flush_pending_lists (insn, 0);
1550 while (XEXP (link, 1))
1551 link = XEXP (link, 1);
1552 XEXP (link, 1) = REG_NOTES (insn);
1553 REG_NOTES (insn) = loop_notes;
1556 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i,
1558 reg_last_sets[i] = insn;
1560 CLEAR_REG_SET (reg_pending_sets);
1562 if (reg_pending_sets_all)
1564 for (i = 0; i < maxreg; i++)
1565 reg_last_sets[i] = insn;
1566 reg_pending_sets_all = 0;
1569 /* Handle function calls and function returns created by the epilogue
1571 if (GET_CODE (insn) == CALL_INSN || GET_CODE (insn) == JUMP_INSN)
1576 /* When scheduling instructions, we make sure calls don't lose their
1577 accompanying USE insns by depending them one on another in order.
1579 Also, we must do the same thing for returns created by the epilogue
1580 threading code. Note this code works only in this special case,
1581 because other passes make no guarantee that they will never emit
1582 an instruction between a USE and a RETURN. There is such a guarantee
1583 for USE instructions immediately before a call. */
1585 prev_dep_insn = insn;
1586 dep_insn = PREV_INSN (insn);
1587 while (GET_CODE (dep_insn) == INSN
1588 && GET_CODE (PATTERN (dep_insn)) == USE
1589 && GET_CODE (XEXP (PATTERN (dep_insn), 0)) == REG)
1591 SCHED_GROUP_P (prev_dep_insn) = 1;
1593 /* Make a copy of all dependencies on dep_insn, and add to insn.
1594 This is so that all of the dependencies will apply to the
1597 for (link = LOG_LINKS (dep_insn); link; link = XEXP (link, 1))
1598 add_dependence (insn, XEXP (link, 0), REG_NOTE_KIND (link));
1600 prev_dep_insn = dep_insn;
1601 dep_insn = PREV_INSN (dep_insn);
1606 /* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
1607 for every dependency. */
1610 sched_analyze (head, tail)
1614 register int n_insns = 0;
1616 register int luid = 0;
1619 for (insn = head; ; insn = NEXT_INSN (insn))
1621 INSN_LUID (insn) = luid++;
1623 if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
1625 sched_analyze_insn (PATTERN (insn), insn, loop_notes);
1629 else if (GET_CODE (insn) == CALL_INSN)
1634 /* Any instruction using a hard register which may get clobbered
1635 by a call needs to be marked as dependent on this call.
1636 This prevents a use of a hard return reg from being moved
1637 past a void call (i.e. it does not explicitly set the hard
1640 /* If this call is followed by a NOTE_INSN_SETJMP, then assume that
1641 all registers, not just hard registers, may be clobbered by this
1644 /* Insn, being a CALL_INSN, magically depends on
1645 `last_function_call' already. */
1647 if (NEXT_INSN (insn) && GET_CODE (NEXT_INSN (insn)) == NOTE
1648 && NOTE_LINE_NUMBER (NEXT_INSN (insn)) == NOTE_INSN_SETJMP)
1650 int max_reg = max_reg_num ();
1651 for (i = 0; i < max_reg; i++)
1653 for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
1654 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
1655 reg_last_uses[i] = 0;
1656 if (reg_last_sets[i])
1657 add_dependence (insn, reg_last_sets[i], 0);
1659 reg_pending_sets_all = 1;
1661 /* Add a pair of fake REG_NOTEs which we will later
1662 convert back into a NOTE_INSN_SETJMP note. See
1663 reemit_notes for why we use a pair of NOTEs. */
1665 REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_DEAD,
1668 REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_DEAD,
1669 GEN_INT (NOTE_INSN_SETJMP),
1674 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1675 if (call_used_regs[i] || global_regs[i])
1677 for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
1678 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
1679 reg_last_uses[i] = 0;
1680 if (reg_last_sets[i])
1681 add_dependence (insn, reg_last_sets[i], REG_DEP_ANTI);
1682 SET_REGNO_REG_SET (reg_pending_sets, i);
1686 /* For each insn which shouldn't cross a call, add a dependence
1687 between that insn and this call insn. */
1688 x = LOG_LINKS (sched_before_next_call);
1691 add_dependence (insn, XEXP (x, 0), REG_DEP_ANTI);
1694 LOG_LINKS (sched_before_next_call) = 0;
1696 sched_analyze_insn (PATTERN (insn), insn, loop_notes);
1699 /* In the absence of interprocedural alias analysis, we must flush
1700 all pending reads and writes, and start new dependencies starting
1701 from here. But only flush writes for constant calls (which may
1702 be passed a pointer to something we haven't written yet). */
1703 flush_pending_lists (insn, CONST_CALL_P (insn));
1705 /* Depend this function call (actually, the user of this
1706 function call) on all hard register clobberage. */
1707 last_function_call = insn;
1711 /* See comments on reemit_notes as to why we do this. */
1712 else if (GET_CODE (insn) == NOTE
1713 && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
1714 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END
1715 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
1716 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END
1717 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_START
1718 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_END
1719 || (NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP
1720 && GET_CODE (PREV_INSN (insn)) != CALL_INSN)))
1722 loop_notes = gen_rtx_EXPR_LIST (REG_DEAD,
1723 GEN_INT (NOTE_BLOCK_NUMBER (insn)),
1725 loop_notes = gen_rtx_EXPR_LIST (REG_DEAD,
1726 GEN_INT (NOTE_LINE_NUMBER (insn)),
1728 CONST_CALL_P (loop_notes) = CONST_CALL_P (insn);
1738 /* Called when we see a set of a register. If death is true, then we are
1739 scanning backwards. Mark that register as unborn. If nobody says
1740 otherwise, that is how things will remain. If death is false, then we
1741 are scanning forwards. Mark that register as being born. */
1744 sched_note_set (x, death)
1749 register rtx reg = SET_DEST (x);
1755 while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == STRICT_LOW_PART
1756 || GET_CODE (reg) == SIGN_EXTRACT || GET_CODE (reg) == ZERO_EXTRACT)
1758 /* Must treat modification of just one hardware register of a multi-reg
1759 value or just a byte field of a register exactly the same way that
1760 mark_set_1 in flow.c does, i.e. anything except a paradoxical subreg
1761 does not kill the entire register. */
1762 if (GET_CODE (reg) != SUBREG
1763 || REG_SIZE (SUBREG_REG (reg)) > REG_SIZE (reg))
1766 reg = SUBREG_REG (reg);
1769 if (GET_CODE (reg) != REG)
1772 /* Global registers are always live, so the code below does not apply
1775 regno = REGNO (reg);
1776 if (regno >= FIRST_PSEUDO_REGISTER || ! global_regs[regno])
1780 /* If we only set part of the register, then this set does not
1785 /* Try killing this register. */
1786 if (regno < FIRST_PSEUDO_REGISTER)
1788 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
1791 CLEAR_REGNO_REG_SET (bb_live_regs, regno + j);
1792 SET_REGNO_REG_SET (bb_dead_regs, regno + j);
1797 CLEAR_REGNO_REG_SET (bb_live_regs, regno);
1798 SET_REGNO_REG_SET (bb_dead_regs, regno);
1803 /* Make the register live again. */
1804 if (regno < FIRST_PSEUDO_REGISTER)
1806 int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
1809 SET_REGNO_REG_SET (bb_live_regs, regno + j);
1810 CLEAR_REGNO_REG_SET (bb_dead_regs, regno + j);
1815 SET_REGNO_REG_SET (bb_live_regs, regno);
1816 CLEAR_REGNO_REG_SET (bb_dead_regs, regno);
1822 /* Macros and functions for keeping the priority queue sorted, and
1823 dealing with queueing and dequeueing of instructions. */
1825 #define SCHED_SORT(READY, NEW_READY, OLD_READY) \
1826 do { if ((NEW_READY) - (OLD_READY) == 1) \
1827 swap_sort (READY, NEW_READY); \
1828 else if ((NEW_READY) - (OLD_READY) > 1) \
1829 qsort (READY, NEW_READY, sizeof (rtx), rank_for_schedule); } \
1832 /* Returns a positive value if y is preferred; returns a negative value if
1833 x is preferred. Should never return 0, since that will make the sort
1837 rank_for_schedule (x, y)
1838 const GENERIC_PTR x;
1839 const GENERIC_PTR y;
1841 rtx tmp = *(rtx *)y;
1842 rtx tmp2 = *(rtx *)x;
1844 int tmp_class, tmp2_class;
1847 /* Choose the instruction with the highest priority, if different. */
1848 if ((value = INSN_PRIORITY (tmp) - INSN_PRIORITY (tmp2)))
1851 if (last_scheduled_insn)
1853 /* Classify the instructions into three classes:
1854 1) Data dependent on last schedule insn.
1855 2) Anti/Output dependent on last scheduled insn.
1856 3) Independent of last scheduled insn, or has latency of one.
1857 Choose the insn from the highest numbered class if different. */
1858 link = find_insn_list (tmp, LOG_LINKS (last_scheduled_insn));
1859 if (link == 0 || insn_cost (tmp, link, last_scheduled_insn) == 1)
1861 else if (REG_NOTE_KIND (link) == 0) /* Data dependence. */
1866 link = find_insn_list (tmp2, LOG_LINKS (last_scheduled_insn));
1867 if (link == 0 || insn_cost (tmp2, link, last_scheduled_insn) == 1)
1869 else if (REG_NOTE_KIND (link) == 0) /* Data dependence. */
1874 if ((value = tmp_class - tmp2_class))
1878 /* If insns are equally good, sort by INSN_LUID (original insn order),
1879 so that we make the sort stable. This minimizes instruction movement,
1880 thus minimizing sched's effect on debugging and cross-jumping. */
1881 return INSN_LUID (tmp) - INSN_LUID (tmp2);
1884 /* Resort the array A in which only element at index N may be out of order. */
1886 __inline static void
1894 while (i >= 0 && rank_for_schedule (a+i, &insn) >= 0)
1902 static int max_priority;
1904 /* Add INSN to the insn queue so that it fires at least N_CYCLES
1905 before the currently executing insn. */
1907 __inline static void
1908 queue_insn (insn, n_cycles)
1912 int next_q = NEXT_Q_AFTER (q_ptr, n_cycles);
1913 NEXT_INSN (insn) = insn_queue[next_q];
1914 insn_queue[next_q] = insn;
1918 /* Return nonzero if PAT is the pattern of an insn which makes a
1922 birthing_insn_p (pat)
1927 if (reload_completed == 1)
1930 if (GET_CODE (pat) == SET
1931 && GET_CODE (SET_DEST (pat)) == REG)
1933 rtx dest = SET_DEST (pat);
1934 int i = REGNO (dest);
1936 /* It would be more accurate to use refers_to_regno_p or
1937 reg_mentioned_p to determine when the dest is not live before this
1940 if (REGNO_REG_SET_P (bb_live_regs, i))
1941 return (REG_N_SETS (i) == 1);
1945 if (GET_CODE (pat) == PARALLEL)
1947 for (j = 0; j < XVECLEN (pat, 0); j++)
1948 if (birthing_insn_p (XVECEXP (pat, 0, j)))
1954 /* PREV is an insn that is ready to execute. Adjust its priority if that
1955 will help shorten register lifetimes. */
1957 __inline static void
1958 adjust_priority (prev)
1961 /* Trying to shorten register lives after reload has completed
1962 is useless and wrong. It gives inaccurate schedules. */
1963 if (reload_completed == 0)
1968 /* ??? This code has no effect, because REG_DEAD notes are removed
1969 before we ever get here. */
1970 for (note = REG_NOTES (prev); note; note = XEXP (note, 1))
1971 if (REG_NOTE_KIND (note) == REG_DEAD)
1974 /* Defer scheduling insns which kill registers, since that
1975 shortens register lives. Prefer scheduling insns which
1976 make registers live for the same reason. */
1980 INSN_PRIORITY (prev) >>= 3;
1983 INSN_PRIORITY (prev) >>= 2;
1987 INSN_PRIORITY (prev) >>= 1;
1990 if (birthing_insn_p (PATTERN (prev)))
1992 int max = max_priority;
1994 if (max > INSN_PRIORITY (prev))
1995 INSN_PRIORITY (prev) = max;
1999 #ifdef ADJUST_PRIORITY
2000 ADJUST_PRIORITY (prev);
2005 /* INSN is the "currently executing insn". Launch each insn which was
2006 waiting on INSN (in the backwards dataflow sense). READY is a
2007 vector of insns which are ready to fire. N_READY is the number of
2008 elements in READY. CLOCK is the current virtual cycle. */
2011 schedule_insn (insn, ready, n_ready, clock)
2018 int new_ready = n_ready;
2020 if (MAX_BLOCKAGE > 1)
2021 schedule_unit (insn_unit (insn), insn, clock);
2023 if (LOG_LINKS (insn) == 0)
2026 /* This is used by the function adjust_priority above. */
2028 max_priority = MAX (INSN_PRIORITY (ready[0]), INSN_PRIORITY (insn));
2030 max_priority = INSN_PRIORITY (insn);
2032 for (link = LOG_LINKS (insn); link != 0; link = XEXP (link, 1))
2034 rtx prev = XEXP (link, 0);
2035 int cost = insn_cost (prev, link, insn);
2037 if ((INSN_REF_COUNT (prev) -= 1) != 0)
2039 /* We satisfied one requirement to fire PREV. Record the earliest
2040 time when PREV can fire. No need to do this if the cost is 1,
2041 because PREV can fire no sooner than the next cycle. */
2043 INSN_TICK (prev) = MAX (INSN_TICK (prev), clock + cost);
2047 /* We satisfied the last requirement to fire PREV. Ensure that all
2048 timing requirements are satisfied. */
2049 if (INSN_TICK (prev) - clock > cost)
2050 cost = INSN_TICK (prev) - clock;
2052 /* Adjust the priority of PREV and either put it on the ready
2053 list or queue it. */
2054 adjust_priority (prev);
2056 ready[new_ready++] = prev;
2058 queue_insn (prev, cost);
2065 /* Given N_READY insns in the ready list READY at time CLOCK, queue
2066 those that are blocked due to function unit hazards and rearrange
2067 the remaining ones to minimize subsequent function unit hazards. */
2070 schedule_select (ready, n_ready, clock, file)
2075 int pri = INSN_PRIORITY (ready[0]);
2076 int i, j, k, q, cost, best_cost, best_insn = 0, new_ready = n_ready;
2079 /* Work down the ready list in groups of instructions with the same
2080 priority value. Queue insns in the group that are blocked and
2081 select among those that remain for the one with the largest
2082 potential hazard. */
2083 for (i = 0; i < n_ready; i = j)
2086 for (j = i + 1; j < n_ready; j++)
2087 if ((pri = INSN_PRIORITY (ready[j])) != opri)
2090 /* Queue insns in the group that are blocked. */
2091 for (k = i, q = 0; k < j; k++)
2094 if ((cost = actual_hazard (insn_unit (insn), insn, clock, 0)) != 0)
2098 queue_insn (insn, cost);
2100 fprintf (file, "\n;; blocking insn %d for %d cycles",
2101 INSN_UID (insn), cost);
2106 /* Check the next group if all insns were queued. */
2110 /* If more than one remains, select the first one with the largest
2111 potential hazard. */
2112 else if (j - i - q > 1)
2115 for (k = i; k < j; k++)
2117 if ((insn = ready[k]) == 0)
2119 if ((cost = potential_hazard (insn_unit (insn), insn, 0))
2127 /* We have found a suitable insn to schedule. */
2131 /* Move the best insn to be front of the ready list. */
2136 fprintf (file, ", now");
2137 for (i = 0; i < n_ready; i++)
2139 fprintf (file, " %d", INSN_UID (ready[i]));
2140 fprintf (file, "\n;; insn %d has a greater potential hazard",
2141 INSN_UID (ready[best_insn]));
2143 for (i = best_insn; i > 0; i--)
2146 ready[i-1] = ready[i];
2151 /* Compact the ready list. */
2152 if (new_ready < n_ready)
2153 for (i = j = 0; i < n_ready; i++)
2155 ready[j++] = ready[i];
2160 /* Add a REG_DEAD note for REG to INSN, reusing a REG_DEAD note from the
2164 create_reg_dead_note (reg, insn)
2169 /* The number of registers killed after scheduling must be the same as the
2170 number of registers killed before scheduling. The number of REG_DEAD
2171 notes may not be conserved, i.e. two SImode hard register REG_DEAD notes
2172 might become one DImode hard register REG_DEAD note, but the number of
2173 registers killed will be conserved.
2175 We carefully remove REG_DEAD notes from the dead_notes list, so that
2176 there will be none left at the end. If we run out early, then there
2177 is a bug somewhere in flow, combine and/or sched. */
2179 if (dead_notes == 0)
2184 link = rtx_alloc (EXPR_LIST);
2185 PUT_REG_NOTE_KIND (link, REG_DEAD);
2190 /* Number of regs killed by REG. */
2191 int regs_killed = (REGNO (reg) >= FIRST_PSEUDO_REGISTER ? 1
2192 : HARD_REGNO_NREGS (REGNO (reg), GET_MODE (reg)));
2193 /* Number of regs killed by REG_DEAD notes taken off the list. */
2197 reg_note_regs = (REGNO (XEXP (link, 0)) >= FIRST_PSEUDO_REGISTER ? 1
2198 : HARD_REGNO_NREGS (REGNO (XEXP (link, 0)),
2199 GET_MODE (XEXP (link, 0))));
2200 while (reg_note_regs < regs_killed)
2202 /* LINK might be zero if we killed more registers after scheduling
2203 than before, and the last hard register we kill is actually
2204 multiple hard regs. */
2205 if (link == NULL_RTX)
2208 link = XEXP (link, 1);
2209 reg_note_regs += (REGNO (XEXP (link, 0)) >= FIRST_PSEUDO_REGISTER ? 1
2210 : HARD_REGNO_NREGS (REGNO (XEXP (link, 0)),
2211 GET_MODE (XEXP (link, 0))));
2213 dead_notes = XEXP (link, 1);
2215 /* If we took too many regs kills off, put the extra ones back. */
2216 while (reg_note_regs > regs_killed)
2218 rtx temp_reg, temp_link;
2220 temp_reg = gen_rtx_REG (word_mode, 0);
2221 temp_link = rtx_alloc (EXPR_LIST);
2222 PUT_REG_NOTE_KIND (temp_link, REG_DEAD);
2223 XEXP (temp_link, 0) = temp_reg;
2224 XEXP (temp_link, 1) = dead_notes;
2225 dead_notes = temp_link;
2230 XEXP (link, 0) = reg;
2231 XEXP (link, 1) = REG_NOTES (insn);
2232 REG_NOTES (insn) = link;
2235 /* Subroutine on attach_deaths_insn--handles the recursive search
2236 through INSN. If SET_P is true, then x is being modified by the insn. */
2239 attach_deaths (x, insn, set_p)
2246 register enum rtx_code code;
2252 code = GET_CODE (x);
2264 /* Get rid of the easy cases first. */
2269 /* If the register dies in this insn, queue that note, and mark
2270 this register as needing to die. */
2271 /* This code is very similar to mark_used_1 (if set_p is false)
2272 and mark_set_1 (if set_p is true) in flow.c. */
2282 all_needed = some_needed = REGNO_REG_SET_P (old_live_regs, regno);
2283 if (regno < FIRST_PSEUDO_REGISTER)
2287 n = HARD_REGNO_NREGS (regno, GET_MODE (x));
2290 int needed = (REGNO_REG_SET_P (old_live_regs, regno + n));
2291 some_needed |= needed;
2292 all_needed &= needed;
2296 /* If it wasn't live before we started, then add a REG_DEAD note.
2297 We must check the previous lifetime info not the current info,
2298 because we may have to execute this code several times, e.g.
2299 once for a clobber (which doesn't add a note) and later
2300 for a use (which does add a note).
2302 Always make the register live. We must do this even if it was
2303 live before, because this may be an insn which sets and uses
2304 the same register, in which case the register has already been
2305 killed, so we must make it live again.
2307 Global registers are always live, and should never have a REG_DEAD
2308 note added for them, so none of the code below applies to them. */
2310 if (regno >= FIRST_PSEUDO_REGISTER || ! global_regs[regno])
2312 /* Never add REG_DEAD notes for STACK_POINTER_REGNUM
2313 since it's always considered to be live. Similarly
2314 for FRAME_POINTER_REGNUM if a frame pointer is needed
2315 and for ARG_POINTER_REGNUM if it is fixed. */
2316 if (! (regno == FRAME_POINTER_REGNUM
2317 && (! reload_completed || frame_pointer_needed))
2318 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
2319 && ! (regno == HARD_FRAME_POINTER_REGNUM
2320 && (! reload_completed || frame_pointer_needed))
2322 #if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
2323 && ! (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
2325 && regno != STACK_POINTER_REGNUM)
2327 if (! all_needed && ! dead_or_set_p (insn, x))
2329 /* Check for the case where the register dying partially
2330 overlaps the register set by this insn. */
2331 if (regno < FIRST_PSEUDO_REGISTER
2332 && HARD_REGNO_NREGS (regno, GET_MODE (x)) > 1)
2334 int n = HARD_REGNO_NREGS (regno, GET_MODE (x));
2336 some_needed |= dead_or_set_regno_p (insn, regno + n);
2339 /* If none of the words in X is needed, make a REG_DEAD
2340 note. Otherwise, we must make partial REG_DEAD
2343 create_reg_dead_note (x, insn);
2348 /* Don't make a REG_DEAD note for a part of a
2349 register that is set in the insn. */
2350 for (i = HARD_REGNO_NREGS (regno, GET_MODE (x)) - 1;
2352 if (! REGNO_REG_SET_P (old_live_regs, regno + i)
2353 && ! dead_or_set_regno_p (insn, regno + i))
2354 create_reg_dead_note (gen_rtx_REG (reg_raw_mode[regno + i],
2361 if (regno < FIRST_PSEUDO_REGISTER)
2363 int j = HARD_REGNO_NREGS (regno, GET_MODE (x));
2366 CLEAR_REGNO_REG_SET (bb_dead_regs, regno + j);
2367 SET_REGNO_REG_SET (bb_live_regs, regno + j);
2372 CLEAR_REGNO_REG_SET (bb_dead_regs, regno);
2373 SET_REGNO_REG_SET (bb_live_regs, regno);
2380 /* Handle tail-recursive case. */
2381 attach_deaths (XEXP (x, 0), insn, 0);
2385 attach_deaths (SUBREG_REG (x), insn,
2386 set_p && ((GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)))
2388 || (GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)))
2389 == GET_MODE_SIZE (GET_MODE ((x))))));
2392 case STRICT_LOW_PART:
2393 attach_deaths (XEXP (x, 0), insn, 0);
2398 attach_deaths (XEXP (x, 0), insn, 0);
2399 attach_deaths (XEXP (x, 1), insn, 0);
2400 attach_deaths (XEXP (x, 2), insn, 0);
2404 /* Other cases: walk the insn. */
2405 fmt = GET_RTX_FORMAT (code);
2406 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2409 attach_deaths (XEXP (x, i), insn, 0);
2410 else if (fmt[i] == 'E')
2411 for (j = 0; j < XVECLEN (x, i); j++)
2412 attach_deaths (XVECEXP (x, i, j), insn, 0);
2417 /* After INSN has executed, add register death notes for each register
2418 that is dead after INSN. */
2421 attach_deaths_insn (insn)
2424 rtx x = PATTERN (insn);
2425 register RTX_CODE code = GET_CODE (x);
2430 attach_deaths (SET_SRC (x), insn, 0);
2432 /* A register might die here even if it is the destination, e.g.
2433 it is the target of a volatile read and is otherwise unused.
2434 Hence we must always call attach_deaths for the SET_DEST. */
2435 attach_deaths (SET_DEST (x), insn, 1);
2437 else if (code == PARALLEL)
2440 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
2442 code = GET_CODE (XVECEXP (x, 0, i));
2445 attach_deaths (SET_SRC (XVECEXP (x, 0, i)), insn, 0);
2447 attach_deaths (SET_DEST (XVECEXP (x, 0, i)), insn, 1);
2449 /* Flow does not add REG_DEAD notes to registers that die in
2450 clobbers, so we can't either. */
2451 else if (code != CLOBBER)
2452 attach_deaths (XVECEXP (x, 0, i), insn, 0);
2455 /* If this is a CLOBBER, only add REG_DEAD notes to registers inside a
2456 MEM being clobbered, just like flow. */
2457 else if (code == CLOBBER && GET_CODE (XEXP (x, 0)) == MEM)
2458 attach_deaths (XEXP (XEXP (x, 0), 0), insn, 0);
2459 /* Otherwise don't add a death note to things being clobbered. */
2460 else if (code != CLOBBER)
2461 attach_deaths (x, insn, 0);
2463 /* Make death notes for things used in the called function. */
2464 if (GET_CODE (insn) == CALL_INSN)
2465 for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
2466 attach_deaths (XEXP (XEXP (link, 0), 0), insn,
2467 GET_CODE (XEXP (link, 0)) == CLOBBER);
2470 /* Delete notes beginning with INSN and maybe put them in the chain
2471 of notes ended by NOTE_LIST.
2472 Returns the insn following the notes. */
2475 unlink_notes (insn, tail)
2478 rtx prev = PREV_INSN (insn);
2480 while (insn != tail && GET_CODE (insn) == NOTE)
2482 rtx next = NEXT_INSN (insn);
2483 /* Delete the note from its current position. */
2485 NEXT_INSN (prev) = next;
2487 PREV_INSN (next) = prev;
2489 if (write_symbols != NO_DEBUG && NOTE_LINE_NUMBER (insn) > 0)
2490 /* Record line-number notes so they can be reused. */
2491 LINE_NOTE (insn) = insn;
2493 /* Don't save away NOTE_INSN_SETJMPs, because they must remain
2494 immediately after the call they follow. We use a fake
2495 (REG_DEAD (const_int -1)) note to remember them.
2496 Likewise with NOTE_INSN_{LOOP,EHREGION}_{BEG, END}. */
2497 else if (NOTE_LINE_NUMBER (insn) != NOTE_INSN_SETJMP
2498 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG
2499 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_END
2500 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_RANGE_START
2501 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_RANGE_END
2502 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_BEG
2503 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_END)
2505 /* Insert the note at the end of the notes list. */
2506 PREV_INSN (insn) = note_list;
2508 NEXT_INSN (note_list) = insn;
2517 /* Constructor for `sometimes' data structure. */
2520 new_sometimes_live (regs_sometimes_live, regno, sometimes_max)
2521 struct sometimes *regs_sometimes_live;
2525 register struct sometimes *p;
2527 /* There should never be a register greater than max_regno here. If there
2528 is, it means that a define_split has created a new pseudo reg. This
2529 is not allowed, since there will not be flow info available for any
2530 new register, so catch the error here. */
2531 if (regno >= max_regno)
2534 p = ®s_sometimes_live[sometimes_max];
2537 p->calls_crossed = 0;
2539 return sometimes_max;
2542 /* Count lengths of all regs we are currently tracking,
2543 and find new registers no longer live. */
2546 finish_sometimes_live (regs_sometimes_live, sometimes_max)
2547 struct sometimes *regs_sometimes_live;
2552 for (i = 0; i < sometimes_max; i++)
2554 register struct sometimes *p = ®s_sometimes_live[i];
2555 int regno = p->regno;
2557 sched_reg_live_length[regno] += p->live_length;
2558 sched_reg_n_calls_crossed[regno] += p->calls_crossed;
2562 /* Search INSN for fake REG_DEAD note pairs for NOTE_INSN_SETJMP,
2563 NOTE_INSN_{LOOP,EHREGION}_{BEG,END}; and convert them back into
2564 NOTEs. The REG_DEAD note following first one is contains the saved
2565 value for NOTE_BLOCK_NUMBER which is useful for
2566 NOTE_INSN_EH_REGION_{BEG,END} NOTEs. LAST is the last instruction
2567 output by the instruction scheduler. Return the new value of LAST. */
2570 reemit_notes (insn, last)
2576 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
2578 if (REG_NOTE_KIND (note) == REG_DEAD
2579 && GET_CODE (XEXP (note, 0)) == CONST_INT)
2581 if (INTVAL (XEXP (note, 0)) == NOTE_INSN_SETJMP)
2583 CONST_CALL_P (emit_note_after (INTVAL (XEXP (note, 0)), insn))
2584 = CONST_CALL_P (note);
2585 remove_note (insn, note);
2586 note = XEXP (note, 1);
2590 last = emit_note_before (INTVAL (XEXP (note, 0)), last);
2591 remove_note (insn, note);
2592 note = XEXP (note, 1);
2593 NOTE_BLOCK_NUMBER (last) = INTVAL (XEXP (note, 0));
2595 remove_note (insn, note);
2601 /* Use modified list scheduling to rearrange insns in basic block
2602 B. FILE, if nonzero, is where we dump interesting output about
2606 schedule_block (b, file)
2612 int i, j, n_ready = 0, new_ready, n_insns;
2613 int sched_n_insns = 0;
2615 #define NEED_NOTHING 0
2620 /* HEAD and TAIL delimit the region being scheduled. */
2621 rtx head = BLOCK_HEAD (b);
2622 rtx tail = BLOCK_END (b);
2623 /* PREV_HEAD and NEXT_TAIL are the boundaries of the insns
2624 being scheduled. When the insns have been ordered,
2625 these insns delimit where the new insns are to be
2626 spliced back into the insn chain. */
2630 /* Keep life information accurate. */
2631 register struct sometimes *regs_sometimes_live;
2635 fprintf (file, ";;\t -- basic block number %d from %d to %d --\n",
2636 b, INSN_UID (BLOCK_HEAD (b)), INSN_UID (BLOCK_END (b)));
2639 reg_last_uses = (rtx *) alloca (i * sizeof (rtx));
2640 bzero ((char *) reg_last_uses, i * sizeof (rtx));
2641 reg_last_sets = (rtx *) alloca (i * sizeof (rtx));
2642 bzero ((char *) reg_last_sets, i * sizeof (rtx));
2643 reg_pending_sets = ALLOCA_REG_SET ();
2644 CLEAR_REG_SET (reg_pending_sets);
2645 reg_pending_sets_all = 0;
2649 /* We used to have code to avoid getting parameters moved from hard
2650 argument registers into pseudos.
2652 However, it was removed when it proved to be of marginal benefit and
2653 caused problems because of different notions of what the "head" insn
2656 /* Remove certain insns at the beginning from scheduling,
2657 by advancing HEAD. */
2659 /* At the start of a function, before reload has run, don't delay getting
2660 parameters from hard registers into pseudo registers. */
2661 if (reload_completed == 0 && b == 0)
2664 && GET_CODE (head) == NOTE
2665 && NOTE_LINE_NUMBER (head) != NOTE_INSN_FUNCTION_BEG)
2666 head = NEXT_INSN (head);
2668 && GET_CODE (head) == INSN
2669 && GET_CODE (PATTERN (head)) == SET)
2671 rtx src = SET_SRC (PATTERN (head));
2672 while (GET_CODE (src) == SUBREG
2673 || GET_CODE (src) == SIGN_EXTEND
2674 || GET_CODE (src) == ZERO_EXTEND
2675 || GET_CODE (src) == SIGN_EXTRACT
2676 || GET_CODE (src) == ZERO_EXTRACT)
2677 src = XEXP (src, 0);
2678 if (GET_CODE (src) != REG
2679 || REGNO (src) >= FIRST_PSEUDO_REGISTER)
2681 /* Keep this insn from ever being scheduled. */
2682 INSN_REF_COUNT (head) = 1;
2683 head = NEXT_INSN (head);
2688 /* Don't include any notes or labels at the beginning of the
2689 basic block, or notes at the ends of basic blocks. */
2690 while (head != tail)
2692 if (GET_CODE (head) == NOTE)
2693 head = NEXT_INSN (head);
2694 else if (GET_CODE (tail) == NOTE)
2695 tail = PREV_INSN (tail);
2696 else if (GET_CODE (head) == CODE_LABEL)
2697 head = NEXT_INSN (head);
2700 /* If the only insn left is a NOTE or a CODE_LABEL, then there is no need
2701 to schedule this block. */
2703 && (GET_CODE (head) == NOTE || GET_CODE (head) == CODE_LABEL))
2707 /* This short-cut doesn't work. It does not count call insns crossed by
2708 registers in reg_sometimes_live. It does not mark these registers as
2709 dead if they die in this block. It does not mark these registers live
2710 (or create new reg_sometimes_live entries if necessary) if they are born
2713 The easy solution is to just always schedule a block. This block only
2714 has one insn, so this won't slow down this pass by much. */
2720 /* Now HEAD through TAIL are the insns actually to be rearranged;
2721 Let PREV_HEAD and NEXT_TAIL enclose them. */
2722 prev_head = PREV_INSN (head);
2723 next_tail = NEXT_INSN (tail);
2725 /* Initialize basic block data structures. */
2727 pending_read_insns = 0;
2728 pending_read_mems = 0;
2729 pending_write_insns = 0;
2730 pending_write_mems = 0;
2731 pending_lists_length = 0;
2732 last_pending_memory_flush = 0;
2733 last_function_call = 0;
2734 last_scheduled_insn = 0;
2736 LOG_LINKS (sched_before_next_call) = 0;
2738 n_insns = sched_analyze (head, tail);
2741 free_pending_lists ();
2745 /* Allocate vector to hold insns to be rearranged (except those
2746 insns which are controlled by an insn with SCHED_GROUP_P set).
2747 All these insns are included between ORIG_HEAD and ORIG_TAIL,
2748 as those variables ultimately are set up. */
2749 ready = (rtx *) alloca ((n_insns+1) * sizeof (rtx));
2751 /* TAIL is now the last of the insns to be rearranged.
2752 Put those insns into the READY vector. */
2755 /* For all branches, calls, uses, and cc0 setters, force them to remain
2756 in order at the end of the block by adding dependencies and giving
2757 the last a high priority. There may be notes present, and prev_head
2760 Branches must obviously remain at the end. Calls should remain at the
2761 end since moving them results in worse register allocation. Uses remain
2762 at the end to ensure proper register allocation. cc0 setters remaim
2763 at the end because they can't be moved away from their cc0 user. */
2765 while (GET_CODE (insn) == CALL_INSN || GET_CODE (insn) == JUMP_INSN
2766 || (GET_CODE (insn) == INSN
2767 && (GET_CODE (PATTERN (insn)) == USE
2769 || sets_cc0_p (PATTERN (insn))
2772 || GET_CODE (insn) == NOTE)
2774 if (GET_CODE (insn) != NOTE)
2779 ready[n_ready++] = insn;
2780 INSN_PRIORITY (insn) = TAIL_PRIORITY - i;
2781 INSN_REF_COUNT (insn) = 0;
2783 else if (! find_insn_list (insn, LOG_LINKS (last)))
2785 add_dependence (last, insn, REG_DEP_ANTI);
2786 INSN_REF_COUNT (insn)++;
2790 /* Skip over insns that are part of a group. */
2791 while (SCHED_GROUP_P (insn))
2793 insn = prev_nonnote_insn (insn);
2798 insn = PREV_INSN (insn);
2799 /* Don't overrun the bounds of the basic block. */
2800 if (insn == prev_head)
2804 /* Assign priorities to instructions. Also check whether they
2805 are in priority order already. If so then I will be nonnegative.
2806 We use this shortcut only before reloading. */
2808 i = reload_completed ? DONE_PRIORITY : MAX_PRIORITY;
2811 for (; insn != prev_head; insn = PREV_INSN (insn))
2813 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
2816 if (INSN_REF_COUNT (insn) == 0)
2819 ready[n_ready++] = insn;
2822 /* Make this dependent on the last of the instructions
2823 that must remain in order at the end of the block. */
2824 add_dependence (last, insn, REG_DEP_ANTI);
2825 INSN_REF_COUNT (insn) = 1;
2828 if (SCHED_GROUP_P (insn))
2830 while (SCHED_GROUP_P (insn))
2832 insn = prev_nonnote_insn (insn);
2840 if (INSN_PRIORITY (insn) < i)
2841 i = INSN_PRIORITY (insn);
2842 else if (INSN_PRIORITY (insn) > i)
2849 /* This short-cut doesn't work. It does not count call insns crossed by
2850 registers in reg_sometimes_live. It does not mark these registers as
2851 dead if they die in this block. It does not mark these registers live
2852 (or create new reg_sometimes_live entries if necessary) if they are born
2855 The easy solution is to just always schedule a block. These blocks tend
2856 to be very short, so this doesn't slow down this pass by much. */
2858 /* If existing order is good, don't bother to reorder. */
2859 if (i != DONE_PRIORITY)
2862 fprintf (file, ";; already scheduled\n");
2864 if (reload_completed == 0)
2866 for (i = 0; i < sometimes_max; i++)
2867 regs_sometimes_live[i].live_length += n_insns;
2869 finish_sometimes_live (regs_sometimes_live, sometimes_max);
2871 free_pending_lists ();
2876 /* Scan all the insns to be scheduled, removing NOTE insns
2877 and register death notes.
2878 Line number NOTE insns end up in NOTE_LIST.
2879 Register death notes end up in DEAD_NOTES.
2881 Recreate the register life information for the end of this basic
2884 if (reload_completed == 0)
2886 COPY_REG_SET (bb_live_regs, BASIC_BLOCK (b)->global_live_at_start);
2887 CLEAR_REG_SET (bb_dead_regs);
2891 /* This is the first block in the function. There may be insns
2892 before head that we can't schedule. We still need to examine
2893 them though for accurate register lifetime analysis. */
2895 /* We don't want to remove any REG_DEAD notes as the code below
2898 for (insn = BLOCK_HEAD (b); insn != head;
2899 insn = NEXT_INSN (insn))
2900 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
2902 /* See if the register gets born here. */
2903 /* We must check for registers being born before we check for
2904 registers dying. It is possible for a register to be born
2905 and die in the same insn, e.g. reading from a volatile
2906 memory location into an otherwise unused register. Such
2907 a register must be marked as dead after this insn. */
2908 if (GET_CODE (PATTERN (insn)) == SET
2909 || GET_CODE (PATTERN (insn)) == CLOBBER)
2910 sched_note_set (PATTERN (insn), 0);
2911 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
2914 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
2915 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
2916 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
2917 sched_note_set (XVECEXP (PATTERN (insn), 0, j), 0);
2919 /* ??? This code is obsolete and should be deleted. It
2920 is harmless though, so we will leave it in for now. */
2921 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
2922 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == USE)
2923 sched_note_set (XVECEXP (PATTERN (insn), 0, j), 0);
2926 /* Each call clobbers (makes live) all call-clobbered regs
2927 that are not global or fixed. Note that the function-value
2928 reg is a call_clobbered reg. */
2930 if (GET_CODE (insn) == CALL_INSN)
2933 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
2934 if (call_used_regs[j] && ! global_regs[j]
2937 SET_REGNO_REG_SET (bb_live_regs, j);
2938 CLEAR_REGNO_REG_SET (bb_dead_regs, j);
2942 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2944 if ((REG_NOTE_KIND (link) == REG_DEAD
2945 || REG_NOTE_KIND (link) == REG_UNUSED)
2946 /* Verify that the REG_NOTE has a valid value. */
2947 && GET_CODE (XEXP (link, 0)) == REG)
2949 register int regno = REGNO (XEXP (link, 0));
2951 if (regno < FIRST_PSEUDO_REGISTER)
2953 int j = HARD_REGNO_NREGS (regno,
2954 GET_MODE (XEXP (link, 0)));
2957 CLEAR_REGNO_REG_SET (bb_live_regs, regno + j);
2958 SET_REGNO_REG_SET (bb_dead_regs, regno + j);
2963 CLEAR_REGNO_REG_SET (bb_live_regs, regno);
2964 SET_REGNO_REG_SET (bb_dead_regs, regno);
2972 /* If debugging information is being produced, keep track of the line
2973 number notes for each insn. */
2974 if (write_symbols != NO_DEBUG)
2976 /* We must use the true line number for the first insn in the block
2977 that was computed and saved at the start of this pass. We can't
2978 use the current line number, because scheduling of the previous
2979 block may have changed the current line number. */
2980 rtx line = line_note_head[b];
2982 for (insn = BLOCK_HEAD (b);
2984 insn = NEXT_INSN (insn))
2985 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
2988 LINE_NOTE (insn) = line;
2991 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
2993 rtx prev, next, link;
2995 /* Farm out notes. This is needed to keep the debugger from
2996 getting completely deranged. */
2997 if (GET_CODE (insn) == NOTE)
3000 insn = unlink_notes (insn, next_tail);
3005 if (insn == next_tail)
3009 if (reload_completed == 0
3010 && GET_RTX_CLASS (GET_CODE (insn)) == 'i')
3012 /* See if the register gets born here. */
3013 /* We must check for registers being born before we check for
3014 registers dying. It is possible for a register to be born and
3015 die in the same insn, e.g. reading from a volatile memory
3016 location into an otherwise unused register. Such a register
3017 must be marked as dead after this insn. */
3018 if (GET_CODE (PATTERN (insn)) == SET
3019 || GET_CODE (PATTERN (insn)) == CLOBBER)
3020 sched_note_set (PATTERN (insn), 0);
3021 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
3024 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
3025 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
3026 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
3027 sched_note_set (XVECEXP (PATTERN (insn), 0, j), 0);
3029 /* ??? This code is obsolete and should be deleted. It
3030 is harmless though, so we will leave it in for now. */
3031 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
3032 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == USE)
3033 sched_note_set (XVECEXP (PATTERN (insn), 0, j), 0);
3036 /* Each call clobbers (makes live) all call-clobbered regs that are
3037 not global or fixed. Note that the function-value reg is a
3038 call_clobbered reg. */
3040 if (GET_CODE (insn) == CALL_INSN)
3043 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
3044 if (call_used_regs[j] && ! global_regs[j]
3047 SET_REGNO_REG_SET (bb_live_regs, j);
3048 CLEAR_REGNO_REG_SET (bb_dead_regs, j);
3052 /* Need to know what registers this insn kills. */
3053 for (prev = 0, link = REG_NOTES (insn); link; link = next)
3055 next = XEXP (link, 1);
3056 if ((REG_NOTE_KIND (link) == REG_DEAD
3057 || REG_NOTE_KIND (link) == REG_UNUSED)
3058 /* Verify that the REG_NOTE has a valid value. */
3059 && GET_CODE (XEXP (link, 0)) == REG)
3061 register int regno = REGNO (XEXP (link, 0));
3063 /* Only unlink REG_DEAD notes; leave REG_UNUSED notes
3065 if (REG_NOTE_KIND (link) == REG_DEAD)
3068 XEXP (prev, 1) = next;
3070 REG_NOTES (insn) = next;
3071 XEXP (link, 1) = dead_notes;
3077 if (regno < FIRST_PSEUDO_REGISTER)
3079 int j = HARD_REGNO_NREGS (regno,
3080 GET_MODE (XEXP (link, 0)));
3083 CLEAR_REGNO_REG_SET (bb_live_regs, regno + j);
3084 SET_REGNO_REG_SET (bb_dead_regs, regno + j);
3089 CLEAR_REGNO_REG_SET (bb_live_regs, regno);
3090 SET_REGNO_REG_SET (bb_dead_regs, regno);
3099 if (reload_completed == 0)
3101 /* Keep track of register lives. */
3102 old_live_regs = ALLOCA_REG_SET ();
3104 = (struct sometimes *) alloca (max_regno * sizeof (struct sometimes));
3107 /* Start with registers live at end. */
3108 COPY_REG_SET (old_live_regs, bb_live_regs);
3109 EXECUTE_IF_SET_IN_REG_SET (bb_live_regs, 0, j,
3112 = new_sometimes_live (regs_sometimes_live,
3117 SCHED_SORT (ready, n_ready, 1);
3121 fprintf (file, ";; ready list initially:\n;; ");
3122 for (i = 0; i < n_ready; i++)
3123 fprintf (file, "%d ", INSN_UID (ready[i]));
3124 fprintf (file, "\n\n");
3126 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
3127 if (INSN_PRIORITY (insn) > 0)
3128 fprintf (file, ";; insn[%4d]: priority = %4d, ref_count = %4d\n",
3129 INSN_UID (insn), INSN_PRIORITY (insn),
3130 INSN_REF_COUNT (insn));
3133 /* Now HEAD and TAIL are going to become disconnected
3134 entirely from the insn chain. */
3137 /* Q_SIZE will always be zero here. */
3138 q_ptr = 0; clock = 0;
3139 bzero ((char *) insn_queue, sizeof (insn_queue));
3141 /* Now, perform list scheduling. */
3143 /* Where we start inserting insns is after TAIL. */
3146 new_needs = (NEXT_INSN (prev_head) == BLOCK_HEAD (b)
3147 ? NEED_HEAD : NEED_NOTHING);
3148 if (PREV_INSN (next_tail) == BLOCK_END (b))
3149 new_needs |= NEED_TAIL;
3151 new_ready = n_ready;
3152 while (sched_n_insns < n_insns)
3154 q_ptr = NEXT_Q (q_ptr); clock++;
3156 /* Add all pending insns that can be scheduled without stalls to the
3158 for (insn = insn_queue[q_ptr]; insn; insn = NEXT_INSN (insn))
3161 fprintf (file, ";; launching %d before %d with no stalls at T-%d\n",
3162 INSN_UID (insn), INSN_UID (last), clock);
3163 ready[new_ready++] = insn;
3166 insn_queue[q_ptr] = 0;
3168 /* If there are no ready insns, stall until one is ready and add all
3169 of the pending insns at that point to the ready list. */
3172 register int stalls;
3174 for (stalls = 1; stalls < INSN_QUEUE_SIZE; stalls++)
3175 if ((insn = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
3177 for (; insn; insn = NEXT_INSN (insn))
3180 fprintf (file, ";; launching %d before %d with %d stalls at T-%d\n",
3181 INSN_UID (insn), INSN_UID (last), stalls, clock);
3182 ready[new_ready++] = insn;
3185 insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = 0;
3189 q_ptr = NEXT_Q_AFTER (q_ptr, stalls); clock += stalls;
3192 /* There should be some instructions waiting to fire. */
3198 fprintf (file, ";; ready list at T-%d:", clock);
3199 for (i = 0; i < new_ready; i++)
3200 fprintf (file, " %d (%x)",
3201 INSN_UID (ready[i]), INSN_PRIORITY (ready[i]));
3204 /* Sort the ready list and choose the best insn to schedule. Select
3205 which insn should issue in this cycle and queue those that are
3206 blocked by function unit hazards.
3208 N_READY holds the number of items that were scheduled the last time,
3209 minus the one instruction scheduled on the last loop iteration; it
3210 is not modified for any other reason in this loop. */
3212 SCHED_SORT (ready, new_ready, n_ready);
3213 if (MAX_BLOCKAGE > 1)
3215 new_ready = schedule_select (ready, new_ready, clock, file);
3219 fprintf (file, "\n");
3220 /* We must set n_ready here, to ensure that sorting always
3221 occurs when we come back to the SCHED_SORT line above. */
3226 n_ready = new_ready;
3227 last_scheduled_insn = insn = ready[0];
3229 /* The first insn scheduled becomes the new tail. */
3235 fprintf (file, ", now");
3236 for (i = 0; i < n_ready; i++)
3237 fprintf (file, " %d", INSN_UID (ready[i]));
3238 fprintf (file, "\n");
3241 if (DONE_PRIORITY_P (insn))
3244 if (reload_completed == 0)
3246 /* Process this insn, and each insn linked to this one which must
3247 be immediately output after this insn. */
3250 /* First we kill registers set by this insn, and then we
3251 make registers used by this insn live. This is the opposite
3252 order used above because we are traversing the instructions
3255 /* Strictly speaking, we should scan REG_UNUSED notes and make
3256 every register mentioned there live, however, we will just
3257 kill them again immediately below, so there doesn't seem to
3258 be any reason why we bother to do this. */
3260 /* See if this is the last notice we must take of a register. */
3261 if (GET_CODE (PATTERN (insn)) == SET
3262 || GET_CODE (PATTERN (insn)) == CLOBBER)
3263 sched_note_set (PATTERN (insn), 1);
3264 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
3267 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
3268 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
3269 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
3270 sched_note_set (XVECEXP (PATTERN (insn), 0, j), 1);
3273 /* This code keeps life analysis information up to date. */
3274 if (GET_CODE (insn) == CALL_INSN)
3276 register struct sometimes *p;
3278 /* A call kills all call used registers that are not
3279 global or fixed, except for those mentioned in the call
3280 pattern which will be made live again later. */
3281 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3282 if (call_used_regs[i] && ! global_regs[i]
3285 CLEAR_REGNO_REG_SET (bb_live_regs, i);
3286 SET_REGNO_REG_SET (bb_dead_regs, i);
3289 /* Regs live at the time of a call instruction must not
3290 go in a register clobbered by calls. Record this for
3291 all regs now live. Note that insns which are born or
3292 die in a call do not cross a call, so this must be done
3293 after the killings (above) and before the births
3295 p = regs_sometimes_live;
3296 for (i = 0; i < sometimes_max; i++, p++)
3297 if (REGNO_REG_SET_P (bb_live_regs, p->regno))
3298 p->calls_crossed += 1;
3301 /* Make every register used live, and add REG_DEAD notes for
3302 registers which were not live before we started. */
3303 attach_deaths_insn (insn);
3305 /* Find registers now made live by that instruction. */
3306 EXECUTE_IF_AND_COMPL_IN_REG_SET (bb_live_regs, old_live_regs, 0, i,
3309 = new_sometimes_live (regs_sometimes_live,
3312 IOR_REG_SET (old_live_regs, bb_live_regs);
3314 /* Count lengths of all regs we are worrying about now,
3315 and handle registers no longer live. */
3317 for (i = 0; i < sometimes_max; i++)
3319 register struct sometimes *p = ®s_sometimes_live[i];
3320 int regno = p->regno;
3322 p->live_length += 1;
3324 if (!REGNO_REG_SET_P (bb_live_regs, p->regno))
3326 /* This is the end of one of this register's lifetime
3327 segments. Save the lifetime info collected so far,
3328 and clear its bit in the old_live_regs entry. */
3329 sched_reg_live_length[regno] += p->live_length;
3330 sched_reg_n_calls_crossed[regno] += p->calls_crossed;
3331 CLEAR_REGNO_REG_SET (old_live_regs, p->regno);
3333 /* Delete the reg_sometimes_live entry for this reg by
3334 copying the last entry over top of it. */
3335 *p = regs_sometimes_live[--sometimes_max];
3336 /* ...and decrement i so that this newly copied entry
3337 will be processed. */
3343 insn = PREV_INSN (insn);
3345 while (SCHED_GROUP_P (link));
3347 /* Set INSN back to the insn we are scheduling now. */
3351 /* Schedule INSN. Remove it from the ready list. */
3356 NEXT_INSN (insn) = last;
3357 PREV_INSN (last) = insn;
3359 /* Everything that precedes INSN now either becomes "ready", if
3360 it can execute immediately before INSN, or "pending", if
3361 there must be a delay. Give INSN high enough priority that
3362 at least one (maybe more) reg-killing insns can be launched
3363 ahead of all others. Mark INSN as scheduled by changing its
3365 INSN_PRIORITY (insn) = LAUNCH_PRIORITY;
3366 new_ready = schedule_insn (insn, ready, n_ready, clock);
3367 INSN_PRIORITY (insn) = DONE_PRIORITY;
3369 /* Schedule all prior insns that must not be moved. */
3370 if (SCHED_GROUP_P (insn))
3372 /* Disable these insns from being launched, in case one of the
3373 insns in the group has a dependency on an earlier one. */
3375 while (SCHED_GROUP_P (link))
3377 /* Disable these insns from being launched by anybody. */
3378 link = PREV_INSN (link);
3379 INSN_REF_COUNT (link) = 0;
3382 /* Now handle each group insn like the main insn was handled
3385 while (SCHED_GROUP_P (link))
3387 link = PREV_INSN (link);
3391 /* ??? Why don't we set LAUNCH_PRIORITY here? */
3392 new_ready = schedule_insn (link, ready, new_ready, clock);
3393 INSN_PRIORITY (link) = DONE_PRIORITY;
3397 /* Put back NOTE_INSN_SETJMP,
3398 NOTE_INSN_{LOOP,EHREGION}_{BEGIN,END} notes. */
3400 /* To prime the loop. We need to handle INSN and all the insns in the
3402 last = NEXT_INSN (insn);
3405 insn = PREV_INSN (last);
3407 /* Maintain a valid chain so emit_note_before works.
3408 This is necessary because PREV_INSN (insn) isn't valid
3409 (if ! SCHED_GROUP_P) and if it points to an insn already
3410 scheduled, a circularity will result. */
3411 if (! SCHED_GROUP_P (insn))
3413 NEXT_INSN (prev_head) = insn;
3414 PREV_INSN (insn) = prev_head;
3417 last = reemit_notes (insn, insn);
3419 while (SCHED_GROUP_P (insn));
3424 if (reload_completed == 0)
3425 finish_sometimes_live (regs_sometimes_live, sometimes_max);
3427 /* HEAD is now the first insn in the chain of insns that
3428 been scheduled by the loop above.
3429 TAIL is the last of those insns. */
3432 /* NOTE_LIST is the end of a chain of notes previously found
3433 among the insns. Insert them at the beginning of the insns. */
3436 rtx note_head = note_list;
3437 while (PREV_INSN (note_head))
3438 note_head = PREV_INSN (note_head);
3440 PREV_INSN (head) = note_list;
3441 NEXT_INSN (note_list) = head;
3445 /* There should be no REG_DEAD notes leftover at the end.
3446 In practice, this can occur as the result of bugs in flow, combine.c,
3447 and/or sched.c. The values of the REG_DEAD notes remaining are
3448 meaningless, because dead_notes is just used as a free list. */
3450 if (dead_notes != 0)
3454 if (new_needs & NEED_HEAD)
3455 BLOCK_HEAD (b) = head;
3456 PREV_INSN (head) = prev_head;
3457 NEXT_INSN (prev_head) = head;
3459 if (new_needs & NEED_TAIL)
3460 BLOCK_END (b) = tail;
3461 NEXT_INSN (tail) = next_tail;
3462 PREV_INSN (next_tail) = tail;
3464 /* Restore the line-number notes of each insn. */
3465 if (write_symbols != NO_DEBUG)
3467 rtx line, note, prev, new;
3470 head = BLOCK_HEAD (b);
3471 next_tail = NEXT_INSN (BLOCK_END (b));
3473 /* Determine the current line-number. We want to know the current
3474 line number of the first insn of the block here, in case it is
3475 different from the true line number that was saved earlier. If
3476 different, then we need a line number note before the first insn
3477 of this block. If it happens to be the same, then we don't want to
3478 emit another line number note here. */
3479 for (line = head; line; line = PREV_INSN (line))
3480 if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
3483 /* Walk the insns keeping track of the current line-number and inserting
3484 the line-number notes as needed. */
3485 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
3486 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
3488 /* This used to emit line number notes before every non-deleted note.
3489 However, this confuses a debugger, because line notes not separated
3490 by real instructions all end up at the same address. I can find no
3491 use for line number notes before other notes, so none are emitted. */
3492 else if (GET_CODE (insn) != NOTE
3493 && (note = LINE_NOTE (insn)) != 0
3496 || NOTE_LINE_NUMBER (note) != NOTE_LINE_NUMBER (line)
3497 || NOTE_SOURCE_FILE (note) != NOTE_SOURCE_FILE (line)))
3500 prev = PREV_INSN (insn);
3501 if (LINE_NOTE (note))
3503 /* Re-use the original line-number note. */
3504 LINE_NOTE (note) = 0;
3505 PREV_INSN (note) = prev;
3506 NEXT_INSN (prev) = note;
3507 PREV_INSN (insn) = note;
3508 NEXT_INSN (note) = insn;
3513 new = emit_note_after (NOTE_LINE_NUMBER (note), prev);
3514 NOTE_SOURCE_FILE (new) = NOTE_SOURCE_FILE (note);
3515 RTX_INTEGRATED_P (new) = RTX_INTEGRATED_P (note);
3519 fprintf (file, ";; added %d line-number notes\n", notes);
3524 fprintf (file, ";; total time = %d\n;; new basic block head = %d\n;; new basic block end = %d\n\n",
3525 clock, INSN_UID (BLOCK_HEAD (b)), INSN_UID (BLOCK_END (b)));
3528 /* Yow! We're done! */
3529 free_pending_lists ();
3532 FREE_REG_SET (reg_pending_sets);
3533 FREE_REG_SET (old_live_regs);
3538 /* Subroutine of update_flow_info. Determines whether any new REG_NOTEs are
3539 needed for the hard register mentioned in the note. This can happen
3540 if the reference to the hard register in the original insn was split into
3541 several smaller hard register references in the split insns. */
3544 split_hard_reg_notes (note, first, last)
3545 rtx note, first, last;
3547 rtx reg, temp, link;
3548 int n_regs, i, new_reg;
3551 /* Assume that this is a REG_DEAD note. */
3552 if (REG_NOTE_KIND (note) != REG_DEAD)
3555 reg = XEXP (note, 0);
3557 n_regs = HARD_REGNO_NREGS (REGNO (reg), GET_MODE (reg));
3559 for (i = 0; i < n_regs; i++)
3561 new_reg = REGNO (reg) + i;
3563 /* Check for references to new_reg in the split insns. */
3564 for (insn = last; ; insn = PREV_INSN (insn))
3566 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
3567 && (temp = regno_use_in (new_reg, PATTERN (insn))))
3569 /* Create a new reg dead note here. */
3570 link = rtx_alloc (EXPR_LIST);
3571 PUT_REG_NOTE_KIND (link, REG_DEAD);
3572 XEXP (link, 0) = temp;
3573 XEXP (link, 1) = REG_NOTES (insn);
3574 REG_NOTES (insn) = link;
3576 /* If killed multiple registers here, then add in the excess. */
3577 i += HARD_REGNO_NREGS (REGNO (temp), GET_MODE (temp)) - 1;
3581 /* It isn't mentioned anywhere, so no new reg note is needed for
3589 /* Subroutine of update_flow_info. Determines whether a SET or CLOBBER in an
3590 insn created by splitting needs a REG_DEAD or REG_UNUSED note added. */
3593 new_insn_dead_notes (pat, insn, last, orig_insn)
3594 rtx pat, insn, last, orig_insn;
3598 /* PAT is either a CLOBBER or a SET here. */
3599 dest = XEXP (pat, 0);
3601 while (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SUBREG
3602 || GET_CODE (dest) == STRICT_LOW_PART
3603 || GET_CODE (dest) == SIGN_EXTRACT)
3604 dest = XEXP (dest, 0);
3606 if (GET_CODE (dest) == REG)
3608 /* If the original insn already used this register, we may not add new
3609 notes for it. One example for a split that needs this test is
3610 when a multi-word memory access with register-indirect addressing
3611 is split into multiple memory accesses with auto-increment and
3612 one adjusting add instruction for the address register. */
3613 if (reg_referenced_p (dest, PATTERN (orig_insn)))
3615 for (tem = last; tem != insn; tem = PREV_INSN (tem))
3617 if (GET_RTX_CLASS (GET_CODE (tem)) == 'i'
3618 && reg_overlap_mentioned_p (dest, PATTERN (tem))
3619 && (set = single_set (tem)))
3621 rtx tem_dest = SET_DEST (set);
3623 while (GET_CODE (tem_dest) == ZERO_EXTRACT
3624 || GET_CODE (tem_dest) == SUBREG
3625 || GET_CODE (tem_dest) == STRICT_LOW_PART
3626 || GET_CODE (tem_dest) == SIGN_EXTRACT)
3627 tem_dest = XEXP (tem_dest, 0);
3629 if (! rtx_equal_p (tem_dest, dest))
3631 /* Use the same scheme as combine.c, don't put both REG_DEAD
3632 and REG_UNUSED notes on the same insn. */
3633 if (! find_regno_note (tem, REG_UNUSED, REGNO (dest))
3634 && ! find_regno_note (tem, REG_DEAD, REGNO (dest)))
3636 rtx note = rtx_alloc (EXPR_LIST);
3637 PUT_REG_NOTE_KIND (note, REG_DEAD);
3638 XEXP (note, 0) = dest;
3639 XEXP (note, 1) = REG_NOTES (tem);
3640 REG_NOTES (tem) = note;
3642 /* The reg only dies in one insn, the last one that uses
3646 else if (reg_overlap_mentioned_p (dest, SET_SRC (set)))
3647 /* We found an instruction that both uses the register,
3648 and sets it, so no new REG_NOTE is needed for this set. */
3652 /* If this is a set, it must die somewhere, unless it is the dest of
3653 the original insn, and hence is live after the original insn. Abort
3654 if it isn't supposed to be live after the original insn.
3656 If this is a clobber, then just add a REG_UNUSED note. */
3659 int live_after_orig_insn = 0;
3660 rtx pattern = PATTERN (orig_insn);
3663 if (GET_CODE (pat) == CLOBBER)
3665 rtx note = rtx_alloc (EXPR_LIST);
3666 PUT_REG_NOTE_KIND (note, REG_UNUSED);
3667 XEXP (note, 0) = dest;
3668 XEXP (note, 1) = REG_NOTES (insn);
3669 REG_NOTES (insn) = note;
3673 /* The original insn could have multiple sets, so search the
3674 insn for all sets. */
3675 if (GET_CODE (pattern) == SET)
3677 if (reg_overlap_mentioned_p (dest, SET_DEST (pattern)))
3678 live_after_orig_insn = 1;
3680 else if (GET_CODE (pattern) == PARALLEL)
3682 for (i = 0; i < XVECLEN (pattern, 0); i++)
3683 if (GET_CODE (XVECEXP (pattern, 0, i)) == SET
3684 && reg_overlap_mentioned_p (dest,
3685 SET_DEST (XVECEXP (pattern,
3687 live_after_orig_insn = 1;
3690 if (! live_after_orig_insn)
3696 /* Subroutine of update_flow_info. Update the value of reg_n_sets for all
3697 registers modified by X. INC is -1 if the containing insn is being deleted,
3698 and is 1 if the containing insn is a newly generated insn. */
3701 update_n_sets (x, inc)
3705 rtx dest = SET_DEST (x);
3707 while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
3708 || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
3709 dest = SUBREG_REG (dest);
3711 if (GET_CODE (dest) == REG)
3713 int regno = REGNO (dest);
3715 if (regno < FIRST_PSEUDO_REGISTER)
3718 int endregno = regno + HARD_REGNO_NREGS (regno, GET_MODE (dest));
3720 for (i = regno; i < endregno; i++)
3721 REG_N_SETS (i) += inc;
3724 REG_N_SETS (regno) += inc;
3728 /* Updates all flow-analysis related quantities (including REG_NOTES) for
3729 the insns from FIRST to LAST inclusive that were created by splitting
3730 ORIG_INSN. NOTES are the original REG_NOTES. */
3733 update_flow_info (notes, first, last, orig_insn)
3740 rtx orig_dest, temp;
3743 /* Get and save the destination set by the original insn. */
3745 orig_dest = single_set (orig_insn);
3747 orig_dest = SET_DEST (orig_dest);
3749 /* Move REG_NOTES from the original insn to where they now belong. */
3751 for (note = notes; note; note = next)
3753 next = XEXP (note, 1);
3754 switch (REG_NOTE_KIND (note))
3758 /* Move these notes from the original insn to the last new insn where
3759 the register is now set. */
3761 for (insn = last; ; insn = PREV_INSN (insn))
3763 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
3764 && reg_mentioned_p (XEXP (note, 0), PATTERN (insn)))
3766 /* If this note refers to a multiple word hard register, it
3767 may have been split into several smaller hard register
3768 references, so handle it specially. */
3769 temp = XEXP (note, 0);
3770 if (REG_NOTE_KIND (note) == REG_DEAD
3771 && GET_CODE (temp) == REG
3772 && REGNO (temp) < FIRST_PSEUDO_REGISTER
3773 && HARD_REGNO_NREGS (REGNO (temp), GET_MODE (temp)) > 1)
3774 split_hard_reg_notes (note, first, last);
3777 XEXP (note, 1) = REG_NOTES (insn);
3778 REG_NOTES (insn) = note;
3781 /* Sometimes need to convert REG_UNUSED notes to REG_DEAD
3783 /* ??? This won't handle multiple word registers correctly,
3784 but should be good enough for now. */
3785 if (REG_NOTE_KIND (note) == REG_UNUSED
3786 && GET_CODE (XEXP (note, 0)) != SCRATCH
3787 && ! dead_or_set_p (insn, XEXP (note, 0)))
3788 PUT_REG_NOTE_KIND (note, REG_DEAD);
3790 /* The reg only dies in one insn, the last one that uses
3794 /* It must die somewhere, fail it we couldn't find where it died.
3796 If this is a REG_UNUSED note, then it must be a temporary
3797 register that was not needed by this instantiation of the
3798 pattern, so we can safely ignore it. */
3801 if (REG_NOTE_KIND (note) != REG_UNUSED)
3810 /* If the insn that set the register to 0 was deleted, this
3811 note cannot be relied on any longer. The destination might
3812 even have been moved to memory.
3813 This was observed for SH4 with execute/920501-6.c compilation,
3814 -O2 -fomit-frame-pointer -finline-functions . */
3815 if (GET_CODE (XEXP (note, 0)) == NOTE
3816 || INSN_DELETED_P (XEXP (note, 0)))
3818 /* This note applies to the dest of the original insn. Find the
3819 first new insn that now has the same dest, and move the note
3825 for (insn = first; ; insn = NEXT_INSN (insn))
3827 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
3828 && (temp = single_set (insn))
3829 && rtx_equal_p (SET_DEST (temp), orig_dest))
3831 XEXP (note, 1) = REG_NOTES (insn);
3832 REG_NOTES (insn) = note;
3833 /* The reg is only zero before one insn, the first that
3837 /* If this note refers to a multiple word hard
3838 register, it may have been split into several smaller
3839 hard register references. We could split the notes,
3840 but simply dropping them is good enough. */
3841 if (GET_CODE (orig_dest) == REG
3842 && REGNO (orig_dest) < FIRST_PSEUDO_REGISTER
3843 && HARD_REGNO_NREGS (REGNO (orig_dest),
3844 GET_MODE (orig_dest)) > 1)
3846 /* It must be set somewhere, fail if we couldn't find where it
3855 /* A REG_EQUIV or REG_EQUAL note on an insn with more than one
3856 set is meaningless. Just drop the note. */
3860 case REG_NO_CONFLICT:
3861 /* These notes apply to the dest of the original insn. Find the last
3862 new insn that now has the same dest, and move the note there. */
3867 for (insn = last; ; insn = PREV_INSN (insn))
3869 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
3870 && (temp = single_set (insn))
3871 && rtx_equal_p (SET_DEST (temp), orig_dest))
3873 XEXP (note, 1) = REG_NOTES (insn);
3874 REG_NOTES (insn) = note;
3875 /* Only put this note on one of the new insns. */
3879 /* The original dest must still be set someplace. Abort if we
3880 couldn't find it. */
3883 /* However, if this note refers to a multiple word hard
3884 register, it may have been split into several smaller
3885 hard register references. We could split the notes,
3886 but simply dropping them is good enough. */
3887 if (GET_CODE (orig_dest) == REG
3888 && REGNO (orig_dest) < FIRST_PSEUDO_REGISTER
3889 && HARD_REGNO_NREGS (REGNO (orig_dest),
3890 GET_MODE (orig_dest)) > 1)
3892 /* Likewise for multi-word memory references. */
3893 if (GET_CODE (orig_dest) == MEM
3894 && SIZE_FOR_MODE (orig_dest) > MOVE_MAX)
3902 /* Move a REG_LIBCALL note to the first insn created, and update
3903 the corresponding REG_RETVAL note. */
3904 XEXP (note, 1) = REG_NOTES (first);
3905 REG_NOTES (first) = note;
3907 insn = XEXP (note, 0);
3908 note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
3910 XEXP (note, 0) = first;
3913 case REG_EXEC_COUNT:
3914 /* Move a REG_EXEC_COUNT note to the first insn created. */
3915 XEXP (note, 1) = REG_NOTES (first);
3916 REG_NOTES (first) = note;
3920 /* Move a REG_RETVAL note to the last insn created, and update
3921 the corresponding REG_LIBCALL note. */
3922 XEXP (note, 1) = REG_NOTES (last);
3923 REG_NOTES (last) = note;
3925 insn = XEXP (note, 0);
3926 note = find_reg_note (insn, REG_LIBCALL, NULL_RTX);
3928 XEXP (note, 0) = last;
3933 /* This should be moved to whichever instruction is a JUMP_INSN. */
3935 for (insn = last; ; insn = PREV_INSN (insn))
3937 if (GET_CODE (insn) == JUMP_INSN)
3939 XEXP (note, 1) = REG_NOTES (insn);
3940 REG_NOTES (insn) = note;
3941 /* Only put this note on one of the new insns. */
3944 /* Fail if we couldn't find a JUMP_INSN. */
3951 /* reload sometimes leaves obsolete REG_INC notes around. */
3952 if (reload_completed)
3954 /* This should be moved to whichever instruction now has the
3955 increment operation. */
3959 /* Should be moved to the new insn(s) which use the label. */
3960 for (insn = first; insn != NEXT_INSN (last); insn = NEXT_INSN (insn))
3961 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
3962 && reg_mentioned_p (XEXP (note, 0), PATTERN (insn)))
3963 REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_LABEL,
3970 /* These two notes will never appear until after reorg, so we don't
3971 have to handle them here. */
3977 /* Each new insn created, except the last, has a new set. If the destination
3978 is a register, then this reg is now live across several insns, whereas
3979 previously the dest reg was born and died within the same insn. To
3980 reflect this, we now need a REG_DEAD note on the insn where this
3983 Similarly, the new insns may have clobbers that need REG_UNUSED notes. */
3985 for (insn = first; insn != last; insn = NEXT_INSN (insn))
3990 pat = PATTERN (insn);
3991 if (GET_CODE (pat) == SET || GET_CODE (pat) == CLOBBER)
3992 new_insn_dead_notes (pat, insn, last, orig_insn);
3993 else if (GET_CODE (pat) == PARALLEL)
3995 for (i = 0; i < XVECLEN (pat, 0); i++)
3996 if (GET_CODE (XVECEXP (pat, 0, i)) == SET
3997 || GET_CODE (XVECEXP (pat, 0, i)) == CLOBBER)
3998 new_insn_dead_notes (XVECEXP (pat, 0, i), insn, last, orig_insn);
4002 /* If any insn, except the last, uses the register set by the last insn,
4003 then we need a new REG_DEAD note on that insn. In this case, there
4004 would not have been a REG_DEAD note for this register in the original
4005 insn because it was used and set within one insn. */
4007 set = single_set (last);
4010 rtx dest = SET_DEST (set);
4012 while (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SUBREG
4013 || GET_CODE (dest) == STRICT_LOW_PART
4014 || GET_CODE (dest) == SIGN_EXTRACT)
4015 dest = XEXP (dest, 0);
4017 if (GET_CODE (dest) == REG
4018 /* Global registers are always live, so the code below does not
4020 && (REGNO (dest) >= FIRST_PSEUDO_REGISTER
4021 || ! global_regs[REGNO (dest)]))
4023 rtx stop_insn = PREV_INSN (first);
4025 /* If the last insn uses the register that it is setting, then
4026 we don't want to put a REG_DEAD note there. Search backwards
4027 to find the first insn that sets but does not use DEST. */
4030 if (reg_overlap_mentioned_p (dest, SET_SRC (set)))
4032 for (insn = PREV_INSN (insn); insn != first;
4033 insn = PREV_INSN (insn))
4035 if ((set = single_set (insn))
4036 && reg_mentioned_p (dest, SET_DEST (set))
4037 && ! reg_overlap_mentioned_p (dest, SET_SRC (set)))
4042 /* Now find the first insn that uses but does not set DEST. */
4044 for (insn = PREV_INSN (insn); insn != stop_insn;
4045 insn = PREV_INSN (insn))
4047 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
4048 && reg_mentioned_p (dest, PATTERN (insn))
4049 && (set = single_set (insn)))
4051 rtx insn_dest = SET_DEST (set);
4053 while (GET_CODE (insn_dest) == ZERO_EXTRACT
4054 || GET_CODE (insn_dest) == SUBREG
4055 || GET_CODE (insn_dest) == STRICT_LOW_PART
4056 || GET_CODE (insn_dest) == SIGN_EXTRACT)
4057 insn_dest = XEXP (insn_dest, 0);
4059 if (insn_dest != dest)
4061 note = rtx_alloc (EXPR_LIST);
4062 PUT_REG_NOTE_KIND (note, REG_DEAD);
4063 XEXP (note, 0) = dest;
4064 XEXP (note, 1) = REG_NOTES (insn);
4065 REG_NOTES (insn) = note;
4066 /* The reg only dies in one insn, the last one
4075 /* If the original dest is modifying a multiple register target, and the
4076 original instruction was split such that the original dest is now set
4077 by two or more SUBREG sets, then the split insns no longer kill the
4078 destination of the original insn.
4080 In this case, if there exists an instruction in the same basic block,
4081 before the split insn, which uses the original dest, and this use is
4082 killed by the original insn, then we must remove the REG_DEAD note on
4083 this insn, because it is now superfluous.
4085 This does not apply when a hard register gets split, because the code
4086 knows how to handle overlapping hard registers properly. */
4087 if (orig_dest && GET_CODE (orig_dest) == REG)
4089 int found_orig_dest = 0;
4090 int found_split_dest = 0;
4092 for (insn = first; ; insn = NEXT_INSN (insn))
4094 rtx pat = PATTERN (insn);
4095 int i = GET_CODE (pat) == PARALLEL ? XVECLEN (pat, 0) : 0;
4099 if (GET_CODE (set) == SET)
4101 if (GET_CODE (SET_DEST (set)) == REG
4102 && REGNO (SET_DEST (set)) == REGNO (orig_dest))
4104 found_orig_dest = 1;
4107 else if (GET_CODE (SET_DEST (set)) == SUBREG
4108 && SUBREG_REG (SET_DEST (set)) == orig_dest)
4110 found_split_dest = 1;
4116 set = XVECEXP (pat, 0, i);
4123 if (found_split_dest)
4125 /* Search backwards from FIRST, looking for the first insn that uses
4126 the original dest. Stop if we pass a CODE_LABEL or a JUMP_INSN.
4127 If we find an insn, and it has a REG_DEAD note, then delete the
4130 for (insn = first; insn; insn = PREV_INSN (insn))
4132 if (GET_CODE (insn) == CODE_LABEL
4133 || GET_CODE (insn) == JUMP_INSN)
4135 else if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
4136 && reg_mentioned_p (orig_dest, insn))
4138 note = find_regno_note (insn, REG_DEAD, REGNO (orig_dest));
4140 remove_note (insn, note);
4144 else if (! found_orig_dest)
4148 /* Should never reach here for a pseudo reg. */
4149 if (REGNO (orig_dest) >= FIRST_PSEUDO_REGISTER)
4152 /* This can happen for a hard register, if the splitter
4153 does not bother to emit instructions which would be no-ops.
4154 We try to verify that this is the case by checking to see if
4155 the original instruction uses all of the registers that it
4156 set. This case is OK, because deleting a no-op can not affect
4157 REG_DEAD notes on other insns. If this is not the case, then
4160 regno = REGNO (orig_dest);
4161 for (i = HARD_REGNO_NREGS (regno, GET_MODE (orig_dest)) - 1;
4163 if (! refers_to_regno_p (regno + i, regno + i + 1, orig_insn,
4171 /* Update reg_n_sets. This is necessary to prevent local alloc from
4172 converting REG_EQUAL notes to REG_EQUIV when splitting has modified
4173 a reg from set once to set multiple times. */
4176 rtx x = PATTERN (orig_insn);
4177 RTX_CODE code = GET_CODE (x);
4179 if (code == SET || code == CLOBBER)
4180 update_n_sets (x, -1);
4181 else if (code == PARALLEL)
4184 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
4186 code = GET_CODE (XVECEXP (x, 0, i));
4187 if (code == SET || code == CLOBBER)
4188 update_n_sets (XVECEXP (x, 0, i), -1);
4192 for (insn = first; ; insn = NEXT_INSN (insn))
4195 code = GET_CODE (x);
4197 if (code == SET || code == CLOBBER)
4198 update_n_sets (x, 1);
4199 else if (code == PARALLEL)
4202 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
4204 code = GET_CODE (XVECEXP (x, 0, i));
4205 if (code == SET || code == CLOBBER)
4206 update_n_sets (XVECEXP (x, 0, i), 1);
4216 /* The one entry point in this file. DUMP_FILE is the dump file for
4220 schedule_insns (dump_file)
4223 int max_uid = MAX_INSNS_PER_SPLIT * (get_max_uid () + 1);
4227 /* Taking care of this degenerate case makes the rest of
4228 this code simpler. */
4229 if (n_basic_blocks == 0)
4232 /* Create an insn here so that we can hang dependencies off of it later. */
4233 sched_before_next_call
4234 = gen_rtx_INSN (VOIDmode, 0, NULL_RTX, NULL_RTX,
4235 NULL_RTX, 0, NULL_RTX, NULL_RTX);
4237 /* Initialize the unused_*_lists. We can't use the ones left over from
4238 the previous function, because gcc has freed that memory. We can use
4239 the ones left over from the first sched pass in the second pass however,
4240 so only clear them on the first sched pass. The first pass is before
4241 reload if flag_schedule_insns is set, otherwise it is afterwards. */
4243 if (reload_completed == 0 || ! flag_schedule_insns)
4245 unused_insn_list = 0;
4246 unused_expr_list = 0;
4249 /* We create no insns here, only reorder them, so we
4250 remember how far we can cut back the stack on exit. */
4252 /* Allocate data for this pass. See comments, above,
4253 for what these vectors do.
4255 We use xmalloc instead of alloca, because max_uid can be very large
4256 when there is a lot of function inlining. If we used alloca, we could
4257 exceed stack limits on some hosts for some inputs. */
4258 insn_luid = (int *) xmalloc (max_uid * sizeof (int));
4259 insn_priority = (int *) xmalloc (max_uid * sizeof (int));
4260 insn_tick = (int *) xmalloc (max_uid * sizeof (int));
4261 insn_costs = (short *) xmalloc (max_uid * sizeof (short));
4262 insn_units = (short *) xmalloc (max_uid * sizeof (short));
4263 insn_blockage = (unsigned int *) xmalloc (max_uid * sizeof (unsigned int));
4264 insn_ref_count = (int *) xmalloc (max_uid * sizeof (int));
4266 if (reload_completed == 0)
4268 sched_reg_n_calls_crossed = (int *) alloca (max_regno * sizeof (int));
4269 sched_reg_live_length = (int *) alloca (max_regno * sizeof (int));
4270 bb_dead_regs = ALLOCA_REG_SET ();
4271 bb_live_regs = ALLOCA_REG_SET ();
4272 bzero ((char *) sched_reg_n_calls_crossed, max_regno * sizeof (int));
4273 bzero ((char *) sched_reg_live_length, max_regno * sizeof (int));
4277 sched_reg_n_calls_crossed = 0;
4278 sched_reg_live_length = 0;
4282 init_alias_analysis ();
4284 if (write_symbols != NO_DEBUG)
4288 line_note = (rtx *) xmalloc (max_uid * sizeof (rtx));
4289 bzero ((char *) line_note, max_uid * sizeof (rtx));
4290 line_note_head = (rtx *) alloca (n_basic_blocks * sizeof (rtx));
4291 bzero ((char *) line_note_head, n_basic_blocks * sizeof (rtx));
4293 /* Determine the line-number at the start of each basic block.
4294 This must be computed and saved now, because after a basic block's
4295 predecessor has been scheduled, it is impossible to accurately
4296 determine the correct line number for the first insn of the block. */
4298 for (b = 0; b < n_basic_blocks; b++)
4299 for (line = BLOCK_HEAD (b); line; line = PREV_INSN (line))
4300 if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
4302 line_note_head[b] = line;
4307 bzero ((char *) insn_luid, max_uid * sizeof (int));
4308 bzero ((char *) insn_priority, max_uid * sizeof (int));
4309 bzero ((char *) insn_tick, max_uid * sizeof (int));
4310 bzero ((char *) insn_costs, max_uid * sizeof (short));
4311 bzero ((char *) insn_units, max_uid * sizeof (short));
4312 bzero ((char *) insn_blockage, max_uid * sizeof (unsigned int));
4313 bzero ((char *) insn_ref_count, max_uid * sizeof (int));
4315 /* Schedule each basic block, block by block. */
4317 /* ??? Add a NOTE after the last insn of the last basic block. It is not
4318 known why this is done. */
4319 /* ??? Perhaps it's done to ensure NEXT_TAIL in schedule_block is a
4322 insn = BLOCK_END (n_basic_blocks-1);
4323 if (NEXT_INSN (insn) == 0
4324 || (GET_CODE (insn) != NOTE
4325 && GET_CODE (insn) != CODE_LABEL
4326 /* Don't emit a NOTE if it would end up between an unconditional
4327 jump and a BARRIER. */
4328 && ! (GET_CODE (insn) == JUMP_INSN
4329 && GET_CODE (NEXT_INSN (insn)) == BARRIER)))
4330 emit_note_after (NOTE_INSN_DELETED, BLOCK_END (n_basic_blocks-1));
4332 for (b = 0; b < n_basic_blocks; b++)
4336 split_block_insns (b, reload_completed == 0 || ! flag_schedule_insns);
4338 schedule_block (b, dump_file);
4345 /* Reposition the prologue and epilogue notes in case we moved the
4346 prologue/epilogue insns. */
4347 if (reload_completed)
4348 reposition_prologue_and_epilogue_notes (get_insns ());
4350 if (write_symbols != NO_DEBUG)
4353 rtx insn = get_insns ();
4354 int active_insn = 0;
4357 /* Walk the insns deleting redundant line-number notes. Many of these
4358 are already present. The remainder tend to occur at basic
4359 block boundaries. */
4360 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
4361 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
4363 /* If there are no active insns following, INSN is redundant. */
4364 if (active_insn == 0)
4367 NOTE_SOURCE_FILE (insn) = 0;
4368 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
4370 /* If the line number is unchanged, LINE is redundant. */
4372 && NOTE_LINE_NUMBER (line) == NOTE_LINE_NUMBER (insn)
4373 && NOTE_SOURCE_FILE (line) == NOTE_SOURCE_FILE (insn))
4376 NOTE_SOURCE_FILE (line) = 0;
4377 NOTE_LINE_NUMBER (line) = NOTE_INSN_DELETED;
4384 else if (! ((GET_CODE (insn) == NOTE
4385 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED)
4386 || (GET_CODE (insn) == INSN
4387 && (GET_CODE (PATTERN (insn)) == USE
4388 || GET_CODE (PATTERN (insn)) == CLOBBER))))
4391 if (dump_file && notes)
4392 fprintf (dump_file, ";; deleted %d line-number notes\n", notes);
4395 if (reload_completed == 0)
4398 for (regno = 0; regno < max_regno; regno++)
4399 if (sched_reg_live_length[regno])
4403 if (REG_LIVE_LENGTH (regno) > sched_reg_live_length[regno])
4405 ";; register %d life shortened from %d to %d\n",
4406 regno, REG_LIVE_LENGTH (regno),
4407 sched_reg_live_length[regno]);
4408 /* Negative values are special; don't overwrite the current
4409 reg_live_length value if it is negative. */
4410 else if (REG_LIVE_LENGTH (regno) < sched_reg_live_length[regno]
4411 && REG_LIVE_LENGTH (regno) >= 0)
4413 ";; register %d life extended from %d to %d\n",
4414 regno, REG_LIVE_LENGTH (regno),
4415 sched_reg_live_length[regno]);
4417 if (! REG_N_CALLS_CROSSED (regno)
4418 && sched_reg_n_calls_crossed[regno])
4420 ";; register %d now crosses calls\n", regno);
4421 else if (REG_N_CALLS_CROSSED (regno)
4422 && ! sched_reg_n_calls_crossed[regno]
4423 && REG_BASIC_BLOCK (regno) != REG_BLOCK_GLOBAL)
4425 ";; register %d no longer crosses calls\n", regno);
4428 /* Negative values are special; don't overwrite the current
4429 reg_live_length value if it is negative. */
4430 if (REG_LIVE_LENGTH (regno) >= 0)
4431 REG_LIVE_LENGTH (regno) = sched_reg_live_length[regno];
4433 /* We can't change the value of reg_n_calls_crossed to zero for
4434 pseudos which are live in more than one block.
4436 This is because combine might have made an optimization which
4437 invalidated basic_block_live_at_start and reg_n_calls_crossed,
4438 but it does not update them. If we update reg_n_calls_crossed
4439 here, the two variables are now inconsistent, and this might
4440 confuse the caller-save code into saving a register that doesn't
4441 need to be saved. This is only a problem when we zero calls
4442 crossed for a pseudo live in multiple basic blocks.
4444 Alternatively, we could try to correctly update basic block live
4445 at start here in sched, but that seems complicated. */
4446 if (sched_reg_n_calls_crossed[regno]
4447 || REG_BASIC_BLOCK (regno) != REG_BLOCK_GLOBAL)
4448 REG_N_CALLS_CROSSED (regno) = sched_reg_n_calls_crossed[regno];
4453 free (insn_priority);
4457 free (insn_blockage);
4458 free (insn_ref_count);
4460 if (write_symbols != NO_DEBUG)
4463 if (reload_completed == 0)
4465 FREE_REG_SET (bb_dead_regs);
4466 FREE_REG_SET (bb_live_regs);
4470 #endif /* INSN_SCHEDULING */