![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to sched.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Apple XNU] / GNUtools / cc|
Return to sched.c CVS log | Up to [Apple XNU] / GNUtools / cc |
1.1 root 1: /* Instruction scheduling pass.
2: Copyright (C) 1992, 1993 Free Software Foundation, Inc.
3: Contributed by Michael Tiemann ([email protected])
4: Enhanced by, and currently maintained by, Jim Wilson ([email protected])
5:
6: This file is part of GNU CC.
7:
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)
11: any later version.
12:
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.
17:
18: You should have received a copy of the GNU General Public License
19: along with GNU CC; see the file COPYING. If not, write to
20: the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
21:
22: /* Instruction scheduling pass.
23:
24: This pass implements list scheduling within basic blocks. It is
25: run after flow analysis, but before register allocation. The
26: scheduler works as follows:
27:
28: We compute insn priorities based on data dependencies. Flow
29: analysis only creates a fraction of the data-dependencies we must
30: observe: namely, only those dependencies which the combiner can be
31: expected to use. For this pass, we must therefore create the
32: remaining dependencies we need to observe: register dependencies,
33: memory dependencies, dependencies to keep function calls in order,
34: and the dependence between a conditional branch and the setting of
35: condition codes are all dealt with here.
36:
37: The scheduler first traverses the data flow graph, starting with
38: the last instruction, and proceeding to the first, assigning
39: values to insn_priority as it goes. This sorts the instructions
40: topologically by data dependence.
41:
42: Once priorities have been established, we order the insns using
43: list scheduling. This works as follows: starting with a list of
44: all the ready insns, and sorted according to priority number, we
45: schedule the insn from the end of the list by placing its
46: predecessors in the list according to their priority order. We
47: consider this insn scheduled by setting the pointer to the "end" of
48: the list to point to the previous insn. When an insn has no
49: predecessors, we either queue it until sufficient time has elapsed
50: or add it to the ready list. As the instructions are scheduled or
51: when stalls are introduced, the queue advances and dumps insns into
52: the ready list. When all insns down to the lowest priority have
53: been scheduled, the critical path of the basic block has been made
54: as short as possible. The remaining insns are then scheduled in
55: remaining slots.
56:
57: Function unit conflicts are resolved during reverse list scheduling
58: by tracking the time when each insn is committed to the schedule
59: and from that, the time the function units it uses must be free.
60: As insns on the ready list are considered for scheduling, those
61: that would result in a blockage of the already committed insns are
62: queued until no blockage will result. Among the remaining insns on
63: the ready list to be considered, the first one with the largest
64: potential for causing a subsequent blockage is chosen.
65:
66: The following list shows the order in which we want to break ties
67: among insns in the ready list:
68:
69: 1. choose insn with lowest conflict cost, ties broken by
70: 2. choose insn with the longest path to end of bb, ties broken by
71: 3. choose insn that kills the most registers, ties broken by
72: 4. choose insn that conflicts with the most ready insns, or finally
73: 5. choose insn with lowest UID.
74:
75: Memory references complicate matters. Only if we can be certain
76: that memory references are not part of the data dependency graph
77: (via true, anti, or output dependence), can we move operations past
78: memory references. To first approximation, reads can be done
79: independently, while writes introduce dependencies. Better
80: approximations will yield fewer dependencies.
81:
82: Dependencies set up by memory references are treated in exactly the
83: same way as other dependencies, by using LOG_LINKS.
84:
85: Having optimized the critical path, we may have also unduly
86: extended the lifetimes of some registers. If an operation requires
87: that constants be loaded into registers, it is certainly desirable
88: to load those constants as early as necessary, but no earlier.
89: I.e., it will not do to load up a bunch of registers at the
90: beginning of a basic block only to use them at the end, if they
91: could be loaded later, since this may result in excessive register
92: utilization.
93:
94: Note that since branches are never in basic blocks, but only end
95: basic blocks, this pass will not do any branch scheduling. But
96: that is ok, since we can use GNU's delayed branch scheduling
97: pass to take care of this case.
98:
99: Also note that no further optimizations based on algebraic identities
100: are performed, so this pass would be a good one to perform instruction
101: splitting, such as breaking up a multiply instruction into shifts
102: and adds where that is profitable.
103:
104: Given the memory aliasing analysis that this pass should perform,
105: it should be possible to remove redundant stores to memory, and to
106: load values from registers instead of hitting memory.
107:
108: This pass must update information that subsequent passes expect to be
109: correct. Namely: reg_n_refs, reg_n_sets, reg_n_deaths,
110: reg_n_calls_crossed, and reg_live_length. Also, basic_block_head,
111: basic_block_end.
112:
113: The information in the line number notes is carefully retained by this
114: pass. All other NOTE insns are grouped in their same relative order at
115: the beginning of basic blocks that have been scheduled. */
116:
117: #include <stdio.h>
118: #include "config.h"
119: #include "rtl.h"
120: #include "basic-block.h"
121: #include "regs.h"
122: #include "hard-reg-set.h"
123: #include "flags.h"
124: #include "insn-config.h"
125: #include "insn-attr.h"
126:
127: #ifdef INSN_SCHEDULING
128: /* Arrays set up by scheduling for the same respective purposes as
129: similar-named arrays set up by flow analysis. We work with these
130: arrays during the scheduling pass so we can compare values against
131: unscheduled code.
132:
133: Values of these arrays are copied at the end of this pass into the
134: arrays set up by flow analysis. */
135: static short *sched_reg_n_deaths;
136: static int *sched_reg_n_calls_crossed;
137: static int *sched_reg_live_length;
138:
139: /* Element N is the next insn that sets (hard or pseudo) register
140: N within the current basic block; or zero, if there is no
141: such insn. Needed for new registers which may be introduced
142: by splitting insns. */
143: static rtx *reg_last_uses;
144: static rtx *reg_last_sets;
145:
146: /* Vector indexed by INSN_UID giving the original ordering of the insns. */
147: static int *insn_luid;
148: #define INSN_LUID(INSN) (insn_luid[INSN_UID (INSN)])
149:
150: /* Vector indexed by INSN_UID giving each instruction a priority. */
151: static int *insn_priority;
152: #define INSN_PRIORITY(INSN) (insn_priority[INSN_UID (INSN)])
153:
154: static short *insn_costs;
155: #define INSN_COST(INSN) insn_costs[INSN_UID (INSN)]
156:
157: /* Vector indexed by INSN_UID giving an encoding of the function units
158: used. */
159: static short *insn_units;
160: #define INSN_UNIT(INSN) insn_units[INSN_UID (INSN)]
161:
162: /* Vector indexed by INSN_UID giving an encoding of the blockage range
163: function. The unit and the range are encoded. */
164: static unsigned int *insn_blockage;
165: #define INSN_BLOCKAGE(INSN) insn_blockage[INSN_UID (INSN)]
166: #define UNIT_BITS 5
167: #define BLOCKAGE_MASK ((1 << BLOCKAGE_BITS) - 1)
168: #define ENCODE_BLOCKAGE(U,R) \
169: ((((U) << UNIT_BITS) << BLOCKAGE_BITS \
170: | MIN_BLOCKAGE_COST (R)) << BLOCKAGE_BITS \
171: | MAX_BLOCKAGE_COST (R))
172: #define UNIT_BLOCKED(B) ((B) >> (2 * BLOCKAGE_BITS))
173: #define BLOCKAGE_RANGE(B) \
174: (((((B) >> BLOCKAGE_BITS) & BLOCKAGE_MASK) << (HOST_BITS_PER_INT / 2)) \
175: | (B) & BLOCKAGE_MASK)
176:
177: /* Encodings of the `<name>_unit_blockage_range' function. */
178: #define MIN_BLOCKAGE_COST(R) ((R) >> (HOST_BITS_PER_INT / 2))
179: #define MAX_BLOCKAGE_COST(R) ((R) & ((1 << (HOST_BITS_PER_INT / 2)) - 1))
180:
181: #define DONE_PRIORITY -1
182: #define MAX_PRIORITY 0x7fffffff
183: #define TAIL_PRIORITY 0x7ffffffe
184: #define LAUNCH_PRIORITY 0x7f000001
185: #define DONE_PRIORITY_P(INSN) (INSN_PRIORITY (INSN) < 0)
186: #define LOW_PRIORITY_P(INSN) ((INSN_PRIORITY (INSN) & 0x7f000000) == 0)
187:
188: /* Vector indexed by INSN_UID giving number of insns referring to this insn. */
189: static int *insn_ref_count;
190: #define INSN_REF_COUNT(INSN) (insn_ref_count[INSN_UID (INSN)])
191:
192: /* Vector indexed by INSN_UID giving line-number note in effect for each
193: insn. For line-number notes, this indicates whether the note may be
194: reused. */
195: static rtx *line_note;
196: #define LINE_NOTE(INSN) (line_note[INSN_UID (INSN)])
197:
198: /* Vector indexed by basic block number giving the starting line-number
199: for each basic block. */
200: static rtx *line_note_head;
201:
202: /* List of important notes we must keep around. This is a pointer to the
203: last element in the list. */
204: static rtx note_list;
205:
206: /* Regsets telling whether a given register is live or dead before the last
207: scheduled insn. Must scan the instructions once before scheduling to
208: determine what registers are live or dead at the end of the block. */
209: static regset bb_dead_regs;
210: static regset bb_live_regs;
211:
212: /* Regset telling whether a given register is live after the insn currently
213: being scheduled. Before processing an insn, this is equal to bb_live_regs
214: above. This is used so that we can find registers that are newly born/dead
215: after processing an insn. */
216: static regset old_live_regs;
217:
218: /* The chain of REG_DEAD notes. REG_DEAD notes are removed from all insns
219: during the initial scan and reused later. If there are not exactly as
220: many REG_DEAD notes in the post scheduled code as there were in the
221: prescheduled code then we trigger an abort because this indicates a bug. */
222: static rtx dead_notes;
223:
224: /* Queues, etc. */
225:
226: /* An instruction is ready to be scheduled when all insns following it
227: have already been scheduled. It is important to ensure that all
228: insns which use its result will not be executed until its result
229: has been computed. An insn is maintained in one of four structures:
230:
231: (P) the "Pending" set of insns which cannot be scheduled until
232: their dependencies have been satisfied.
233: (Q) the "Queued" set of insns that can be scheduled when sufficient
234: time has passed.
235: (R) the "Ready" list of unscheduled, uncommitted insns.
236: (S) the "Scheduled" list of insns.
237:
238: Initially, all insns are either "Pending" or "Ready" depending on
239: whether their dependencies are satisfied.
240:
241: Insns move from the "Ready" list to the "Scheduled" list as they
242: are committed to the schedule. As this occurs, the insns in the
243: "Pending" list have their dependencies satisfied and move to either
244: the "Ready" list or the "Queued" set depending on whether
245: sufficient time has passed to make them ready. As time passes,
246: insns move from the "Queued" set to the "Ready" list. Insns may
247: move from the "Ready" list to the "Queued" set if they are blocked
248: due to a function unit conflict.
249:
250: The "Pending" list (P) are the insns in the LOG_LINKS of the unscheduled
251: insns, i.e., those that are ready, queued, and pending.
252: The "Queued" set (Q) is implemented by the variable `insn_queue'.
253: The "Ready" list (R) is implemented by the variables `ready' and
254: `n_ready'.
255: The "Scheduled" list (S) is the new insn chain built by this pass.
256:
257: The transition (R->S) is implemented in the scheduling loop in
258: `schedule_block' when the best insn to schedule is chosen.
259: The transition (R->Q) is implemented in `schedule_select' when an
260: insn is found to to have a function unit conflict with the already
261: committed insns.
262: The transitions (P->R and P->Q) are implemented in `schedule_insn' as
263: insns move from the ready list to the scheduled list.
264: The transition (Q->R) is implemented at the top of the scheduling
265: loop in `schedule_block' as time passes or stalls are introduced. */
266:
267: /* Implement a circular buffer to delay instructions until sufficient
268: time has passed. INSN_QUEUE_SIZE is a power of two larger than
269: MAX_BLOCKAGE and MAX_READY_COST computed by genattr.c. This is the
270: longest time an isnsn may be queued. */
271: static rtx insn_queue[INSN_QUEUE_SIZE];
272: static int q_ptr = 0;
273: static int q_size = 0;
274: #define NEXT_Q(X) (((X)+1) & (INSN_QUEUE_SIZE-1))
275: #define NEXT_Q_AFTER(X,C) (((X)+C) & (INSN_QUEUE_SIZE-1))
276:
277: /* Vector indexed by INSN_UID giving the minimum clock tick at which
278: the insn becomes ready. This is used to note timing constraints for
279: insns in the pending list. */
280: static int *insn_tick;
281: #define INSN_TICK(INSN) (insn_tick[INSN_UID (INSN)])
282:
283: /* Data structure for keeping track of register information
284: during that register's life. */
285:
286: struct sometimes
287: {
288: short offset; short bit;
289: short live_length; short calls_crossed;
290: };
291:
292: /* Forward declarations. */
293: static rtx canon_rtx PROTO((rtx));
294: static int rtx_equal_for_memref_p PROTO((rtx, rtx));
295: static rtx find_symbolic_term PROTO((rtx));
296: static int memrefs_conflict_p PROTO((int, rtx, int, rtx,
297: HOST_WIDE_INT));
298: static void add_dependence PROTO((rtx, rtx, enum reg_note));
299: static void remove_dependence PROTO((rtx, rtx));
300: static rtx find_insn_list PROTO((rtx, rtx));
301: static int insn_unit PROTO((rtx));
302: static unsigned int blockage_range PROTO((int, rtx));
303: static void clear_units PROTO((void));
304: static void prepare_unit PROTO((int));
305: static int actual_hazard_this_instance PROTO((int, int, rtx, int, int));
306: static void schedule_unit PROTO((int, rtx, int));
307: static int actual_hazard PROTO((int, rtx, int, int));
308: static int potential_hazard PROTO((int, rtx, int));
309: static int insn_cost PROTO((rtx, rtx, rtx));
310: static int priority PROTO((rtx));
311: static void free_pending_lists PROTO((void));
312: static void add_insn_mem_dependence PROTO((rtx *, rtx *, rtx, rtx));
313: static void flush_pending_lists PROTO((rtx));
314: static void sched_analyze_1 PROTO((rtx, rtx));
315: static void sched_analyze_2 PROTO((rtx, rtx));
316: static void sched_analyze_insn PROTO((rtx, rtx));
317: static int sched_analyze PROTO((rtx, rtx));
318: static void sched_note_set PROTO((int, rtx, int));
319: static int rank_for_schedule PROTO((rtx *, rtx *));
320: static void swap_sort PROTO((rtx *, int));
321: static void queue_insn PROTO((rtx, int));
322: static int birthing_insn PROTO((rtx));
323: static void adjust_priority PROTO((rtx));
324: static int schedule_insn PROTO((rtx, rtx *, int, int));
325: static int schedule_select PROTO((rtx *, int, int, FILE *));
326: static void create_reg_dead_note PROTO((rtx, rtx));
327: static void attach_deaths PROTO((rtx, rtx, int));
328: static void attach_deaths_insn PROTO((rtx));
329: static rtx unlink_notes PROTO((rtx, rtx));
330: static int new_sometimes_live PROTO((struct sometimes *, int, int,
331: int));
332: static void finish_sometimes_live PROTO((struct sometimes *, int));
333: static void schedule_block PROTO((int, FILE *));
334: static rtx regno_use_in PROTO((int, rtx));
335: static void split_hard_reg_notes PROTO((rtx, rtx, rtx, rtx));
336: static void new_insn_dead_notes PROTO((rtx, rtx, rtx, rtx));
337: static void update_n_sets PROTO((rtx, int));
338: static void update_flow_info PROTO((rtx, rtx, rtx, rtx));
339:
340: /* Main entry point of this file. */
341: void schedule_insns PROTO((FILE *));
342:
343: #endif /* INSN_SCHEDULING */
344:
345: #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
346:
347: /* Vector indexed by N giving the initial (unchanging) value known
348: for pseudo-register N. */
349: static rtx *reg_known_value;
350:
351: /* Vector recording for each reg_known_value whether it is due to a
352: REG_EQUIV note. Future passes (viz., reload) may replace the
353: pseudo with the equivalent expression and so we account for the
354: dependences that would be introduced if that happens. */
355: /* ??? This is a problem only on the Convex. The REG_EQUIV notes created in
356: assign_parms mention the arg pointer, and there are explicit insns in the
357: RTL that modify the arg pointer. Thus we must ensure that such insns don't
358: get scheduled across each other because that would invalidate the REG_EQUIV
359: notes. One could argue that the REG_EQUIV notes are wrong, but solving
360: the problem in the scheduler will likely give better code, so we do it
361: here. */
362: static char *reg_known_equiv_p;
363:
364: /* Indicates number of valid entries in reg_known_value. */
365: static int reg_known_value_size;
366:
367: static rtx
368: canon_rtx (x)
369: rtx x;
370: {
371: if (GET_CODE (x) == REG && REGNO (x) >= FIRST_PSEUDO_REGISTER
372: && REGNO (x) <= reg_known_value_size)
373: return reg_known_value[REGNO (x)];
374: else if (GET_CODE (x) == PLUS)
375: {
376: rtx x0 = canon_rtx (XEXP (x, 0));
377: rtx x1 = canon_rtx (XEXP (x, 1));
378:
379: if (x0 != XEXP (x, 0) || x1 != XEXP (x, 1))
380: {
381: /* We can tolerate LO_SUMs being offset here; these
382: rtl are used for nothing other than comparisons. */
383: if (GET_CODE (x0) == CONST_INT)
384: return plus_constant_for_output (x1, INTVAL (x0));
385: else if (GET_CODE (x1) == CONST_INT)
386: return plus_constant_for_output (x0, INTVAL (x1));
387: return gen_rtx (PLUS, GET_MODE (x), x0, x1);
388: }
389: }
390: return x;
391: }
392:
393: /* Set up all info needed to perform alias analysis on memory references. */
394:
395: void
396: init_alias_analysis ()
397: {
398: int maxreg = max_reg_num ();
399: rtx insn;
400: rtx note;
401: rtx set;
402:
403: reg_known_value_size = maxreg;
404:
405: reg_known_value
406: = (rtx *) oballoc ((maxreg-FIRST_PSEUDO_REGISTER) * sizeof (rtx))
407: - FIRST_PSEUDO_REGISTER;
408: bzero (reg_known_value+FIRST_PSEUDO_REGISTER,
409: (maxreg-FIRST_PSEUDO_REGISTER) * sizeof (rtx));
410:
411: reg_known_equiv_p
412: = (char *) oballoc ((maxreg-FIRST_PSEUDO_REGISTER) * sizeof (char))
413: - FIRST_PSEUDO_REGISTER;
414: bzero (reg_known_equiv_p+FIRST_PSEUDO_REGISTER,
415: (maxreg-FIRST_PSEUDO_REGISTER) * sizeof (char));
416:
417: /* Fill in the entries with known constant values. */
418: for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
419: if ((set = single_set (insn)) != 0
420: && GET_CODE (SET_DEST (set)) == REG
421: && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER
422: && (((note = find_reg_note (insn, REG_EQUAL, 0)) != 0
423: && reg_n_sets[REGNO (SET_DEST (set))] == 1)
424: || (note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != 0)
425: && GET_CODE (XEXP (note, 0)) != EXPR_LIST)
426: {
427: int regno = REGNO (SET_DEST (set));
428: reg_known_value[regno] = XEXP (note, 0);
429: reg_known_equiv_p[regno] = REG_NOTE_KIND (note) == REG_EQUIV;
430: }
431:
432: /* Fill in the remaining entries. */
433: while (--maxreg >= FIRST_PSEUDO_REGISTER)
434: if (reg_known_value[maxreg] == 0)
435: reg_known_value[maxreg] = regno_reg_rtx[maxreg];
436: }
437:
438: /* Return 1 if X and Y are identical-looking rtx's.
439:
440: We use the data in reg_known_value above to see if two registers with
441: different numbers are, in fact, equivalent. */
442:
443: static int
444: rtx_equal_for_memref_p (x, y)
445: rtx x, y;
446: {
447: register int i;
448: register int j;
449: register enum rtx_code code;
450: register char *fmt;
451:
452: if (x == 0 && y == 0)
453: return 1;
454: if (x == 0 || y == 0)
455: return 0;
456: x = canon_rtx (x);
457: y = canon_rtx (y);
458:
459: if (x == y)
460: return 1;
461:
462: code = GET_CODE (x);
463: /* Rtx's of different codes cannot be equal. */
464: if (code != GET_CODE (y))
465: return 0;
466:
467: /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
468: (REG:SI x) and (REG:HI x) are NOT equivalent. */
469:
470: if (GET_MODE (x) != GET_MODE (y))
471: return 0;
472:
473: /* REG, LABEL_REF, and SYMBOL_REF can be compared nonrecursively. */
474:
475: if (code == REG)
476: return REGNO (x) == REGNO (y);
477: if (code == LABEL_REF)
478: return XEXP (x, 0) == XEXP (y, 0);
479: if (code == SYMBOL_REF)
480: return XSTR (x, 0) == XSTR (y, 0);
481:
482: /* Compare the elements. If any pair of corresponding elements
483: fail to match, return 0 for the whole things. */
484:
485: fmt = GET_RTX_FORMAT (code);
486: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
487: {
488: switch (fmt[i])
489: {
490: case 'w':
491: if (XWINT (x, i) != XWINT (y, i))
492: return 0;
493: break;
494:
495: case 'n':
496: case 'i':
497: if (XINT (x, i) != XINT (y, i))
498: return 0;
499: break;
500:
501: case 'V':
502: case 'E':
503: /* Two vectors must have the same length. */
504: if (XVECLEN (x, i) != XVECLEN (y, i))
505: return 0;
506:
507: /* And the corresponding elements must match. */
508: for (j = 0; j < XVECLEN (x, i); j++)
509: if (rtx_equal_for_memref_p (XVECEXP (x, i, j), XVECEXP (y, i, j)) == 0)
510: return 0;
511: break;
512:
513: case 'e':
514: if (rtx_equal_for_memref_p (XEXP (x, i), XEXP (y, i)) == 0)
515: return 0;
516: break;
517:
518: case 'S':
519: case 's':
520: if (strcmp (XSTR (x, i), XSTR (y, i)))
521: return 0;
522: break;
523:
524: case 'u':
525: /* These are just backpointers, so they don't matter. */
526: break;
527:
528: case '0':
529: break;
530:
531: /* It is believed that rtx's at this level will never
532: contain anything but integers and other rtx's,
533: except for within LABEL_REFs and SYMBOL_REFs. */
534: default:
535: abort ();
536: }
537: }
538: return 1;
539: }
540:
541: /* Given an rtx X, find a SYMBOL_REF or LABEL_REF within
542: X and return it, or return 0 if none found. */
543:
544: static rtx
545: find_symbolic_term (x)
546: rtx x;
547: {
548: register int i;
549: register enum rtx_code code;
550: register char *fmt;
551:
552: code = GET_CODE (x);
553: if (code == SYMBOL_REF || code == LABEL_REF)
554: return x;
555: if (GET_RTX_CLASS (code) == 'o')
556: return 0;
557:
558: fmt = GET_RTX_FORMAT (code);
559: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
560: {
561: rtx t;
562:
563: if (fmt[i] == 'e')
564: {
565: t = find_symbolic_term (XEXP (x, i));
566: if (t != 0)
567: return t;
568: }
569: else if (fmt[i] == 'E')
570: break;
571: }
572: return 0;
573: }
574:
575: /* Return nonzero if X and Y (memory addresses) could reference the
576: same location in memory. C is an offset accumulator. When
577: C is nonzero, we are testing aliases between X and Y + C.
578: XSIZE is the size in bytes of the X reference,
579: similarly YSIZE is the size in bytes for Y.
580:
581: If XSIZE or YSIZE is zero, we do not know the amount of memory being
582: referenced (the reference was BLKmode), so make the most pessimistic
583: assumptions.
584:
585: We recognize the following cases of non-conflicting memory:
586:
587: (1) addresses involving the frame pointer cannot conflict
588: with addresses involving static variables.
589: (2) static variables with different addresses cannot conflict.
590:
591: Nice to notice that varying addresses cannot conflict with fp if no
592: local variables had their addresses taken, but that's too hard now. */
593:
594: /* ??? In Fortran, references to a array parameter can never conflict with
595: another array parameter. */
596:
597: static int
598: memrefs_conflict_p (xsize, x, ysize, y, c)
599: rtx x, y;
600: int xsize, ysize;
601: HOST_WIDE_INT c;
602: {
603: if (GET_CODE (x) == HIGH)
604: x = XEXP (x, 0);
605: else if (GET_CODE (x) == LO_SUM)
606: x = XEXP (x, 1);
607: else
608: x = canon_rtx (x);
609: if (GET_CODE (y) == HIGH)
610: y = XEXP (y, 0);
611: else if (GET_CODE (y) == LO_SUM)
612: y = XEXP (y, 1);
613: else
614: y = canon_rtx (y);
615:
616: if (rtx_equal_for_memref_p (x, y))
617: return (xsize == 0 || ysize == 0 ||
618: (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
619:
620: if (y == frame_pointer_rtx || y == hard_frame_pointer_rtx
621: || y == stack_pointer_rtx)
622: {
623: rtx t = y;
624: int tsize = ysize;
625: y = x; ysize = xsize;
626: x = t; xsize = tsize;
627: }
628:
629: if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
630: || x == stack_pointer_rtx)
631: {
632: rtx y1;
633:
634: if (CONSTANT_P (y))
635: return 0;
636:
637: if (GET_CODE (y) == PLUS
638: && canon_rtx (XEXP (y, 0)) == x
639: && (y1 = canon_rtx (XEXP (y, 1)))
640: && GET_CODE (y1) == CONST_INT)
641: {
642: c += INTVAL (y1);
643: return (xsize == 0 || ysize == 0
644: || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
645: }
646:
647: if (GET_CODE (y) == PLUS
648: && (y1 = canon_rtx (XEXP (y, 0)))
649: && CONSTANT_P (y1))
650: return 0;
651:
652: return 1;
653: }
654:
655: if (GET_CODE (x) == PLUS)
656: {
657: /* The fact that X is canonicalized means that this
658: PLUS rtx is canonicalized. */
659: rtx x0 = XEXP (x, 0);
660: rtx x1 = XEXP (x, 1);
661:
662: if (GET_CODE (y) == PLUS)
663: {
664: /* The fact that Y is canonicalized means that this
665: PLUS rtx is canonicalized. */
666: rtx y0 = XEXP (y, 0);
667: rtx y1 = XEXP (y, 1);
668:
669: if (rtx_equal_for_memref_p (x1, y1))
670: return memrefs_conflict_p (xsize, x0, ysize, y0, c);
671: if (rtx_equal_for_memref_p (x0, y0))
672: return memrefs_conflict_p (xsize, x1, ysize, y1, c);
673: if (GET_CODE (x1) == CONST_INT)
674: if (GET_CODE (y1) == CONST_INT)
675: return memrefs_conflict_p (xsize, x0, ysize, y0,
676: c - INTVAL (x1) + INTVAL (y1));
677: else
678: return memrefs_conflict_p (xsize, x0, ysize, y, c - INTVAL (x1));
679: else if (GET_CODE (y1) == CONST_INT)
680: return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1));
681:
682: /* Handle case where we cannot understand iteration operators,
683: but we notice that the base addresses are distinct objects. */
684: x = find_symbolic_term (x);
685: if (x == 0)
686: return 1;
687: y = find_symbolic_term (y);
688: if (y == 0)
689: return 1;
690: return rtx_equal_for_memref_p (x, y);
691: }
692: else if (GET_CODE (x1) == CONST_INT)
693: return memrefs_conflict_p (xsize, x0, ysize, y, c - INTVAL (x1));
694: }
695: else if (GET_CODE (y) == PLUS)
696: {
697: /* The fact that Y is canonicalized means that this
698: PLUS rtx is canonicalized. */
699: rtx y0 = XEXP (y, 0);
700: rtx y1 = XEXP (y, 1);
701:
702: if (GET_CODE (y1) == CONST_INT)
703: return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1));
704: else
705: return 1;
706: }
707:
708: if (GET_CODE (x) == GET_CODE (y))
709: switch (GET_CODE (x))
710: {
711: case MULT:
712: {
713: /* Handle cases where we expect the second operands to be the
714: same, and check only whether the first operand would conflict
715: or not. */
716: rtx x0, y0;
717: rtx x1 = canon_rtx (XEXP (x, 1));
718: rtx y1 = canon_rtx (XEXP (y, 1));
719: if (! rtx_equal_for_memref_p (x1, y1))
720: return 1;
721: x0 = canon_rtx (XEXP (x, 0));
722: y0 = canon_rtx (XEXP (y, 0));
723: if (rtx_equal_for_memref_p (x0, y0))
724: return (xsize == 0 || ysize == 0
725: || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
726:
727: /* Can't properly adjust our sizes. */
728: if (GET_CODE (x1) != CONST_INT)
729: return 1;
730: xsize /= INTVAL (x1);
731: ysize /= INTVAL (x1);
732: c /= INTVAL (x1);
733: return memrefs_conflict_p (xsize, x0, ysize, y0, c);
734: }
735: }
736:
737: if (CONSTANT_P (x))
738: {
739: if (GET_CODE (x) == CONST_INT && GET_CODE (y) == CONST_INT)
740: {
741: c += (INTVAL (y) - INTVAL (x));
742: return (xsize == 0 || ysize == 0
743: || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0));
744: }
745:
746: if (GET_CODE (x) == CONST)
747: {
748: if (GET_CODE (y) == CONST)
749: return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
750: ysize, canon_rtx (XEXP (y, 0)), c);
751: else
752: return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)),
753: ysize, y, c);
754: }
755: if (GET_CODE (y) == CONST)
756: return memrefs_conflict_p (xsize, x, ysize,
757: canon_rtx (XEXP (y, 0)), c);
758:
759: if (CONSTANT_P (y))
760: return (rtx_equal_for_memref_p (x, y)
761: && (xsize == 0 || ysize == 0
762: || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0)));
763:
764: return 1;
765: }
766: return 1;
767: }
768:
769: /* Functions to compute memory dependencies.
770:
771: Since we process the insns in execution order, we can build tables
772: to keep track of what registers are fixed (and not aliased), what registers
773: are varying in known ways, and what registers are varying in unknown
774: ways.
775:
776: If both memory references are volatile, then there must always be a
777: dependence between the two references, since their order can not be
778: changed. A volatile and non-volatile reference can be interchanged
779: though.
780:
781: A MEM_IN_STRUCT reference at a non-QImode varying address can never
782: conflict with a non-MEM_IN_STRUCT reference at a fixed address. We must
783: allow QImode aliasing because the ANSI C standard allows character
784: pointers to alias anything. We are assuming that characters are
785: always QImode here. */
786:
787: /* Read dependence: X is read after read in MEM takes place. There can
788: only be a dependence here if both reads are volatile. */
789:
790: int
791: read_dependence (mem, x)
792: rtx mem;
793: rtx x;
794: {
795: return MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem);
796: }
797:
798: /* True dependence: X is read after store in MEM takes place. */
799:
800: int
801: true_dependence (mem, x)
802: rtx mem;
803: rtx x;
804: {
805: /* If X is an unchanging read, then it can't possibly conflict with any
806: non-unchanging store. It may conflict with an unchanging write though,
807: because there may be a single store to this address to initialize it.
808: Just fall through to the code below to resolve the case where we have
809: both an unchanging read and an unchanging write. This won't handle all
810: cases optimally, but the possible performance loss should be
811: negligible. */
812: if (RTX_UNCHANGING_P (x) && ! RTX_UNCHANGING_P (mem))
813: return 0;
814:
815: return ((MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
816: || (memrefs_conflict_p (SIZE_FOR_MODE (mem), XEXP (mem, 0),
817: SIZE_FOR_MODE (x), XEXP (x, 0), 0)
818: && ! (MEM_IN_STRUCT_P (mem) && rtx_addr_varies_p (mem)
819: && GET_MODE (mem) != QImode
820: && ! MEM_IN_STRUCT_P (x) && ! rtx_addr_varies_p (x))
821: && ! (MEM_IN_STRUCT_P (x) && rtx_addr_varies_p (x)
822: && GET_MODE (x) != QImode
823: && ! MEM_IN_STRUCT_P (mem) && ! rtx_addr_varies_p (mem))));
824: }
825:
826: /* Anti dependence: X is written after read in MEM takes place. */
827:
828: int
829: anti_dependence (mem, x)
830: rtx mem;
831: rtx x;
832: {
833: /* If MEM is an unchanging read, then it can't possibly conflict with
834: the store to X, because there is at most one store to MEM, and it must
835: have occured somewhere before MEM. */
836: if (RTX_UNCHANGING_P (mem))
837: return 0;
838:
839: return ((MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
840: || (memrefs_conflict_p (SIZE_FOR_MODE (mem), XEXP (mem, 0),
841: SIZE_FOR_MODE (x), XEXP (x, 0), 0)
842: && ! (MEM_IN_STRUCT_P (mem) && rtx_addr_varies_p (mem)
843: && GET_MODE (mem) != QImode
844: && ! MEM_IN_STRUCT_P (x) && ! rtx_addr_varies_p (x))
845: && ! (MEM_IN_STRUCT_P (x) && rtx_addr_varies_p (x)
846: && GET_MODE (x) != QImode
847: && ! MEM_IN_STRUCT_P (mem) && ! rtx_addr_varies_p (mem))));
848: }
849:
850: /* Output dependence: X is written after store in MEM takes place. */
851:
852: int
853: output_dependence (mem, x)
854: rtx mem;
855: rtx x;
856: {
857: return ((MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
858: || (memrefs_conflict_p (SIZE_FOR_MODE (mem), XEXP (mem, 0),
859: SIZE_FOR_MODE (x), XEXP (x, 0), 0)
860: && ! (MEM_IN_STRUCT_P (mem) && rtx_addr_varies_p (mem)
861: && GET_MODE (mem) != QImode
862: && ! MEM_IN_STRUCT_P (x) && ! rtx_addr_varies_p (x))
863: && ! (MEM_IN_STRUCT_P (x) && rtx_addr_varies_p (x)
864: && GET_MODE (x) != QImode
865: && ! MEM_IN_STRUCT_P (mem) && ! rtx_addr_varies_p (mem))));
866: }
867:
868: /* Helper functions for instruction scheduling. */
869:
870: /* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the
871: LOG_LINKS of INSN, if not already there. DEP_TYPE indicates the type
872: of dependence that this link represents. */
873:
874: static void
875: add_dependence (insn, elem, dep_type)
876: rtx insn;
877: rtx elem;
878: enum reg_note dep_type;
879: {
880: rtx link, next;
881:
882: /* Don't depend an insn on itself. */
883: if (insn == elem)
884: return;
885:
886: /* If elem is part of a sequence that must be scheduled together, then
887: make the dependence point to the last insn of the sequence.
888: When HAVE_cc0, it is possible for NOTEs to exist between users and
889: setters of the condition codes, so we must skip past notes here.
890: Otherwise, NOTEs are impossible here. */
891:
892: next = NEXT_INSN (elem);
893:
894: #ifdef HAVE_cc0
895: while (next && GET_CODE (next) == NOTE)
896: next = NEXT_INSN (next);
897: #endif
898:
899: if (next && SCHED_GROUP_P (next))
900: {
901: /* Notes will never intervene here though, so don't bother checking
902: for them. */
903: /* We must reject CODE_LABELs, so that we don't get confused by one
904: that has LABEL_PRESERVE_P set, which is represented by the same
905: bit in the rtl as SCHED_GROUP_P. A CODE_LABEL can never be
906: SCHED_GROUP_P. */
907: while (NEXT_INSN (next) && SCHED_GROUP_P (NEXT_INSN (next))
908: && GET_CODE (NEXT_INSN (next)) != CODE_LABEL)
909: next = NEXT_INSN (next);
910:
911: /* Again, don't depend an insn on itself. */
912: if (insn == next)
913: return;
914:
915: /* Make the dependence to NEXT, the last insn of the group, instead
916: of the original ELEM. */
917: elem = next;
918: }
919:
920: /* Check that we don't already have this dependence. */
921: for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
922: if (XEXP (link, 0) == elem)
923: {
924: /* If this is a more restrictive type of dependence than the existing
925: one, then change the existing dependence to this type. */
926: if ((int) dep_type < (int) REG_NOTE_KIND (link))
927: PUT_REG_NOTE_KIND (link, dep_type);
928: return;
929: }
930: /* Might want to check one level of transitivity to save conses. */
931:
932: link = rtx_alloc (INSN_LIST);
933: /* Insn dependency, not data dependency. */
934: PUT_REG_NOTE_KIND (link, dep_type);
935: XEXP (link, 0) = elem;
936: XEXP (link, 1) = LOG_LINKS (insn);
937: LOG_LINKS (insn) = link;
938: }
939:
940: /* Remove ELEM wrapped in an INSN_LIST from the LOG_LINKS
941: of INSN. Abort if not found. */
942:
943: static void
944: remove_dependence (insn, elem)
945: rtx insn;
946: rtx elem;
947: {
948: rtx prev, link;
949: int found = 0;
950:
951: for (prev = 0, link = LOG_LINKS (insn); link;
952: prev = link, link = XEXP (link, 1))
953: {
954: if (XEXP (link, 0) == elem)
955: {
956: if (prev)
957: XEXP (prev, 1) = XEXP (link, 1);
958: else
959: LOG_LINKS (insn) = XEXP (link, 1);
960: found = 1;
961: }
962: }
963:
964: if (! found)
965: abort ();
966: return;
967: }
968:
969: #ifndef INSN_SCHEDULING
970: void
971: schedule_insns (dump_file)
972: FILE *dump_file;
973: {
974: }
975: #else
976: #ifndef __GNUC__
977: #define __inline
978: #endif
979:
980: /* Computation of memory dependencies. */
981:
982: /* The *_insns and *_mems are paired lists. Each pending memory operation
983: will have a pointer to the MEM rtx on one list and a pointer to the
984: containing insn on the other list in the same place in the list. */
985:
986: /* We can't use add_dependence like the old code did, because a single insn
987: may have multiple memory accesses, and hence needs to be on the list
988: once for each memory access. Add_dependence won't let you add an insn
989: to a list more than once. */
990:
991: /* An INSN_LIST containing all insns with pending read operations. */
992: static rtx pending_read_insns;
993:
994: /* An EXPR_LIST containing all MEM rtx's which are pending reads. */
995: static rtx pending_read_mems;
996:
997: /* An INSN_LIST containing all insns with pending write operations. */
998: static rtx pending_write_insns;
999:
1000: /* An EXPR_LIST containing all MEM rtx's which are pending writes. */
1001: static rtx pending_write_mems;
1002:
1003: /* Indicates the combined length of the two pending lists. We must prevent
1004: these lists from ever growing too large since the number of dependencies
1005: produced is at least O(N*N), and execution time is at least O(4*N*N), as
1006: a function of the length of these pending lists. */
1007:
1008: static int pending_lists_length;
1009:
1010: /* An INSN_LIST containing all INSN_LISTs allocated but currently unused. */
1011:
1012: static rtx unused_insn_list;
1013:
1014: /* An EXPR_LIST containing all EXPR_LISTs allocated but currently unused. */
1015:
1016: static rtx unused_expr_list;
1017:
1018: /* The last insn upon which all memory references must depend.
1019: This is an insn which flushed the pending lists, creating a dependency
1020: between it and all previously pending memory references. This creates
1021: a barrier (or a checkpoint) which no memory reference is allowed to cross.
1022:
1023: This includes all non constant CALL_INSNs. When we do interprocedural
1024: alias analysis, this restriction can be relaxed.
1025: This may also be an INSN that writes memory if the pending lists grow
1026: too large. */
1027:
1028: static rtx last_pending_memory_flush;
1029:
1030: /* The last function call we have seen. All hard regs, and, of course,
1031: the last function call, must depend on this. */
1032:
1033: static rtx last_function_call;
1034:
1035: /* The LOG_LINKS field of this is a list of insns which use a pseudo register
1036: that does not already cross a call. We create dependencies between each
1037: of those insn and the next call insn, to ensure that they won't cross a call
1038: after scheduling is done. */
1039:
1040: static rtx sched_before_next_call;
1041:
1042: /* Pointer to the last instruction scheduled. Used by rank_for_schedule,
1043: so that insns independent of the last scheduled insn will be preferred
1044: over dependent instructions. */
1045:
1046: static rtx last_scheduled_insn;
1047:
1048: /* Process an insn's memory dependencies. There are four kinds of
1049: dependencies:
1050:
1051: (0) read dependence: read follows read
1052: (1) true dependence: read follows write
1053: (2) anti dependence: write follows read
1054: (3) output dependence: write follows write
1055:
1056: We are careful to build only dependencies which actually exist, and
1057: use transitivity to avoid building too many links. */
1058:
1059: /* Return the INSN_LIST containing INSN in LIST, or NULL
1060: if LIST does not contain INSN. */
1061:
1062: __inline static rtx
1063: find_insn_list (insn, list)
1064: rtx insn;
1065: rtx list;
1066: {
1067: while (list)
1068: {
1069: if (XEXP (list, 0) == insn)
1070: return list;
1071: list = XEXP (list, 1);
1072: }
1073: return 0;
1074: }
1075:
1076: /* Compute the function units used by INSN. This caches the value
1077: returned by function_units_used. A function unit is encoded as the
1078: unit number if the value is non-negative and the compliment of a
1079: mask if the value is negative. A function unit index is the
1080: non-negative encoding. */
1081:
1082: __inline static int
1083: insn_unit (insn)
1084: rtx insn;
1085: {
1086: register int unit = INSN_UNIT (insn);
1087:
1088: if (unit == 0)
1089: {
1090: recog_memoized (insn);
1091:
1092: /* A USE insn, or something else we don't need to understand.
1093: We can't pass these directly to function_units_used because it will
1094: trigger a fatal error for unrecognizable insns. */
1095: if (INSN_CODE (insn) < 0)
1096: unit = -1;
1097: else
1098: {
1099: unit = function_units_used (insn);
1100: /* Increment non-negative values so we can cache zero. */
1101: if (unit >= 0) unit++;
1102: }
1103: /* We only cache 16 bits of the result, so if the value is out of
1104: range, don't cache it. */
1105: if (FUNCTION_UNITS_SIZE < HOST_BITS_PER_SHORT
1106: || unit >= 0
1107: || (~unit & ((1 << (HOST_BITS_PER_SHORT - 1)) - 1)) == 0)
1108: INSN_UNIT (insn) = unit;
1109: }
1110: return (unit > 0 ? unit - 1 : unit);
1111: }
1112:
1113: /* Compute the blockage range for executing INSN on UNIT. This caches
1114: the value returned by the blockage_range_function for the unit.
1115: These values are encoded in an int where the upper half gives the
1116: minimum value and the lower half gives the maximum value. */
1117:
1118: __inline static unsigned int
1119: blockage_range (unit, insn)
1120: int unit;
1121: rtx insn;
1122: {
1123: unsigned int blockage = INSN_BLOCKAGE (insn);
1124: unsigned int range;
1125:
1126: if (UNIT_BLOCKED (blockage) != unit + 1)
1127: {
1128: range = function_units[unit].blockage_range_function (insn);
1129: /* We only cache the blockage range for one unit and then only if
1130: the values fit. */
1131: if (HOST_BITS_PER_INT >= UNIT_BITS + 2 * BLOCKAGE_BITS)
1132: INSN_BLOCKAGE (insn) = ENCODE_BLOCKAGE (unit + 1, range);
1133: }
1134: else
1135: range = BLOCKAGE_RANGE (blockage);
1136:
1137: return range;
1138: }
1139:
1140: /* A vector indexed by function unit instance giving the last insn to use
1141: the unit. The value of the function unit instance index for unit U
1142: instance I is (U + I * FUNCTION_UNITS_SIZE). */
1143: static rtx unit_last_insn[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY];
1144:
1145: /* A vector indexed by function unit instance giving the minimum time when
1146: the unit will unblock based on the maximum blockage cost. */
1147: static int unit_tick[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY];
1148:
1149: /* A vector indexed by function unit number giving the number of insns
1150: that remain to use the unit. */
1151: static int unit_n_insns[FUNCTION_UNITS_SIZE];
1152:
1153: /* Reset the function unit state to the null state. */
1154:
1155: static void
1156: clear_units ()
1157: {
1158: int unit;
1159:
1160: bzero (unit_last_insn, sizeof (unit_last_insn));
1161: bzero (unit_tick, sizeof (unit_tick));
1162: bzero (unit_n_insns, sizeof (unit_n_insns));
1163: }
1164:
1165: /* Record an insn as one that will use the units encoded by UNIT. */
1166:
1167: __inline static void
1168: prepare_unit (unit)
1169: int unit;
1170: {
1171: int i;
1172:
1173: if (unit >= 0)
1174: unit_n_insns[unit]++;
1175: else
1176: for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
1177: if ((unit & 1) != 0)
1178: prepare_unit (i);
1179: }
1180:
1181: /* Return the actual hazard cost of executing INSN on the unit UNIT,
1182: instance INSTANCE at time CLOCK if the previous actual hazard cost
1183: was COST. */
1184:
1185: __inline static int
1186: actual_hazard_this_instance (unit, instance, insn, clock, cost)
1187: int unit, instance, clock, cost;
1188: rtx insn;
1189: {
1190: int i;
1191: int tick = unit_tick[instance];
1192:
1193: if (tick - clock > cost)
1194: {
1195: /* The scheduler is operating in reverse, so INSN is the executing
1196: insn and the unit's last insn is the candidate insn. We want a
1197: more exact measure of the blockage if we execute INSN at CLOCK
1198: given when we committed the execution of the unit's last insn.
1199:
1200: The blockage value is given by either the unit's max blockage
1201: constant, blockage range function, or blockage function. Use
1202: the most exact form for the given unit. */
1203:
1204: if (function_units[unit].blockage_range_function)
1205: {
1206: if (function_units[unit].blockage_function)
1207: tick += (function_units[unit].blockage_function
1208: (insn, unit_last_insn[instance])
1209: - function_units[unit].max_blockage);
1210: else
1211: tick += ((int) MAX_BLOCKAGE_COST (blockage_range (unit, insn))
1212: - function_units[unit].max_blockage);
1213: }
1214: if (tick - clock > cost)
1215: cost = tick - clock;
1216: }
1217: return cost;
1218: }
1219:
1220: /* Record INSN as having begun execution on the units encoded by UNIT at
1221: time CLOCK. */
1222:
1223: __inline static void
1224: schedule_unit (unit, insn, clock)
1225: int unit, clock;
1226: rtx insn;
1227: {
1228: int i;
1229:
1230: if (unit >= 0)
1231: {
1232: int instance = unit;
1233: #if MAX_MULTIPLICITY > 1
1234: /* Find the first free instance of the function unit and use that
1235: one. We assume that one is free. */
1236: for (i = function_units[unit].multiplicity - 1; i > 0; i--)
1237: {
1238: if (! actual_hazard_this_instance (unit, instance, insn, clock, 0))
1239: break;
1240: instance += FUNCTION_UNITS_SIZE;
1241: }
1242: #endif
1243: unit_last_insn[instance] = insn;
1244: unit_tick[instance] = (clock + function_units[unit].max_blockage);
1245: }
1246: else
1247: for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
1248: if ((unit & 1) != 0)
1249: schedule_unit (i, insn, clock);
1250: }
1251:
1252: /* Return the actual hazard cost of executing INSN on the units encoded by
1253: UNIT at time CLOCK if the previous actual hazard cost was COST. */
1254:
1255: __inline static int
1256: actual_hazard (unit, insn, clock, cost)
1257: int unit, clock, cost;
1258: rtx insn;
1259: {
1260: int i;
1261:
1262: if (unit >= 0)
1263: {
1264: /* Find the instance of the function unit with the minimum hazard. */
1265: int instance = unit;
1266: int best = instance;
1267: int best_cost = actual_hazard_this_instance (unit, instance, insn,
1268: clock, cost);
1269: int this_cost;
1270:
1271: #if MAX_MULTIPLICITY > 1
1272: if (best_cost > cost)
1273: {
1274: for (i = function_units[unit].multiplicity - 1; i > 0; i--)
1275: {
1276: instance += FUNCTION_UNITS_SIZE;
1277: this_cost = actual_hazard_this_instance (unit, instance, insn,
1278: clock, cost);
1279: if (this_cost < best_cost)
1280: {
1281: best = instance;
1282: best_cost = this_cost;
1283: if (this_cost <= cost)
1284: break;
1285: }
1286: }
1287: }
1288: #endif
1289: cost = MAX (cost, best_cost);
1290: }
1291: else
1292: for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
1293: if ((unit & 1) != 0)
1294: cost = actual_hazard (i, insn, clock, cost);
1295:
1296: return cost;
1297: }
1298:
1299: /* Return the potential hazard cost of executing an instruction on the
1300: units encoded by UNIT if the previous potential hazard cost was COST.
1301: An insn with a large blockage time is chosen in preference to one
1302: with a smaller time; an insn that uses a unit that is more likely
1303: to be used is chosen in preference to one with a unit that is less
1304: used. We are trying to minimize a subsequent actual hazard. */
1305:
1306: __inline static int
1307: potential_hazard (unit, insn, cost)
1308: int unit, cost;
1309: rtx insn;
1310: {
1311: int i, ncost;
1312: unsigned int minb, maxb;
1313:
1314: if (unit >= 0)
1315: {
1316: minb = maxb = function_units[unit].max_blockage;
1317: if (maxb > 1)
1318: {
1319: if (function_units[unit].blockage_range_function)
1320: {
1321: maxb = minb = blockage_range (unit, insn);
1322: maxb = MAX_BLOCKAGE_COST (maxb);
1323: minb = MIN_BLOCKAGE_COST (minb);
1324: }
1325:
1326: if (maxb > 1)
1327: {
1328: /* Make the number of instructions left dominate. Make the
1329: minimum delay dominate the maximum delay. If all these
1330: are the same, use the unit number to add an arbitrary
1331: ordering. Other terms can be added. */
1332: ncost = minb * 0x40 + maxb;
1333: ncost *= (unit_n_insns[unit] - 1) * 0x1000 + unit;
1334: if (ncost > cost)
1335: cost = ncost;
1336: }
1337: }
1338: }
1339: else
1340: for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
1341: if ((unit & 1) != 0)
1342: cost = potential_hazard (i, insn, cost);
1343:
1344: return cost;
1345: }
1346:
1347: /* Compute cost of executing INSN given the dependence LINK on the insn USED.
1348: This is the number of virtual cycles taken between instruction issue and
1349: instruction results. */
1350:
1351: __inline static int
1352: insn_cost (insn, link, used)
1353: rtx insn, link, used;
1354: {
1355: register int cost = INSN_COST (insn);
1356:
1357: if (cost == 0)
1358: {
1359: recog_memoized (insn);
1360:
1361: /* A USE insn, or something else we don't need to understand.
1362: We can't pass these directly to result_ready_cost because it will
1363: trigger a fatal error for unrecognizable insns. */
1364: if (INSN_CODE (insn) < 0)
1365: {
1366: INSN_COST (insn) = 1;
1367: return 1;
1368: }
1369: else
1370: {
1371: cost = result_ready_cost (insn);
1372:
1373: if (cost < 1)
1374: cost = 1;
1375:
1376: INSN_COST (insn) = cost;
1377: }
1378: }
1379:
1380: /* A USE insn should never require the value used to be computed. This
1381: allows the computation of a function's result and parameter values to
1382: overlap the return and call. */
1383: recog_memoized (used);
1384: if (INSN_CODE (used) < 0)
1385: LINK_COST_FREE (link) = 1;
1386:
1387: /* If some dependencies vary the cost, compute the adjustment. Most
1388: commonly, the adjustment is complete: either the cost is ignored
1389: (in the case of an output- or anti-dependence), or the cost is
1390: unchanged. These values are cached in the link as LINK_COST_FREE
1391: and LINK_COST_ZERO. */
1392:
1393: if (LINK_COST_FREE (link))
1394: cost = 1;
1395: #ifdef ADJUST_COST
1396: else if (! LINK_COST_ZERO (link))
1397: {
1398: int ncost = cost;
1399:
1400: ADJUST_COST (used, link, insn, ncost);
1401: if (ncost <= 1)
1402: LINK_COST_FREE (link) = ncost = 1;
1403: if (cost == ncost)
1404: LINK_COST_ZERO (link) = 1;
1405: cost = ncost;
1406: }
1407: #endif
1408: return cost;
1409: }
1410:
1411: /* Compute the priority number for INSN. */
1412:
1413: static int
1414: priority (insn)
1415: rtx insn;
1416: {
1417: if (insn && GET_RTX_CLASS (GET_CODE (insn)) == 'i')
1418: {
1419: int prev_priority;
1420: int max_priority;
1421: int this_priority = INSN_PRIORITY (insn);
1422: rtx prev;
1423:
1424: if (this_priority > 0)
1425: return this_priority;
1426:
1427: max_priority = 1;
1428:
1429: /* Nonzero if these insns must be scheduled together. */
1430: if (SCHED_GROUP_P (insn))
1431: {
1432: prev = insn;
1433: while (SCHED_GROUP_P (prev))
1434: {
1435: prev = PREV_INSN (prev);
1436: INSN_REF_COUNT (prev) += 1;
1437: }
1438: }
1439:
1440: for (prev = LOG_LINKS (insn); prev; prev = XEXP (prev, 1))
1441: {
1442: rtx x = XEXP (prev, 0);
1443:
1444: /* A dependence pointing to a note is always obsolete, because
1445: sched_analyze_insn will have created any necessary new dependences
1446: which replace it. Notes can be created when instructions are
1447: deleted by insn splitting, or by register allocation. */
1448: if (GET_CODE (x) == NOTE)
1449: {
1450: remove_dependence (insn, x);
1451: continue;
1452: }
1453:
1454: /* Clear the link cost adjustment bits. */
1455: LINK_COST_FREE (prev) = 0;
1456: #ifdef ADJUST_COST
1457: LINK_COST_ZERO (prev) = 0;
1458: #endif
1459:
1460: /* This priority calculation was chosen because it results in the
1461: least instruction movement, and does not hurt the performance
1462: of the resulting code compared to the old algorithm.
1463: This makes the sched algorithm more stable, which results
1464: in better code, because there is less register pressure,
1465: cross jumping is more likely to work, and debugging is easier.
1466:
1467: When all instructions have a latency of 1, there is no need to
1468: move any instructions. Subtracting one here ensures that in such
1469: cases all instructions will end up with a priority of one, and
1470: hence no scheduling will be done.
1471:
1472: The original code did not subtract the one, and added the
1473: insn_cost of the current instruction to its priority (e.g.
1474: move the insn_cost call down to the end). */
1475:
1476: if (REG_NOTE_KIND (prev) == 0)
1477: /* Data dependence. */
1478: prev_priority = priority (x) + insn_cost (x, prev, insn) - 1;
1479: else
1480: /* Anti or output dependence. Don't add the latency of this
1481: insn's result, because it isn't being used. */
1482: prev_priority = priority (x);
1483:
1484: if (prev_priority > max_priority)
1485: max_priority = prev_priority;
1486: INSN_REF_COUNT (x) += 1;
1487: }
1488:
1489: prepare_unit (insn_unit (insn));
1490: INSN_PRIORITY (insn) = max_priority;
1491: return INSN_PRIORITY (insn);
1492: }
1493: return 0;
1494: }
1495:
1496: /* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
1497: them to the unused_*_list variables, so that they can be reused. */
1498:
1499: static void
1500: free_pending_lists ()
1501: {
1502: register rtx link, prev_link;
1503:
1504: if (pending_read_insns)
1505: {
1506: prev_link = pending_read_insns;
1507: link = XEXP (prev_link, 1);
1508:
1509: while (link)
1510: {
1511: prev_link = link;
1512: link = XEXP (link, 1);
1513: }
1514:
1515: XEXP (prev_link, 1) = unused_insn_list;
1516: unused_insn_list = pending_read_insns;
1517: pending_read_insns = 0;
1518: }
1519:
1520: if (pending_write_insns)
1521: {
1522: prev_link = pending_write_insns;
1523: link = XEXP (prev_link, 1);
1524:
1525: while (link)
1526: {
1527: prev_link = link;
1528: link = XEXP (link, 1);
1529: }
1530:
1531: XEXP (prev_link, 1) = unused_insn_list;
1532: unused_insn_list = pending_write_insns;
1533: pending_write_insns = 0;
1534: }
1535:
1536: if (pending_read_mems)
1537: {
1538: prev_link = pending_read_mems;
1539: link = XEXP (prev_link, 1);
1540:
1541: while (link)
1542: {
1543: prev_link = link;
1544: link = XEXP (link, 1);
1545: }
1546:
1547: XEXP (prev_link, 1) = unused_expr_list;
1548: unused_expr_list = pending_read_mems;
1549: pending_read_mems = 0;
1550: }
1551:
1552: if (pending_write_mems)
1553: {
1554: prev_link = pending_write_mems;
1555: link = XEXP (prev_link, 1);
1556:
1557: while (link)
1558: {
1559: prev_link = link;
1560: link = XEXP (link, 1);
1561: }
1562:
1563: XEXP (prev_link, 1) = unused_expr_list;
1564: unused_expr_list = pending_write_mems;
1565: pending_write_mems = 0;
1566: }
1567: }
1568:
1569: /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
1570: The MEM is a memory reference contained within INSN, which we are saving
1571: so that we can do memory aliasing on it. */
1572:
1573: static void
1574: add_insn_mem_dependence (insn_list, mem_list, insn, mem)
1575: rtx *insn_list, *mem_list, insn, mem;
1576: {
1577: register rtx link;
1578:
1579: if (unused_insn_list)
1580: {
1581: link = unused_insn_list;
1582: unused_insn_list = XEXP (link, 1);
1583: }
1584: else
1585: link = rtx_alloc (INSN_LIST);
1586: XEXP (link, 0) = insn;
1587: XEXP (link, 1) = *insn_list;
1588: *insn_list = link;
1589:
1590: if (unused_expr_list)
1591: {
1592: link = unused_expr_list;
1593: unused_expr_list = XEXP (link, 1);
1594: }
1595: else
1596: link = rtx_alloc (EXPR_LIST);
1597: XEXP (link, 0) = mem;
1598: XEXP (link, 1) = *mem_list;
1599: *mem_list = link;
1600:
1601: pending_lists_length++;
1602: }
1603:
1604: /* Make a dependency between every memory reference on the pending lists
1605: and INSN, thus flushing the pending lists. */
1606:
1607: static void
1608: flush_pending_lists (insn)
1609: rtx insn;
1610: {
1611: rtx link;
1612:
1613: while (pending_read_insns)
1614: {
1615: add_dependence (insn, XEXP (pending_read_insns, 0), REG_DEP_ANTI);
1616:
1617: link = pending_read_insns;
1618: pending_read_insns = XEXP (pending_read_insns, 1);
1619: XEXP (link, 1) = unused_insn_list;
1620: unused_insn_list = link;
1621:
1622: link = pending_read_mems;
1623: pending_read_mems = XEXP (pending_read_mems, 1);
1624: XEXP (link, 1) = unused_expr_list;
1625: unused_expr_list = link;
1626: }
1627: while (pending_write_insns)
1628: {
1629: add_dependence (insn, XEXP (pending_write_insns, 0), REG_DEP_ANTI);
1630:
1631: link = pending_write_insns;
1632: pending_write_insns = XEXP (pending_write_insns, 1);
1633: XEXP (link, 1) = unused_insn_list;
1634: unused_insn_list = link;
1635:
1636: link = pending_write_mems;
1637: pending_write_mems = XEXP (pending_write_mems, 1);
1638: XEXP (link, 1) = unused_expr_list;
1639: unused_expr_list = link;
1640: }
1641: pending_lists_length = 0;
1642:
1643: if (last_pending_memory_flush)
1644: add_dependence (insn, last_pending_memory_flush, REG_DEP_ANTI);
1645:
1646: last_pending_memory_flush = insn;
1647: }
1648:
1649: /* Analyze a single SET or CLOBBER rtx, X, creating all dependencies generated
1650: by the write to the destination of X, and reads of everything mentioned. */
1651:
1652: static void
1653: sched_analyze_1 (x, insn)
1654: rtx x;
1655: rtx insn;
1656: {
1657: register int regno;
1658: register rtx dest = SET_DEST (x);
1659:
1660: if (dest == 0)
1661: return;
1662:
1663: while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
1664: || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
1665: {
1666: if (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
1667: {
1668: /* The second and third arguments are values read by this insn. */
1669: sched_analyze_2 (XEXP (dest, 1), insn);
1670: sched_analyze_2 (XEXP (dest, 2), insn);
1671: }
1672: dest = SUBREG_REG (dest);
1673: }
1674:
1675: if (GET_CODE (dest) == REG)
1676: {
1677: register int offset, bit, i;
1678:
1679: regno = REGNO (dest);
1680:
1681: /* A hard reg in a wide mode may really be multiple registers.
1682: If so, mark all of them just like the first. */
1683: if (regno < FIRST_PSEUDO_REGISTER)
1684: {
1685: i = HARD_REGNO_NREGS (regno, GET_MODE (dest));
1686: while (--i >= 0)
1687: {
1688: rtx u;
1689:
1690: for (u = reg_last_uses[regno+i]; u; u = XEXP (u, 1))
1691: add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
1692: reg_last_uses[regno + i] = 0;
1693: if (reg_last_sets[regno + i])
1694: add_dependence (insn, reg_last_sets[regno + i],
1695: REG_DEP_OUTPUT);
1696: reg_last_sets[regno + i] = insn;
1697: if ((call_used_regs[i] || global_regs[i])
1698: && last_function_call)
1699: /* Function calls clobber all call_used regs. */
1700: add_dependence (insn, last_function_call, REG_DEP_ANTI);
1701: }
1702: }
1703: else
1704: {
1705: rtx u;
1706:
1707: for (u = reg_last_uses[regno]; u; u = XEXP (u, 1))
1708: add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
1709: reg_last_uses[regno] = 0;
1710: if (reg_last_sets[regno])
1711: add_dependence (insn, reg_last_sets[regno], REG_DEP_OUTPUT);
1712: reg_last_sets[regno] = insn;
1713:
1714: /* Pseudos that are REG_EQUIV to something may be replaced
1715: by that during reloading. We need only add dependencies for
1716: the address in the REG_EQUIV note. */
1717: if (! reload_completed
1718: && reg_known_equiv_p[regno]
1719: && GET_CODE (reg_known_value[regno]) == MEM)
1720: sched_analyze_2 (XEXP (reg_known_value[regno], 0), insn);
1721:
1722: /* Don't let it cross a call after scheduling if it doesn't
1723: already cross one. */
1724: if (reg_n_calls_crossed[regno] == 0 && last_function_call)
1725: add_dependence (insn, last_function_call, REG_DEP_ANTI);
1726: }
1727: }
1728: else if (GET_CODE (dest) == MEM)
1729: {
1730: /* Writing memory. */
1731:
1732: if (pending_lists_length > 32)
1733: {
1734: /* Flush all pending reads and writes to prevent the pending lists
1735: from getting any larger. Insn scheduling runs too slowly when
1736: these lists get long. The number 32 was chosen because it
1737: seems like a reasonable number. When compiling GCC with itself,
1738: this flush occurs 8 times for sparc, and 10 times for m88k using
1739: the number 32. */
1740: flush_pending_lists (insn);
1741: }
1742: else
1743: {
1744: rtx pending, pending_mem;
1745:
1746: pending = pending_read_insns;
1747: pending_mem = pending_read_mems;
1748: while (pending)
1749: {
1750: /* If a dependency already exists, don't create a new one. */
1751: if (! find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
1752: if (anti_dependence (XEXP (pending_mem, 0), dest))
1753: add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
1754:
1755: pending = XEXP (pending, 1);
1756: pending_mem = XEXP (pending_mem, 1);
1757: }
1758:
1759: pending = pending_write_insns;
1760: pending_mem = pending_write_mems;
1761: while (pending)
1762: {
1763: /* If a dependency already exists, don't create a new one. */
1764: if (! find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
1765: if (output_dependence (XEXP (pending_mem, 0), dest))
1766: add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
1767:
1768: pending = XEXP (pending, 1);
1769: pending_mem = XEXP (pending_mem, 1);
1770: }
1771:
1772: if (last_pending_memory_flush)
1773: add_dependence (insn, last_pending_memory_flush, REG_DEP_ANTI);
1774:
1775: add_insn_mem_dependence (&pending_write_insns, &pending_write_mems,
1776: insn, dest);
1777: }
1778: sched_analyze_2 (XEXP (dest, 0), insn);
1779: }
1780:
1781: /* Analyze reads. */
1782: if (GET_CODE (x) == SET)
1783: sched_analyze_2 (SET_SRC (x), insn);
1784: }
1785:
1786: /* Analyze the uses of memory and registers in rtx X in INSN. */
1787:
1788: static void
1789: sched_analyze_2 (x, insn)
1790: rtx x;
1791: rtx insn;
1792: {
1793: register int i;
1794: register int j;
1795: register enum rtx_code code;
1796: register char *fmt;
1797:
1798: if (x == 0)
1799: return;
1800:
1801: code = GET_CODE (x);
1802:
1803: switch (code)
1804: {
1805: case CONST_INT:
1806: case CONST_DOUBLE:
1807: case SYMBOL_REF:
1808: case CONST:
1809: case LABEL_REF:
1810: /* Ignore constants. Note that we must handle CONST_DOUBLE here
1811: because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but
1812: this does not mean that this insn is using cc0. */
1813: return;
1814:
1815: #ifdef HAVE_cc0
1816: case CC0:
1817: {
1818: rtx link, prev;
1819:
1820: /* There may be a note before this insn now, but all notes will
1821: be removed before we actually try to schedule the insns, so
1822: it won't cause a problem later. We must avoid it here though. */
1823:
1824: /* User of CC0 depends on immediately preceding insn. */
1825: SCHED_GROUP_P (insn) = 1;
1826:
1827: /* Make a copy of all dependencies on the immediately previous insn,
1828: and add to this insn. This is so that all the dependencies will
1829: apply to the group. Remove an explicit dependence on this insn
1830: as SCHED_GROUP_P now represents it. */
1831:
1832: prev = PREV_INSN (insn);
1833: while (GET_CODE (prev) == NOTE)
1834: prev = PREV_INSN (prev);
1835:
1836: if (find_insn_list (prev, LOG_LINKS (insn)))
1837: remove_dependence (insn, prev);
1838:
1839: for (link = LOG_LINKS (prev); link; link = XEXP (link, 1))
1840: add_dependence (insn, XEXP (link, 0), REG_NOTE_KIND (link));
1841:
1842: return;
1843: }
1844: #endif
1845:
1846: case REG:
1847: {
1848: int regno = REGNO (x);
1849: if (regno < FIRST_PSEUDO_REGISTER)
1850: {
1851: int i;
1852:
1853: i = HARD_REGNO_NREGS (regno, GET_MODE (x));
1854: while (--i >= 0)
1855: {
1856: reg_last_uses[regno + i]
1857: = gen_rtx (INSN_LIST, VOIDmode,
1858: insn, reg_last_uses[regno + i]);
1859: if (reg_last_sets[regno + i])
1860: add_dependence (insn, reg_last_sets[regno + i], 0);
1861: if ((call_used_regs[regno + i] || global_regs[regno + i])
1862: && last_function_call)
1863: /* Function calls clobber all call_used regs. */
1864: add_dependence (insn, last_function_call, REG_DEP_ANTI);
1865: }
1866: }
1867: else
1868: {
1869: reg_last_uses[regno]
1870: = gen_rtx (INSN_LIST, VOIDmode, insn, reg_last_uses[regno]);
1871: if (reg_last_sets[regno])
1872: add_dependence (insn, reg_last_sets[regno], 0);
1873:
1874: /* Pseudos that are REG_EQUIV to something may be replaced
1875: by that during reloading. We need only add dependencies for
1876: the address in the REG_EQUIV note. */
1877: if (! reload_completed
1878: && reg_known_equiv_p[regno]
1879: && GET_CODE (reg_known_value[regno]) == MEM)
1880: sched_analyze_2 (XEXP (reg_known_value[regno], 0), insn);
1881:
1882: /* If the register does not already cross any calls, then add this
1883: insn to the sched_before_next_call list so that it will still
1884: not cross calls after scheduling. */
1885: if (reg_n_calls_crossed[regno] == 0)
1886: add_dependence (sched_before_next_call, insn, REG_DEP_ANTI);
1887: }
1888: return;
1889: }
1890:
1891: case MEM:
1892: {
1893: /* Reading memory. */
1894:
1895: rtx pending, pending_mem;
1896:
1897: pending = pending_read_insns;
1898: pending_mem = pending_read_mems;
1899: while (pending)
1900: {
1901: /* If a dependency already exists, don't create a new one. */
1902: if (! find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
1903: if (read_dependence (XEXP (pending_mem, 0), x))
1904: add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
1905:
1906: pending = XEXP (pending, 1);
1907: pending_mem = XEXP (pending_mem, 1);
1908: }
1909:
1910: pending = pending_write_insns;
1911: pending_mem = pending_write_mems;
1912: while (pending)
1913: {
1914: /* If a dependency already exists, don't create a new one. */
1915: if (! find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
1916: if (true_dependence (XEXP (pending_mem, 0), x))
1917: add_dependence (insn, XEXP (pending, 0), 0);
1918:
1919: pending = XEXP (pending, 1);
1920: pending_mem = XEXP (pending_mem, 1);
1921: }
1922: if (last_pending_memory_flush)
1923: add_dependence (insn, last_pending_memory_flush, REG_DEP_ANTI);
1924:
1925: /* Always add these dependencies to pending_reads, since
1926: this insn may be followed by a write. */
1927: add_insn_mem_dependence (&pending_read_insns, &pending_read_mems,
1928: insn, x);
1929:
1930: /* Take advantage of tail recursion here. */
1931: sched_analyze_2 (XEXP (x, 0), insn);
1932: return;
1933: }
1934:
1935: case ASM_OPERANDS:
1936: case ASM_INPUT:
1937: case UNSPEC_VOLATILE:
1938: case TRAP_IF:
1939: {
1940: rtx u;
1941:
1942: /* Traditional and volatile asm instructions must be considered to use
1943: and clobber all hard registers, all pseudo-registers and all of
1944: memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
1945:
1946: Consider for instance a volatile asm that changes the fpu rounding
1947: mode. An insn should not be moved across this even if it only uses
1948: pseudo-regs because it might give an incorrectly rounded result. */
1949: if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
1950: {
1951: int max_reg = max_reg_num ();
1952: for (i = 0; i < max_reg; i++)
1953: {
1954: for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
1955: add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
1956: reg_last_uses[i] = 0;
1957: if (reg_last_sets[i])
1958: add_dependence (insn, reg_last_sets[i], 0);
1959: reg_last_sets[i] = insn;
1960: }
1961:
1962: flush_pending_lists (insn);
1963: }
1964:
1965: /* For all ASM_OPERANDS, we must traverse the vector of input operands.
1966: We can not just fall through here since then we would be confused
1967: by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
1968: traditional asms unlike their normal usage. */
1969:
1970: if (code == ASM_OPERANDS)
1971: {
1972: for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
1973: sched_analyze_2 (ASM_OPERANDS_INPUT (x, j), insn);
1974: return;
1975: }
1976: break;
1977: }
1978:
1979: case PRE_DEC:
1980: case POST_DEC:
1981: case PRE_INC:
1982: case POST_INC:
1983: /* These both read and modify the result. We must handle them as writes
1984: to get proper dependencies for following instructions. We must handle
1985: them as reads to get proper dependencies from this to previous
1986: instructions. Thus we need to pass them to both sched_analyze_1
1987: and sched_analyze_2. We must call sched_analyze_2 first in order
1988: to get the proper antecedent for the read. */
1989: sched_analyze_2 (XEXP (x, 0), insn);
1990: sched_analyze_1 (x, insn);
1991: return;
1992: }
1993:
1994: /* Other cases: walk the insn. */
1995: fmt = GET_RTX_FORMAT (code);
1996: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1997: {
1998: if (fmt[i] == 'e')
1999: sched_analyze_2 (XEXP (x, i), insn);
2000: else if (fmt[i] == 'E')
2001: for (j = 0; j < XVECLEN (x, i); j++)
2002: sched_analyze_2 (XVECEXP (x, i, j), insn);
2003: }
2004: }
2005:
2006: /* Analyze an INSN with pattern X to find all dependencies. */
2007:
2008: static void
2009: sched_analyze_insn (x, insn)
2010: rtx x, insn;
2011: {
2012: register RTX_CODE code = GET_CODE (x);
2013: rtx link;
2014:
2015: if (code == SET || code == CLOBBER)
2016: sched_analyze_1 (x, insn);
2017: else if (code == PARALLEL)
2018: {
2019: register int i;
2020: for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
2021: {
2022: code = GET_CODE (XVECEXP (x, 0, i));
2023: if (code == SET || code == CLOBBER)
2024: sched_analyze_1 (XVECEXP (x, 0, i), insn);
2025: else
2026: sched_analyze_2 (XVECEXP (x, 0, i), insn);
2027: }
2028: }
2029: else
2030: sched_analyze_2 (x, insn);
2031:
2032: /* Handle function calls and function returns created by the epilogue
2033: threading code. */
2034: if (GET_CODE (insn) == CALL_INSN || GET_CODE (insn) == JUMP_INSN)
2035: {
2036: rtx dep_insn;
2037: rtx prev_dep_insn;
2038:
2039: /* When scheduling instructions, we make sure calls don't lose their
2040: accompanying USE insns by depending them one on another in order.
2041:
2042: Also, we must do the same thing for returns created by the epilogue
2043: threading code. Note this code works only in this special case,
2044: because other passes make no guarantee that they will never emit
2045: an instruction between a USE and a RETURN. There is such a guarantee
2046: for USE instructions immediately before a call. */
2047:
2048: prev_dep_insn = insn;
2049: dep_insn = PREV_INSN (insn);
2050: while (GET_CODE (dep_insn) == INSN
2051: && GET_CODE (PATTERN (dep_insn)) == USE)
2052: {
2053: SCHED_GROUP_P (prev_dep_insn) = 1;
2054:
2055: /* Make a copy of all dependencies on dep_insn, and add to insn.
2056: This is so that all of the dependencies will apply to the
2057: group. */
2058:
2059: for (link = LOG_LINKS (dep_insn); link; link = XEXP (link, 1))
2060: add_dependence (insn, XEXP (link, 0), REG_NOTE_KIND (link));
2061:
2062: prev_dep_insn = dep_insn;
2063: dep_insn = PREV_INSN (dep_insn);
2064: }
2065: }
2066: }
2067:
2068: /* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
2069: for every dependency. */
2070:
2071: static int
2072: sched_analyze (head, tail)
2073: rtx head, tail;
2074: {
2075: register rtx insn;
2076: register int n_insns = 0;
2077: register rtx u;
2078: register int luid = 0;
2079:
2080: for (insn = head; ; insn = NEXT_INSN (insn))
2081: {
2082: INSN_LUID (insn) = luid++;
2083:
2084: if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
2085: {
2086: sched_analyze_insn (PATTERN (insn), insn);
2087: n_insns += 1;
2088: }
2089: else if (GET_CODE (insn) == CALL_INSN)
2090: {
2091: rtx dest = 0;
2092: rtx x;
2093: register int i;
2094:
2095: /* Any instruction using a hard register which may get clobbered
2096: by a call needs to be marked as dependent on this call.
2097: This prevents a use of a hard return reg from being moved
2098: past a void call (i.e. it does not explicitly set the hard
2099: return reg). */
2100:
2101: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2102: if (call_used_regs[i] || global_regs[i])
2103: {
2104: for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
2105: add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
2106: reg_last_uses[i] = 0;
2107: if (reg_last_sets[i])
2108: add_dependence (insn, reg_last_sets[i], REG_DEP_ANTI);
2109: reg_last_sets[i] = insn;
2110: /* Insn, being a CALL_INSN, magically depends on
2111: `last_function_call' already. */
2112: }
2113:
2114: /* For each insn which shouldn't cross a call, add a dependence
2115: between that insn and this call insn. */
2116: x = LOG_LINKS (sched_before_next_call);
2117: while (x)
2118: {
2119: add_dependence (insn, XEXP (x, 0), REG_DEP_ANTI);
2120: x = XEXP (x, 1);
2121: }
2122: LOG_LINKS (sched_before_next_call) = 0;
2123:
2124: sched_analyze_insn (PATTERN (insn), insn);
2125:
2126: /* We don't need to flush memory for a function call which does
2127: not involve memory. */
2128: if (! CONST_CALL_P (insn))
2129: {
2130: /* In the absence of interprocedural alias analysis,
2131: we must flush all pending reads and writes, and
2132: start new dependencies starting from here. */
2133: flush_pending_lists (insn);
2134: }
2135:
2136: /* Depend this function call (actually, the user of this
2137: function call) on all hard register clobberage. */
2138: last_function_call = insn;
2139: n_insns += 1;
2140: }
2141:
2142: if (insn == tail)
2143: return n_insns;
2144: }
2145: }
2146:
2147: /* Called when we see a set of a register. If death is true, then we are
2148: scanning backwards. Mark that register as unborn. If nobody says
2149: otherwise, that is how things will remain. If death is false, then we
2150: are scanning forwards. Mark that register as being born. */
2151:
2152: static void
2153: sched_note_set (b, x, death)
2154: int b;
2155: rtx x;
2156: int death;
2157: {
2158: register int regno, j;
2159: register rtx reg = SET_DEST (x);
2160: int subreg_p = 0;
2161:
2162: if (reg == 0)
2163: return;
2164:
2165: while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == STRICT_LOW_PART
2166: || GET_CODE (reg) == SIGN_EXTRACT || GET_CODE (reg) == ZERO_EXTRACT)
2167: {
2168: /* Must treat modification of just one hardware register of a multi-reg
2169: value or just a byte field of a register exactly the same way that
2170: mark_set_1 in flow.c does, i.e. anything except a paradoxical subreg
2171: does not kill the entire register. */
2172: if (GET_CODE (reg) != SUBREG
2173: || REG_SIZE (SUBREG_REG (reg)) > REG_SIZE (reg))
2174: subreg_p = 1;
2175:
2176: reg = SUBREG_REG (reg);
2177: }
2178:
2179: if (GET_CODE (reg) != REG)
2180: return;
2181:
2182: /* Global registers are always live, so the code below does not apply
2183: to them. */
2184:
2185: regno = REGNO (reg);
2186: if (regno >= FIRST_PSEUDO_REGISTER || ! global_regs[regno])
2187: {
2188: register int offset = regno / REGSET_ELT_BITS;
2189: register REGSET_ELT_TYPE bit
2190: = (REGSET_ELT_TYPE) 1 << (regno % REGSET_ELT_BITS);
2191:
2192: if (death)
2193: {
2194: /* If we only set part of the register, then this set does not
2195: kill it. */
2196: if (subreg_p)
2197: return;
2198:
2199: /* Try killing this register. */
2200: if (regno < FIRST_PSEUDO_REGISTER)
2201: {
2202: int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
2203: while (--j >= 0)
2204: {
2205: offset = (regno + j) / REGSET_ELT_BITS;
2206: bit = (REGSET_ELT_TYPE) 1 << ((regno + j) % REGSET_ELT_BITS);
2207:
2208: bb_live_regs[offset] &= ~bit;
2209: bb_dead_regs[offset] |= bit;
2210: }
2211: }
2212: else
2213: {
2214: bb_live_regs[offset] &= ~bit;
2215: bb_dead_regs[offset] |= bit;
2216: }
2217: }
2218: else
2219: {
2220: /* Make the register live again. */
2221: if (regno < FIRST_PSEUDO_REGISTER)
2222: {
2223: int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
2224: while (--j >= 0)
2225: {
2226: offset = (regno + j) / REGSET_ELT_BITS;
2227: bit = (REGSET_ELT_TYPE) 1 << ((regno + j) % REGSET_ELT_BITS);
2228:
2229: bb_live_regs[offset] |= bit;
2230: bb_dead_regs[offset] &= ~bit;
2231: }
2232: }
2233: else
2234: {
2235: bb_live_regs[offset] |= bit;
2236: bb_dead_regs[offset] &= ~bit;
2237: }
2238: }
2239: }
2240: }
2241:
2242: /* Macros and functions for keeping the priority queue sorted, and
2243: dealing with queueing and unqueueing of instructions. */
2244:
2245: #define SCHED_SORT(READY, NEW_READY, OLD_READY) \
2246: do { if ((NEW_READY) - (OLD_READY) == 1) \
2247: swap_sort (READY, NEW_READY); \
2248: else if ((NEW_READY) - (OLD_READY) > 1) \
2249: qsort (READY, NEW_READY, sizeof (rtx), rank_for_schedule); } \
2250: while (0)
2251:
2252: /* Returns a positive value if y is preferred; returns a negative value if
2253: x is preferred. Should never return 0, since that will make the sort
2254: unstable. */
2255:
2256: static int
2257: rank_for_schedule (x, y)
2258: rtx *x, *y;
2259: {
2260: rtx tmp = *y;
2261: rtx tmp2 = *x;
2262: rtx link;
2263: int tmp_class, tmp2_class;
2264: int value;
2265:
2266: /* Choose the instruction with the highest priority, if different. */
2267: if (value = INSN_PRIORITY (tmp) - INSN_PRIORITY (tmp2))
2268: return value;
2269:
2270: if (last_scheduled_insn)
2271: {
2272: /* Classify the instructions into three classes:
2273: 1) Data dependent on last schedule insn.
2274: 2) Anti/Output dependent on last scheduled insn.
2275: 3) Independent of last scheduled insn, or has latency of one.
2276: Choose the insn from the highest numbered class if different. */
2277: link = find_insn_list (tmp, LOG_LINKS (last_scheduled_insn));
2278: if (link == 0 || insn_cost (tmp, link, last_scheduled_insn) == 1)
2279: tmp_class = 3;
2280: else if (REG_NOTE_KIND (link) == 0) /* Data dependence. */
2281: tmp_class = 1;
2282: else
2283: tmp_class = 2;
2284:
2285: link = find_insn_list (tmp2, LOG_LINKS (last_scheduled_insn));
2286: if (link == 0 || insn_cost (tmp2, link, last_scheduled_insn) == 1)
2287: tmp2_class = 3;
2288: else if (REG_NOTE_KIND (link) == 0) /* Data dependence. */
2289: tmp2_class = 1;
2290: else
2291: tmp2_class = 2;
2292:
2293: if (value = tmp_class - tmp2_class)
2294: return value;
2295: }
2296:
2297: /* If insns are equally good, sort by INSN_LUID (original insn order),
2298: so that we make the sort stable. This minimizes instruction movement,
2299: thus minimizing sched's effect on debugging and cross-jumping. */
2300: return INSN_LUID (tmp) - INSN_LUID (tmp2);
2301: }
2302:
2303: /* Resort the array A in which only element at index N may be out of order. */
2304:
2305: __inline static void
2306: swap_sort (a, n)
2307: rtx *a;
2308: int n;
2309: {
2310: rtx insn = a[n-1];
2311: int i = n-2;
2312:
2313: while (i >= 0 && rank_for_schedule (a+i, &insn) >= 0)
2314: {
2315: a[i+1] = a[i];
2316: i -= 1;
2317: }
2318: a[i+1] = insn;
2319: }
2320:
2321: static int max_priority;
2322:
2323: /* Add INSN to the insn queue so that it fires at least N_CYCLES
2324: before the currently executing insn. */
2325:
2326: __inline static void
2327: queue_insn (insn, n_cycles)
2328: rtx insn;
2329: int n_cycles;
2330: {
2331: int next_q = NEXT_Q_AFTER (q_ptr, n_cycles);
2332: NEXT_INSN (insn) = insn_queue[next_q];
2333: insn_queue[next_q] = insn;
2334: q_size += 1;
2335: }
2336:
2337: /* Return nonzero if PAT is the pattern of an insn which makes a
2338: register live. */
2339:
2340: __inline static int
2341: birthing_insn_p (pat)
2342: rtx pat;
2343: {
2344: int j;
2345:
2346: if (reload_completed == 1)
2347: return 0;
2348:
2349: if (GET_CODE (pat) == SET
2350: && GET_CODE (SET_DEST (pat)) == REG)
2351: {
2352: rtx dest = SET_DEST (pat);
2353: int i = REGNO (dest);
2354: int offset = i / REGSET_ELT_BITS;
2355: REGSET_ELT_TYPE bit = (REGSET_ELT_TYPE) 1 << (i % REGSET_ELT_BITS);
2356:
2357: /* It would be more accurate to use refers_to_regno_p or
2358: reg_mentioned_p to determine when the dest is not live before this
2359: insn. */
2360:
2361: if (bb_live_regs[offset] & bit)
2362: return (reg_n_sets[i] == 1);
2363:
2364: return 0;
2365: }
2366: if (GET_CODE (pat) == PARALLEL)
2367: {
2368: for (j = 0; j < XVECLEN (pat, 0); j++)
2369: if (birthing_insn_p (XVECEXP (pat, 0, j)))
2370: return 1;
2371: }
2372: return 0;
2373: }
2374:
2375: /* PREV is an insn that is ready to execute. Adjust its priority if that
2376: will help shorten register lifetimes. */
2377:
2378: __inline static void
2379: adjust_priority (prev)
2380: rtx prev;
2381: {
2382: /* Trying to shorten register lives after reload has completed
2383: is useless and wrong. It gives inaccurate schedules. */
2384: if (reload_completed == 0)
2385: {
2386: rtx note;
2387: int n_deaths = 0;
2388:
2389: /* ??? This code has no effect, because REG_DEAD notes are removed
2390: before we ever get here. */
2391: for (note = REG_NOTES (prev); note; note = XEXP (note, 1))
2392: if (REG_NOTE_KIND (note) == REG_DEAD)
2393: n_deaths += 1;
2394:
2395: /* Defer scheduling insns which kill registers, since that
2396: shortens register lives. Prefer scheduling insns which
2397: make registers live for the same reason. */
2398: switch (n_deaths)
2399: {
2400: default:
2401: INSN_PRIORITY (prev) >>= 3;
2402: break;
2403: case 3:
2404: INSN_PRIORITY (prev) >>= 2;
2405: break;
2406: case 2:
2407: case 1:
2408: INSN_PRIORITY (prev) >>= 1;
2409: break;
2410: case 0:
2411: if (birthing_insn_p (PATTERN (prev)))
2412: {
2413: int max = max_priority;
2414:
2415: if (max > INSN_PRIORITY (prev))
2416: INSN_PRIORITY (prev) = max;
2417: }
2418: break;
2419: }
2420: }
2421: }
2422:
2423: /* INSN is the "currently executing insn". Launch each insn which was
2424: waiting on INSN (in the backwards dataflow sense). READY is a
2425: vector of insns which are ready to fire. N_READY is the number of
2426: elements in READY. CLOCK is the current virtual cycle. */
2427:
2428: static int
2429: schedule_insn (insn, ready, n_ready, clock)
2430: rtx insn;
2431: rtx *ready;
2432: int n_ready;
2433: int clock;
2434: {
2435: rtx link;
2436: int new_ready = n_ready;
2437:
2438: if (MAX_BLOCKAGE > 1)
2439: schedule_unit (insn_unit (insn), insn, clock);
2440:
2441: if (LOG_LINKS (insn) == 0)
2442: return n_ready;
2443:
2444: /* This is used by the function adjust_priority above. */
2445: if (n_ready > 0)
2446: max_priority = MAX (INSN_PRIORITY (ready[0]), INSN_PRIORITY (insn));
2447: else
2448: max_priority = INSN_PRIORITY (insn);
2449:
2450: for (link = LOG_LINKS (insn); link != 0; link = XEXP (link, 1))
2451: {
2452: rtx prev = XEXP (link, 0);
2453: int cost = insn_cost (prev, link, insn);
2454:
2455: if ((INSN_REF_COUNT (prev) -= 1) != 0)
2456: {
2457: /* We satisfied one requirement to fire PREV. Record the earliest
2458: time when PREV can fire. No need to do this if the cost is 1,
2459: because PREV can fire no sooner than the next cycle. */
2460: if (cost > 1)
2461: INSN_TICK (prev) = MAX (INSN_TICK (prev), clock + cost);
2462: }
2463: else
2464: {
2465: /* We satisfied the last requirement to fire PREV. Ensure that all
2466: timing requirements are satisfied. */
2467: if (INSN_TICK (prev) - clock > cost)
2468: cost = INSN_TICK (prev) - clock;
2469:
2470: /* Adjust the priority of PREV and either put it on the ready
2471: list or queue it. */
2472: adjust_priority (prev);
2473: if (cost <= 1)
2474: ready[new_ready++] = prev;
2475: else
2476: queue_insn (prev, cost);
2477: }
2478: }
2479:
2480: return new_ready;
2481: }
2482:
2483: /* Given N_READY insns in the ready list READY at time CLOCK, queue
2484: those that are blocked due to function unit hazards and rearrange
2485: the remaining ones to minimize subsequent function unit hazards. */
2486:
2487: static int
2488: schedule_select (ready, n_ready, clock, file)
2489: rtx *ready;
2490: int n_ready, clock;
2491: FILE *file;
2492: {
2493: int pri = INSN_PRIORITY (ready[0]);
2494: int i, j, k, q, cost, best_cost, best_insn = 0, new_ready = n_ready;
2495: rtx insn;
2496:
2497: /* Work down the ready list in groups of instructions with the same
2498: priority value. Queue insns in the group that are blocked and
2499: select among those that remain for the one with the largest
2500: potential hazard. */
2501: for (i = 0; i < n_ready; i = j)
2502: {
2503: int opri = pri;
2504: for (j = i + 1; j < n_ready; j++)
2505: if ((pri = INSN_PRIORITY (ready[j])) != opri)
2506: break;
2507:
2508: /* Queue insns in the group that are blocked. */
2509: for (k = i, q = 0; k < j; k++)
2510: {
2511: insn = ready[k];
2512: if ((cost = actual_hazard (insn_unit (insn), insn, clock, 0)) != 0)
2513: {
2514: q++;
2515: ready[k] = 0;
2516: queue_insn (insn, cost);
2517: if (file)
2518: fprintf (file, "\n;; blocking insn %d for %d cycles",
2519: INSN_UID (insn), cost);
2520: }
2521: }
2522: new_ready -= q;
2523:
2524: /* Check the next group if all insns were queued. */
2525: if (j - i - q == 0)
2526: continue;
2527:
2528: /* If more than one remains, select the first one with the largest
2529: potential hazard. */
2530: else if (j - i - q > 1)
2531: {
2532: best_cost = -1;
2533: for (k = i; k < j; k++)
2534: {
2535: if ((insn = ready[k]) == 0)
2536: continue;
2537: if ((cost = potential_hazard (insn_unit (insn), insn, 0))
2538: > best_cost)
2539: {
2540: best_cost = cost;
2541: best_insn = k;
2542: }
2543: }
2544: }
2545: /* We have found a suitable insn to schedule. */
2546: break;
2547: }
2548:
2549: /* Move the best insn to be front of the ready list. */
2550: if (best_insn != 0)
2551: {
2552: if (file)
2553: {
2554: fprintf (file, ", now");
2555: for (i = 0; i < n_ready; i++)
2556: if (ready[i])
2557: fprintf (file, " %d", INSN_UID (ready[i]));
2558: fprintf (file, "\n;; insn %d has a greater potential hazard",
2559: INSN_UID (ready[best_insn]));
2560: }
2561: for (i = best_insn; i > 0; i--)
2562: {
2563: insn = ready[i-1];
2564: ready[i-1] = ready[i];
2565: ready[i] = insn;
2566: }
2567: }
2568:
2569: /* Compact the ready list. */
2570: if (new_ready < n_ready)
2571: for (i = j = 0; i < n_ready; i++)
2572: if (ready[i])
2573: ready[j++] = ready[i];
2574:
2575: return new_ready;
2576: }
2577:
2578: /* Add a REG_DEAD note for REG to INSN, reusing a REG_DEAD note from the
2579: dead_notes list. */
2580:
2581: static void
2582: create_reg_dead_note (reg, insn)
2583: rtx reg, insn;
2584: {
2585: rtx link, backlink;
2586:
2587: /* The number of registers killed after scheduling must be the same as the
2588: number of registers killed before scheduling. The number of REG_DEAD
2589: notes may not be conserved, i.e. two SImode hard register REG_DEAD notes
2590: might become one DImode hard register REG_DEAD note, but the number of
2591: registers killed will be conserved.
2592:
2593: We carefully remove REG_DEAD notes from the dead_notes list, so that
2594: there will be none left at the end. If we run out early, then there
2595: is a bug somewhere in flow, combine and/or sched. */
2596:
2597: if (dead_notes == 0)
2598: {
2599: #if 1
2600: abort ();
2601: #else
2602: link = rtx_alloc (EXPR_LIST);
2603: PUT_REG_NOTE_KIND (link, REG_DEAD);
2604: #endif
2605: }
2606: else
2607: {
2608: /* Number of regs killed by REG. */
2609: int regs_killed = (REGNO (reg) >= FIRST_PSEUDO_REGISTER ? 1
2610: : HARD_REGNO_NREGS (REGNO (reg), GET_MODE (reg)));
2611: /* Number of regs killed by REG_DEAD notes taken off the list. */
2612: int reg_note_regs;
2613:
2614: link = dead_notes;
2615: reg_note_regs = (REGNO (XEXP (link, 0)) >= FIRST_PSEUDO_REGISTER ? 1
2616: : HARD_REGNO_NREGS (REGNO (XEXP (link, 0)),
2617: GET_MODE (XEXP (link, 0))));
2618: while (reg_note_regs < regs_killed)
2619: {
2620: link = XEXP (link, 1);
2621: reg_note_regs += (REGNO (XEXP (link, 0)) >= FIRST_PSEUDO_REGISTER ? 1
2622: : HARD_REGNO_NREGS (REGNO (XEXP (link, 0)),
2623: GET_MODE (XEXP (link, 0))));
2624: }
2625: dead_notes = XEXP (link, 1);
2626:
2627: /* If we took too many regs kills off, put the extra ones back. */
2628: while (reg_note_regs > regs_killed)
2629: {
2630: rtx temp_reg, temp_link;
2631:
2632: temp_reg = gen_rtx (REG, word_mode, 0);
2633: temp_link = rtx_alloc (EXPR_LIST);
2634: PUT_REG_NOTE_KIND (temp_link, REG_DEAD);
2635: XEXP (temp_link, 0) = temp_reg;
2636: XEXP (temp_link, 1) = dead_notes;
2637: dead_notes = temp_link;
2638: reg_note_regs--;
2639: }
2640: }
2641:
2642: XEXP (link, 0) = reg;
2643: XEXP (link, 1) = REG_NOTES (insn);
2644: REG_NOTES (insn) = link;
2645: }
2646:
2647: /* Subroutine on attach_deaths_insn--handles the recursive search
2648: through INSN. If SET_P is true, then x is being modified by the insn. */
2649:
2650: static void
2651: attach_deaths (x, insn, set_p)
2652: rtx x;
2653: rtx insn;
2654: int set_p;
2655: {
2656: register int i;
2657: register int j;
2658: register enum rtx_code code;
2659: register char *fmt;
2660:
2661: if (x == 0)
2662: return;
2663:
2664: code = GET_CODE (x);
2665:
2666: switch (code)
2667: {
2668: case CONST_INT:
2669: case CONST_DOUBLE:
2670: case LABEL_REF:
2671: case SYMBOL_REF:
2672: case CONST:
2673: case CODE_LABEL:
2674: case PC:
2675: case CC0:
2676: /* Get rid of the easy cases first. */
2677: return;
2678:
2679: case REG:
2680: {
2681: /* If the register dies in this insn, queue that note, and mark
2682: this register as needing to die. */
2683: /* This code is very similar to mark_used_1 (if set_p is false)
2684: and mark_set_1 (if set_p is true) in flow.c. */
2685:
2686: register int regno = REGNO (x);
2687: register int offset = regno / REGSET_ELT_BITS;
2688: register REGSET_ELT_TYPE bit
2689: = (REGSET_ELT_TYPE) 1 << (regno % REGSET_ELT_BITS);
2690: REGSET_ELT_TYPE all_needed = (old_live_regs[offset] & bit);
2691: REGSET_ELT_TYPE some_needed = (old_live_regs[offset] & bit);
2692:
2693: if (set_p)
2694: return;
2695:
2696: if (regno < FIRST_PSEUDO_REGISTER)
2697: {
2698: int n;
2699:
2700: n = HARD_REGNO_NREGS (regno, GET_MODE (x));
2701: while (--n > 0)
2702: {
2703: some_needed |= (old_live_regs[(regno + n) / REGSET_ELT_BITS]
2704: & ((REGSET_ELT_TYPE) 1
2705: << ((regno + n) % REGSET_ELT_BITS)));
2706: all_needed &= (old_live_regs[(regno + n) / REGSET_ELT_BITS]
2707: & ((REGSET_ELT_TYPE) 1
2708: << ((regno + n) % REGSET_ELT_BITS)));
2709: }
2710: }
2711:
2712: /* If it wasn't live before we started, then add a REG_DEAD note.
2713: We must check the previous lifetime info not the current info,
2714: because we may have to execute this code several times, e.g.
2715: once for a clobber (which doesn't add a note) and later
2716: for a use (which does add a note).
2717:
2718: Always make the register live. We must do this even if it was
2719: live before, because this may be an insn which sets and uses
2720: the same register, in which case the register has already been
2721: killed, so we must make it live again.
2722:
2723: Global registers are always live, and should never have a REG_DEAD
2724: note added for them, so none of the code below applies to them. */
2725:
2726: if (regno >= FIRST_PSEUDO_REGISTER || ! global_regs[regno])
2727: {
2728: /* Never add REG_DEAD notes for the FRAME_POINTER_REGNUM or the
2729: STACK_POINTER_REGNUM, since these are always considered to be
2730: live. Similarly for ARG_POINTER_REGNUM if it is fixed. */
2731: if (regno != FRAME_POINTER_REGNUM
2732: #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
2733: && ! (regno == HARD_FRAME_POINTER_REGNUM)
2734: #endif
2735: #if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
2736: && ! (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
2737: #endif
2738: && regno != STACK_POINTER_REGNUM)
2739: {
2740: if (! all_needed && ! dead_or_set_p (insn, x))
2741: {
2742: /* If none of the words in X is needed, make a REG_DEAD
2743: note. Otherwise, we must make partial REG_DEAD
2744: notes. */
2745: if (! some_needed)
2746: create_reg_dead_note (x, insn);
2747: else
2748: {
2749: int i;
2750:
2751: /* Don't make a REG_DEAD note for a part of a
2752: register that is set in the insn. */
2753: for (i = HARD_REGNO_NREGS (regno, GET_MODE (x)) - 1;
2754: i >= 0; i--)
2755: if ((old_live_regs[(regno + i) / REGSET_ELT_BITS]
2756: & ((REGSET_ELT_TYPE) 1
2757: << ((regno +i) % REGSET_ELT_BITS))) == 0
2758: && ! dead_or_set_regno_p (insn, regno + i))
2759: create_reg_dead_note (gen_rtx (REG, word_mode,
2760: regno + i),
2761: insn);
2762: }
2763: }
2764: }
2765:
2766: if (regno < FIRST_PSEUDO_REGISTER)
2767: {
2768: int j = HARD_REGNO_NREGS (regno, GET_MODE (x));
2769: while (--j >= 0)
2770: {
2771: offset = (regno + j) / REGSET_ELT_BITS;
2772: bit
2773: = (REGSET_ELT_TYPE) 1 << ((regno + j) % REGSET_ELT_BITS);
2774:
2775: bb_dead_regs[offset] &= ~bit;
2776: bb_live_regs[offset] |= bit;
2777: }
2778: }
2779: else
2780: {
2781: bb_dead_regs[offset] &= ~bit;
2782: bb_live_regs[offset] |= bit;
2783: }
2784: }
2785: return;
2786: }
2787:
2788: case MEM:
2789: /* Handle tail-recursive case. */
2790: attach_deaths (XEXP (x, 0), insn, 0);
2791: return;
2792:
2793: case SUBREG:
2794: case STRICT_LOW_PART:
2795: /* These two cases preserve the value of SET_P, so handle them
2796: separately. */
2797: attach_deaths (XEXP (x, 0), insn, set_p);
2798: return;
2799:
2800: case ZERO_EXTRACT:
2801: case SIGN_EXTRACT:
2802: /* This case preserves the value of SET_P for the first operand, but
2803: clears it for the other two. */
2804: attach_deaths (XEXP (x, 0), insn, set_p);
2805: attach_deaths (XEXP (x, 1), insn, 0);
2806: attach_deaths (XEXP (x, 2), insn, 0);
2807: return;
2808:
2809: default:
2810: /* Other cases: walk the insn. */
2811: fmt = GET_RTX_FORMAT (code);
2812: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2813: {
2814: if (fmt[i] == 'e')
2815: attach_deaths (XEXP (x, i), insn, 0);
2816: else if (fmt[i] == 'E')
2817: for (j = 0; j < XVECLEN (x, i); j++)
2818: attach_deaths (XVECEXP (x, i, j), insn, 0);
2819: }
2820: }
2821: }
2822:
2823: /* After INSN has executed, add register death notes for each register
2824: that is dead after INSN. */
2825:
2826: static void
2827: attach_deaths_insn (insn)
2828: rtx insn;
2829: {
2830: rtx x = PATTERN (insn);
2831: register RTX_CODE code = GET_CODE (x);
2832:
2833: if (code == SET)
2834: {
2835: attach_deaths (SET_SRC (x), insn, 0);
2836:
2837: /* A register might die here even if it is the destination, e.g.
2838: it is the target of a volatile read and is otherwise unused.
2839: Hence we must always call attach_deaths for the SET_DEST. */
2840: attach_deaths (SET_DEST (x), insn, 1);
2841: }
2842: else if (code == PARALLEL)
2843: {
2844: register int i;
2845: for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
2846: {
2847: code = GET_CODE (XVECEXP (x, 0, i));
2848: if (code == SET)
2849: {
2850: attach_deaths (SET_SRC (XVECEXP (x, 0, i)), insn, 0);
2851:
2852: attach_deaths (SET_DEST (XVECEXP (x, 0, i)), insn, 1);
2853: }
2854: /* Flow does not add REG_DEAD notes to registers that die in
2855: clobbers, so we can't either. */
2856: else if (code != CLOBBER)
2857: attach_deaths (XVECEXP (x, 0, i), insn, 0);
2858: }
2859: }
2860: /* Flow does not add REG_DEAD notes to registers that die in
2861: clobbers, so we can't either. */
2862: else if (code != CLOBBER)
2863: attach_deaths (x, insn, 0);
2864: }
2865:
2866: /* Delete notes beginning with INSN and maybe put them in the chain
2867: of notes ended by NOTE_LIST.
2868: Returns the insn following the notes. */
2869:
2870: static rtx
2871: unlink_notes (insn, tail)
2872: rtx insn, tail;
2873: {
2874: rtx prev = PREV_INSN (insn);
2875:
2876: while (insn != tail && GET_CODE (insn) == NOTE)
2877: {
2878: rtx next = NEXT_INSN (insn);
2879: /* Delete the note from its current position. */
2880: if (prev)
2881: NEXT_INSN (prev) = next;
2882: if (next)
2883: PREV_INSN (next) = prev;
2884:
2885: if (write_symbols != NO_DEBUG && NOTE_LINE_NUMBER (insn) > 0)
2886: /* Record line-number notes so they can be reused. */
2887: LINE_NOTE (insn) = insn;
2888: else
2889: {
2890: /* Insert the note at the end of the notes list. */
2891: PREV_INSN (insn) = note_list;
2892: if (note_list)
2893: NEXT_INSN (note_list) = insn;
2894: note_list = insn;
2895: }
2896:
2897: insn = next;
2898: }
2899: return insn;
2900: }
2901:
2902: /* Constructor for `sometimes' data structure. */
2903:
2904: static int
2905: new_sometimes_live (regs_sometimes_live, offset, bit, sometimes_max)
2906: struct sometimes *regs_sometimes_live;
2907: int offset, bit;
2908: int sometimes_max;
2909: {
2910: register struct sometimes *p;
2911: register int regno = offset * REGSET_ELT_BITS + bit;
2912: int i;
2913:
2914: /* There should never be a register greater than max_regno here. If there
2915: is, it means that a define_split has created a new pseudo reg. This
2916: is not allowed, since there will not be flow info available for any
2917: new register, so catch the error here. */
2918: if (regno >= max_regno)
2919: abort ();
2920:
2921: p = ®s_sometimes_live[sometimes_max];
2922: p->offset = offset;
2923: p->bit = bit;
2924: p->live_length = 0;
2925: p->calls_crossed = 0;
2926: sometimes_max++;
2927: return sometimes_max;
2928: }
2929:
2930: /* Count lengths of all regs we are currently tracking,
2931: and find new registers no longer live. */
2932:
2933: static void
2934: finish_sometimes_live (regs_sometimes_live, sometimes_max)
2935: struct sometimes *regs_sometimes_live;
2936: int sometimes_max;
2937: {
2938: int i;
2939:
2940: for (i = 0; i < sometimes_max; i++)
2941: {
2942: register struct sometimes *p = ®s_sometimes_live[i];
2943: int regno;
2944:
2945: regno = p->offset * REGSET_ELT_BITS + p->bit;
2946:
2947: sched_reg_live_length[regno] += p->live_length;
2948: sched_reg_n_calls_crossed[regno] += p->calls_crossed;
2949: }
2950: }
2951:
2952: /* Use modified list scheduling to rearrange insns in basic block
2953: B. FILE, if nonzero, is where we dump interesting output about
2954: this pass. */
2955:
2956: static void
2957: schedule_block (b, file)
2958: int b;
2959: FILE *file;
2960: {
2961: rtx insn, last;
2962: rtx last_note = 0;
2963: rtx *ready, link;
2964: int i, j, n_ready = 0, new_ready, n_insns = 0;
2965: int sched_n_insns = 0;
2966: int clock;
2967: #define NEED_NOTHING 0
2968: #define NEED_HEAD 1
2969: #define NEED_TAIL 2
2970: int new_needs;
2971:
2972: /* HEAD and TAIL delimit the region being scheduled. */
2973: rtx head = basic_block_head[b];
2974: rtx tail = basic_block_end[b];
2975: /* PREV_HEAD and NEXT_TAIL are the boundaries of the insns
2976: being scheduled. When the insns have been ordered,
2977: these insns delimit where the new insns are to be
2978: spliced back into the insn chain. */
2979: rtx next_tail;
2980: rtx prev_head;
2981:
2982: /* Keep life information accurate. */
2983: register struct sometimes *regs_sometimes_live;
2984: int sometimes_max;
2985:
2986: if (file)
2987: fprintf (file, ";;\t -- basic block number %d from %d to %d --\n",
2988: b, INSN_UID (basic_block_head[b]), INSN_UID (basic_block_end[b]));
2989:
2990: i = max_reg_num ();
2991: reg_last_uses = (rtx *) alloca (i * sizeof (rtx));
2992: bzero (reg_last_uses, i * sizeof (rtx));
2993: reg_last_sets = (rtx *) alloca (i * sizeof (rtx));
2994: bzero (reg_last_sets, i * sizeof (rtx));
2995: clear_units ();
2996:
2997: /* Remove certain insns at the beginning from scheduling,
2998: by advancing HEAD. */
2999:
3000: /* At the start of a function, before reload has run, don't delay getting
3001: parameters from hard registers into pseudo registers. */
3002: if (reload_completed == 0 && b == 0)
3003: {
3004: while (head != tail
3005: && GET_CODE (head) == NOTE
3006: && NOTE_LINE_NUMBER (head) != NOTE_INSN_FUNCTION_BEG)
3007: head = NEXT_INSN (head);
3008: while (head != tail
3009: && GET_CODE (head) == INSN
3010: && GET_CODE (PATTERN (head)) == SET)
3011: {
3012: rtx src = SET_SRC (PATTERN (head));
3013: while (GET_CODE (src) == SUBREG
3014: || GET_CODE (src) == SIGN_EXTEND
3015: || GET_CODE (src) == ZERO_EXTEND
3016: || GET_CODE (src) == SIGN_EXTRACT
3017: || GET_CODE (src) == ZERO_EXTRACT)
3018: src = XEXP (src, 0);
3019: if (GET_CODE (src) != REG
3020: || REGNO (src) >= FIRST_PSEUDO_REGISTER)
3021: break;
3022: /* Keep this insn from ever being scheduled. */
3023: INSN_REF_COUNT (head) = 1;
3024: head = NEXT_INSN (head);
3025: }
3026: }
3027:
3028: /* Don't include any notes or labels at the beginning of the
3029: basic block, or notes at the ends of basic blocks. */
3030: while (head != tail)
3031: {
3032: if (GET_CODE (head) == NOTE)
3033: head = NEXT_INSN (head);
3034: else if (GET_CODE (tail) == NOTE)
3035: tail = PREV_INSN (tail);
3036: else if (GET_CODE (head) == CODE_LABEL)
3037: head = NEXT_INSN (head);
3038: else break;
3039: }
3040: /* If the only insn left is a NOTE or a CODE_LABEL, then there is no need
3041: to schedule this block. */
3042: if (head == tail
3043: && (GET_CODE (head) == NOTE || GET_CODE (head) == CODE_LABEL))
3044: return;
3045:
3046: #if 0
3047: /* This short-cut doesn't work. It does not count call insns crossed by
3048: registers in reg_sometimes_live. It does not mark these registers as
3049: dead if they die in this block. It does not mark these registers live
3050: (or create new reg_sometimes_live entries if necessary) if they are born
3051: in this block.
3052:
3053: The easy solution is to just always schedule a block. This block only
3054: has one insn, so this won't slow down this pass by much. */
3055:
3056: if (head == tail)
3057: return;
3058: #endif
3059:
3060: /* Now HEAD through TAIL are the insns actually to be rearranged;
3061: Let PREV_HEAD and NEXT_TAIL enclose them. */
3062: prev_head = PREV_INSN (head);
3063: next_tail = NEXT_INSN (tail);
3064:
3065: /* Initialize basic block data structures. */
3066: dead_notes = 0;
3067: pending_read_insns = 0;
3068: pending_read_mems = 0;
3069: pending_write_insns = 0;
3070: pending_write_mems = 0;
3071: pending_lists_length = 0;
3072: last_pending_memory_flush = 0;
3073: last_function_call = 0;
3074: last_scheduled_insn = 0;
3075:
3076: LOG_LINKS (sched_before_next_call) = 0;
3077:
3078: n_insns += sched_analyze (head, tail);
3079: if (n_insns == 0)
3080: {
3081: free_pending_lists ();
3082: return;
3083: }
3084:
3085: /* Allocate vector to hold insns to be rearranged (except those
3086: insns which are controlled by an insn with SCHED_GROUP_P set).
3087: All these insns are included between ORIG_HEAD and ORIG_TAIL,
3088: as those variables ultimately are set up. */
3089: ready = (rtx *) alloca ((n_insns+1) * sizeof (rtx));
3090:
3091: /* TAIL is now the last of the insns to be rearranged.
3092: Put those insns into the READY vector. */
3093: insn = tail;
3094:
3095: /* For all branches, calls, uses, and cc0 setters, force them to remain
3096: in order at the end of the block by adding dependencies and giving
3097: the last a high priority. There may be notes present, and prev_head
3098: may also be a note.
3099:
3100: Branches must obviously remain at the end. Calls should remain at the
3101: end since moving them results in worse register allocation. Uses remain
3102: at the end to ensure proper register allocation. cc0 setters remaim
3103: at the end because they can't be moved away from their cc0 user. */
3104: last = 0;
3105: while (GET_CODE (insn) == CALL_INSN || GET_CODE (insn) == JUMP_INSN
3106: || (GET_CODE (insn) == INSN
3107: && (GET_CODE (PATTERN (insn)) == USE
3108: #ifdef HAVE_cc0
3109: || sets_cc0_p (PATTERN (insn))
3110: #endif
3111: ))
3112: || GET_CODE (insn) == NOTE)
3113: {
3114: if (GET_CODE (insn) != NOTE)
3115: {
3116: priority (insn);
3117: if (last == 0)
3118: {
3119: ready[n_ready++] = insn;
3120: INSN_PRIORITY (insn) = TAIL_PRIORITY - i;
3121: INSN_REF_COUNT (insn) = 0;
3122: }
3123: else if (! find_insn_list (insn, LOG_LINKS (last)))
3124: {
3125: add_dependence (last, insn, REG_DEP_ANTI);
3126: INSN_REF_COUNT (insn)++;
3127: }
3128: last = insn;
3129:
3130: /* Skip over insns that are part of a group. */
3131: while (SCHED_GROUP_P (insn))
3132: {
3133: insn = prev_nonnote_insn (insn);
3134: priority (insn);
3135: }
3136: }
3137:
3138: insn = PREV_INSN (insn);
3139: /* Don't overrun the bounds of the basic block. */
3140: if (insn == prev_head)
3141: break;
3142: }
3143:
3144: /* Assign priorities to instructions. Also check whether they
3145: are in priority order already. If so then I will be nonnegative.
3146: We use this shortcut only before reloading. */
3147: #if 0
3148: i = reload_completed ? DONE_PRIORITY : MAX_PRIORITY;
3149: #endif
3150:
3151: for (; insn != prev_head; insn = PREV_INSN (insn))
3152: {
3153: if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
3154: {
3155: priority (insn);
3156: if (INSN_REF_COUNT (insn) == 0)
3157: {
3158: if (last == 0)
3159: ready[n_ready++] = insn;
3160: else
3161: {
3162: /* Make this dependent on the last of the instructions
3163: that must remain in order at the end of the block. */
3164: add_dependence (last, insn, REG_DEP_ANTI);
3165: INSN_REF_COUNT (insn) = 1;
3166: }
3167: }
3168: if (SCHED_GROUP_P (insn))
3169: {
3170: while (SCHED_GROUP_P (insn))
3171: {
3172: insn = PREV_INSN (insn);
3173: while (GET_CODE (insn) == NOTE)
3174: insn = PREV_INSN (insn);
3175: priority (insn);
3176: }
3177: continue;
3178: }
3179: #if 0
3180: if (i < 0)
3181: continue;
3182: if (INSN_PRIORITY (insn) < i)
3183: i = INSN_PRIORITY (insn);
3184: else if (INSN_PRIORITY (insn) > i)
3185: i = DONE_PRIORITY;
3186: #endif
3187: }
3188: }
3189:
3190: #if 0
3191: /* This short-cut doesn't work. It does not count call insns crossed by
3192: registers in reg_sometimes_live. It does not mark these registers as
3193: dead if they die in this block. It does not mark these registers live
3194: (or create new reg_sometimes_live entries if necessary) if they are born
3195: in this block.
3196:
3197: The easy solution is to just always schedule a block. These blocks tend
3198: to be very short, so this doesn't slow down this pass by much. */
3199:
3200: /* If existing order is good, don't bother to reorder. */
3201: if (i != DONE_PRIORITY)
3202: {
3203: if (file)
3204: fprintf (file, ";; already scheduled\n");
3205:
3206: if (reload_completed == 0)
3207: {
3208: for (i = 0; i < sometimes_max; i++)
3209: regs_sometimes_live[i].live_length += n_insns;
3210:
3211: finish_sometimes_live (regs_sometimes_live, sometimes_max);
3212: }
3213: free_pending_lists ();
3214: return;
3215: }
3216: #endif
3217:
3218: /* Scan all the insns to be scheduled, removing NOTE insns
3219: and register death notes.
3220: Line number NOTE insns end up in NOTE_LIST.
3221: Register death notes end up in DEAD_NOTES.
3222:
3223: Recreate the register life information for the end of this basic
3224: block. */
3225:
3226: if (reload_completed == 0)
3227: {
3228: bcopy (basic_block_live_at_start[b], bb_live_regs, regset_bytes);
3229: bzero (bb_dead_regs, regset_bytes);
3230:
3231: if (b == 0)
3232: {
3233: /* This is the first block in the function. There may be insns
3234: before head that we can't schedule. We still need to examine
3235: them though for accurate register lifetime analysis. */
3236:
3237: /* We don't want to remove any REG_DEAD notes as the code below
3238: does. */
3239:
3240: for (insn = basic_block_head[b]; insn != head;
3241: insn = NEXT_INSN (insn))
3242: if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
3243: {
3244: /* See if the register gets born here. */
3245: /* We must check for registers being born before we check for
3246: registers dying. It is possible for a register to be born
3247: and die in the same insn, e.g. reading from a volatile
3248: memory location into an otherwise unused register. Such
3249: a register must be marked as dead after this insn. */
3250: if (GET_CODE (PATTERN (insn)) == SET
3251: || GET_CODE (PATTERN (insn)) == CLOBBER)
3252: sched_note_set (b, PATTERN (insn), 0);
3253: else if (GET_CODE (PATTERN (insn)) == PARALLEL)
3254: {
3255: int j;
3256: for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
3257: if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
3258: || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
3259: sched_note_set (b, XVECEXP (PATTERN (insn), 0, j), 0);
3260:
3261: /* ??? This code is obsolete and should be deleted. It
3262: is harmless though, so we will leave it in for now. */
3263: for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
3264: if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == USE)
3265: sched_note_set (b, XVECEXP (PATTERN (insn), 0, j), 0);
3266: }
3267:
3268: for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
3269: {
3270: if ((REG_NOTE_KIND (link) == REG_DEAD
3271: || REG_NOTE_KIND (link) == REG_UNUSED)
3272: /* Verify that the REG_NOTE has a legal value. */
3273: && GET_CODE (XEXP (link, 0)) == REG)
3274: {
3275: register int regno = REGNO (XEXP (link, 0));
3276: register int offset = regno / REGSET_ELT_BITS;
3277: register REGSET_ELT_TYPE bit
3278: = (REGSET_ELT_TYPE) 1 << (regno % REGSET_ELT_BITS);
3279:
3280: if (regno < FIRST_PSEUDO_REGISTER)
3281: {
3282: int j = HARD_REGNO_NREGS (regno,
3283: GET_MODE (XEXP (link, 0)));
3284: while (--j >= 0)
3285: {
3286: offset = (regno + j) / REGSET_ELT_BITS;
3287: bit = ((REGSET_ELT_TYPE) 1
3288: << ((regno + j) % REGSET_ELT_BITS));
3289:
3290: bb_live_regs[offset] &= ~bit;
3291: bb_dead_regs[offset] |= bit;
3292: }
3293: }
3294: else
3295: {
3296: bb_live_regs[offset] &= ~bit;
3297: bb_dead_regs[offset] |= bit;
3298: }
3299: }
3300: }
3301: }
3302: }
3303: }
3304:
3305: /* If debugging information is being produced, keep track of the line
3306: number notes for each insn. */
3307: if (write_symbols != NO_DEBUG)
3308: {
3309: /* We must use the true line number for the first insn in the block
3310: that was computed and saved at the start of this pass. We can't
3311: use the current line number, because scheduling of the previous
3312: block may have changed the current line number. */
3313: rtx line = line_note_head[b];
3314:
3315: for (insn = basic_block_head[b];
3316: insn != next_tail;
3317: insn = NEXT_INSN (insn))
3318: if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
3319: line = insn;
3320: else
3321: LINE_NOTE (insn) = line;
3322: }
3323:
3324: for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
3325: {
3326: rtx prev, next, link;
3327:
3328: /* Farm out notes. This is needed to keep the debugger from
3329: getting completely deranged. */
3330: if (GET_CODE (insn) == NOTE)
3331: {
3332: prev = insn;
3333: insn = unlink_notes (insn, next_tail);
3334: if (prev == tail)
3335: abort ();
3336: if (prev == head)
3337: abort ();
3338: if (insn == next_tail)
3339: abort ();
3340: }
3341:
3342: if (reload_completed == 0
3343: && GET_RTX_CLASS (GET_CODE (insn)) == 'i')
3344: {
3345: /* See if the register gets born here. */
3346: /* We must check for registers being born before we check for
3347: registers dying. It is possible for a register to be born and
3348: die in the same insn, e.g. reading from a volatile memory
3349: location into an otherwise unused register. Such a register
3350: must be marked as dead after this insn. */
3351: if (GET_CODE (PATTERN (insn)) == SET
3352: || GET_CODE (PATTERN (insn)) == CLOBBER)
3353: sched_note_set (b, PATTERN (insn), 0);
3354: else if (GET_CODE (PATTERN (insn)) == PARALLEL)
3355: {
3356: int j;
3357: for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
3358: if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
3359: || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
3360: sched_note_set (b, XVECEXP (PATTERN (insn), 0, j), 0);
3361:
3362: /* ??? This code is obsolete and should be deleted. It
3363: is harmless though, so we will leave it in for now. */
3364: for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
3365: if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == USE)
3366: sched_note_set (b, XVECEXP (PATTERN (insn), 0, j), 0);
3367: }
3368:
3369: /* Need to know what registers this insn kills. */
3370: for (prev = 0, link = REG_NOTES (insn); link; link = next)
3371: {
3372: int regno;
3373:
3374: next = XEXP (link, 1);
3375: if ((REG_NOTE_KIND (link) == REG_DEAD
3376: || REG_NOTE_KIND (link) == REG_UNUSED)
3377: /* Verify that the REG_NOTE has a legal value. */
3378: && GET_CODE (XEXP (link, 0)) == REG)
3379: {
3380: register int regno = REGNO (XEXP (link, 0));
3381: register int offset = regno / REGSET_ELT_BITS;
3382: register REGSET_ELT_TYPE bit
3383: = (REGSET_ELT_TYPE) 1 << (regno % REGSET_ELT_BITS);
3384:
3385: /* Only unlink REG_DEAD notes; leave REG_UNUSED notes
3386: alone. */
3387: if (REG_NOTE_KIND (link) == REG_DEAD)
3388: {
3389: if (prev)
3390: XEXP (prev, 1) = next;
3391: else
3392: REG_NOTES (insn) = next;
3393: XEXP (link, 1) = dead_notes;
3394: dead_notes = link;
3395: }
3396: else
3397: prev = link;
3398:
3399: if (regno < FIRST_PSEUDO_REGISTER)
3400: {
3401: int j = HARD_REGNO_NREGS (regno,
3402: GET_MODE (XEXP (link, 0)));
3403: while (--j >= 0)
3404: {
3405: offset = (regno + j) / REGSET_ELT_BITS;
3406: bit = ((REGSET_ELT_TYPE) 1
3407: << ((regno + j) % REGSET_ELT_BITS));
3408:
3409: bb_live_regs[offset] &= ~bit;
3410: bb_dead_regs[offset] |= bit;
3411: }
3412: }
3413: else
3414: {
3415: bb_live_regs[offset] &= ~bit;
3416: bb_dead_regs[offset] |= bit;
3417: }
3418: }
3419: else
3420: prev = link;
3421: }
3422: }
3423: }
3424:
3425: if (reload_completed == 0)
3426: {
3427: /* Keep track of register lives. */
3428: old_live_regs = (regset) alloca (regset_bytes);
3429: regs_sometimes_live
3430: = (struct sometimes *) alloca (max_regno * sizeof (struct sometimes));
3431: sometimes_max = 0;
3432:
3433: /* Start with registers live at end. */
3434: for (j = 0; j < regset_size; j++)
3435: {
3436: REGSET_ELT_TYPE live = bb_live_regs[j];
3437: old_live_regs[j] = live;
3438: if (live)
3439: {
3440: register int bit;
3441: for (bit = 0; bit < REGSET_ELT_BITS; bit++)
3442: if (live & ((REGSET_ELT_TYPE) 1 << bit))
3443: sometimes_max = new_sometimes_live (regs_sometimes_live, j,
3444: bit, sometimes_max);
3445: }
3446: }
3447: }
3448:
3449: SCHED_SORT (ready, n_ready, 1);
3450:
3451: if (file)
3452: {
3453: fprintf (file, ";; ready list initially:\n;; ");
3454: for (i = 0; i < n_ready; i++)
3455: fprintf (file, "%d ", INSN_UID (ready[i]));
3456: fprintf (file, "\n\n");
3457:
3458: for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
3459: if (INSN_PRIORITY (insn) > 0)
3460: fprintf (file, ";; insn[%4d]: priority = %4d, ref_count = %4d\n",
3461: INSN_UID (insn), INSN_PRIORITY (insn),
3462: INSN_REF_COUNT (insn));
3463: }
3464:
3465: /* Now HEAD and TAIL are going to become disconnected
3466: entirely from the insn chain. */
3467: tail = 0;
3468:
3469: /* Q_SIZE will always be zero here. */
3470: q_ptr = 0; clock = 0;
3471: bzero (insn_queue, sizeof (insn_queue));
3472:
3473: /* Now, perform list scheduling. */
3474:
3475: /* Where we start inserting insns is after TAIL. */
3476: last = next_tail;
3477:
3478: new_needs = (NEXT_INSN (prev_head) == basic_block_head[b]
3479: ? NEED_HEAD : NEED_NOTHING);
3480: if (PREV_INSN (next_tail) == basic_block_end[b])
3481: new_needs |= NEED_TAIL;
3482:
3483: new_ready = n_ready;
3484: while (sched_n_insns < n_insns)
3485: {
3486: q_ptr = NEXT_Q (q_ptr); clock++;
3487:
3488: /* Add all pending insns that can be scheduled without stalls to the
3489: ready list. */
3490: for (insn = insn_queue[q_ptr]; insn; insn = NEXT_INSN (insn))
3491: {
3492: if (file)
3493: fprintf (file, ";; launching %d before %d with no stalls at T-%d\n",
3494: INSN_UID (insn), INSN_UID (last), clock);
3495: ready[new_ready++] = insn;
3496: q_size -= 1;
3497: }
3498: insn_queue[q_ptr] = 0;
3499:
3500: /* If there are no ready insns, stall until one is ready and add all
3501: of the pending insns at that point to the ready list. */
3502: if (new_ready == 0)
3503: {
3504: register int stalls;
3505:
3506: for (stalls = 1; stalls < INSN_QUEUE_SIZE; stalls++)
3507: if (insn = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)])
3508: {
3509: for (; insn; insn = NEXT_INSN (insn))
3510: {
3511: if (file)
3512: fprintf (file, ";; launching %d before %d with %d stalls at T-%d\n",
3513: INSN_UID (insn), INSN_UID (last), stalls, clock);
3514: ready[new_ready++] = insn;
3515: q_size -= 1;
3516: }
3517: insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = 0;
3518: break;
3519: }
3520:
3521: q_ptr = NEXT_Q_AFTER (q_ptr, stalls); clock += stalls;
3522: }
3523:
3524: /* There should be some instructions waiting to fire. */
3525: if (new_ready == 0)
3526: abort ();
3527:
3528: if (file)
3529: {
3530: fprintf (file, ";; ready list at T-%d:", clock);
3531: for (i = 0; i < new_ready; i++)
3532: fprintf (file, " %d (%x)",
3533: INSN_UID (ready[i]), INSN_PRIORITY (ready[i]));
3534: }
3535:
3536: /* Sort the ready list and choose the best insn to schedule. Select
3537: which insn should issue in this cycle and queue those that are
3538: blocked by function unit hazards.
3539:
3540: N_READY holds the number of items that were scheduled the last time,
3541: minus the one instruction scheduled on the last loop iteration; it
3542: is not modified for any other reason in this loop. */
3543:
3544: SCHED_SORT (ready, new_ready, n_ready);
3545: if (MAX_BLOCKAGE > 1)
3546: {
3547: new_ready = schedule_select (ready, new_ready, clock, file);
3548: if (new_ready == 0)
3549: {
3550: if (file)
3551: fprintf (file, "\n");
3552: /* We must set n_ready here, to ensure that sorting always
3553: occurs when we come back to the SCHED_SORT line above. */
3554: n_ready = 0;
3555: continue;
3556: }
3557: }
3558: n_ready = new_ready;
3559: last_scheduled_insn = insn = ready[0];
3560:
3561: /* The first insn scheduled becomes the new tail. */
3562: if (tail == 0)
3563: tail = insn;
3564:
3565: if (file)
3566: {
3567: fprintf (file, ", now");
3568: for (i = 0; i < n_ready; i++)
3569: fprintf (file, " %d", INSN_UID (ready[i]));
3570: fprintf (file, "\n");
3571: }
3572:
3573: if (DONE_PRIORITY_P (insn))
3574: abort ();
3575:
3576: if (reload_completed == 0)
3577: {
3578: /* Process this insn, and each insn linked to this one which must
3579: be immediately output after this insn. */
3580: do
3581: {
3582: /* First we kill registers set by this insn, and then we
3583: make registers used by this insn live. This is the opposite
3584: order used above because we are traversing the instructions
3585: backwards. */
3586:
3587: /* Strictly speaking, we should scan REG_UNUSED notes and make
3588: every register mentioned there live, however, we will just
3589: kill them again immediately below, so there doesn't seem to
3590: be any reason why we bother to do this. */
3591:
3592: /* See if this is the last notice we must take of a register. */
3593: if (GET_CODE (PATTERN (insn)) == SET
3594: || GET_CODE (PATTERN (insn)) == CLOBBER)
3595: sched_note_set (b, PATTERN (insn), 1);
3596: else if (GET_CODE (PATTERN (insn)) == PARALLEL)
3597: {
3598: int j;
3599: for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
3600: if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
3601: || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
3602: sched_note_set (b, XVECEXP (PATTERN (insn), 0, j), 1);
3603: }
3604:
3605: /* This code keeps life analysis information up to date. */
3606: if (GET_CODE (insn) == CALL_INSN)
3607: {
3608: register struct sometimes *p;
3609:
3610: /* A call kills all call used and global registers, except
3611: for those mentioned in the call pattern which will be
3612: made live again later. */
3613: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3614: if (call_used_regs[i] || global_regs[i])
3615: {
3616: register int offset = i / REGSET_ELT_BITS;
3617: register REGSET_ELT_TYPE bit
3618: = (REGSET_ELT_TYPE) 1 << (i % REGSET_ELT_BITS);
3619:
3620: bb_live_regs[offset] &= ~bit;
3621: bb_dead_regs[offset] |= bit;
3622: }
3623:
3624: /* Regs live at the time of a call instruction must not
3625: go in a register clobbered by calls. Record this for
3626: all regs now live. Note that insns which are born or
3627: die in a call do not cross a call, so this must be done
3628: after the killings (above) and before the births
3629: (below). */
3630: p = regs_sometimes_live;
3631: for (i = 0; i < sometimes_max; i++, p++)
3632: if (bb_live_regs[p->offset]
3633: & ((REGSET_ELT_TYPE) 1 << p->bit))
3634: p->calls_crossed += 1;
3635: }
3636:
3637: /* Make every register used live, and add REG_DEAD notes for
3638: registers which were not live before we started. */
3639: attach_deaths_insn (insn);
3640:
3641: /* Find registers now made live by that instruction. */
3642: for (i = 0; i < regset_size; i++)
3643: {
3644: REGSET_ELT_TYPE diff = bb_live_regs[i] & ~old_live_regs[i];
3645: if (diff)
3646: {
3647: register int bit;
3648: old_live_regs[i] |= diff;
3649: for (bit = 0; bit < REGSET_ELT_BITS; bit++)
3650: if (diff & ((REGSET_ELT_TYPE) 1 << bit))
3651: sometimes_max
3652: = new_sometimes_live (regs_sometimes_live, i, bit,
3653: sometimes_max);
3654: }
3655: }
3656:
3657: /* Count lengths of all regs we are worrying about now,
3658: and handle registers no longer live. */
3659:
3660: for (i = 0; i < sometimes_max; i++)
3661: {
3662: register struct sometimes *p = ®s_sometimes_live[i];
3663: int regno = p->offset*REGSET_ELT_BITS + p->bit;
3664:
3665: p->live_length += 1;
3666:
3667: if ((bb_live_regs[p->offset]
3668: & ((REGSET_ELT_TYPE) 1 << p->bit)) == 0)
3669: {
3670: /* This is the end of one of this register's lifetime
3671: segments. Save the lifetime info collected so far,
3672: and clear its bit in the old_live_regs entry. */
3673: sched_reg_live_length[regno] += p->live_length;
3674: sched_reg_n_calls_crossed[regno] += p->calls_crossed;
3675: old_live_regs[p->offset]
3676: &= ~((REGSET_ELT_TYPE) 1 << p->bit);
3677:
3678: /* Delete the reg_sometimes_live entry for this reg by
3679: copying the last entry over top of it. */
3680: *p = regs_sometimes_live[--sometimes_max];
3681: /* ...and decrement i so that this newly copied entry
3682: will be processed. */
3683: i--;
3684: }
3685: }
3686:
3687: link = insn;
3688: insn = PREV_INSN (insn);
3689: }
3690: while (SCHED_GROUP_P (link));
3691:
3692: /* Set INSN back to the insn we are scheduling now. */
3693: insn = ready[0];
3694: }
3695:
3696: /* Schedule INSN. Remove it from the ready list. */
3697: ready += 1;
3698: n_ready -= 1;
3699:
3700: sched_n_insns += 1;
3701: NEXT_INSN (insn) = last;
3702: PREV_INSN (last) = insn;
3703: last = insn;
3704:
3705: /* Everything that precedes INSN now either becomes "ready", if
3706: it can execute immediately before INSN, or "pending", if
3707: there must be a delay. Give INSN high enough priority that
3708: at least one (maybe more) reg-killing insns can be launched
3709: ahead of all others. Mark INSN as scheduled by changing its
3710: priority to -1. */
3711: INSN_PRIORITY (insn) = LAUNCH_PRIORITY;
3712: new_ready = schedule_insn (insn, ready, n_ready, clock);
3713: INSN_PRIORITY (insn) = DONE_PRIORITY;
3714:
3715: /* Schedule all prior insns that must not be moved. */
3716: if (SCHED_GROUP_P (insn))
3717: {
3718: /* Disable these insns from being launched. */
3719: link = insn;
3720: while (SCHED_GROUP_P (link))
3721: {
3722: /* Disable these insns from being launched by anybody. */
3723: link = PREV_INSN (link);
3724: INSN_REF_COUNT (link) = 0;
3725: }
3726:
3727: /* None of these insns can move forward into delay slots. */
3728: while (SCHED_GROUP_P (insn))
3729: {
3730: insn = PREV_INSN (insn);
3731: new_ready = schedule_insn (insn, ready, new_ready, clock);
3732: INSN_PRIORITY (insn) = DONE_PRIORITY;
3733:
3734: sched_n_insns += 1;
3735: NEXT_INSN (insn) = last;
3736: PREV_INSN (last) = insn;
3737: last = insn;
3738: }
3739: }
3740: }
3741: if (q_size != 0)
3742: abort ();
3743:
3744: if (reload_completed == 0)
3745: finish_sometimes_live (regs_sometimes_live, sometimes_max);
3746:
3747: /* HEAD is now the first insn in the chain of insns that
3748: been scheduled by the loop above.
3749: TAIL is the last of those insns. */
3750: head = insn;
3751:
3752: /* NOTE_LIST is the end of a chain of notes previously found
3753: among the insns. Insert them at the beginning of the insns. */
3754: if (note_list != 0)
3755: {
3756: rtx note_head = note_list;
3757: while (PREV_INSN (note_head))
3758: note_head = PREV_INSN (note_head);
3759:
3760: PREV_INSN (head) = note_list;
3761: NEXT_INSN (note_list) = head;
3762: head = note_head;
3763: }
3764:
3765: /* There should be no REG_DEAD notes leftover at the end.
3766: In practice, this can occur as the result of bugs in flow, combine.c,
3767: and/or sched.c. The values of the REG_DEAD notes remaining are
3768: meaningless, because dead_notes is just used as a free list. */
3769: #if 1
3770: if (dead_notes != 0)
3771: abort ();
3772: #endif
3773:
3774: if (new_needs & NEED_HEAD)
3775: basic_block_head[b] = head;
3776: PREV_INSN (head) = prev_head;
3777: NEXT_INSN (prev_head) = head;
3778:
3779: if (new_needs & NEED_TAIL)
3780: basic_block_end[b] = tail;
3781: NEXT_INSN (tail) = next_tail;
3782: PREV_INSN (next_tail) = tail;
3783:
3784: /* Restore the line-number notes of each insn. */
3785: if (write_symbols != NO_DEBUG)
3786: {
3787: rtx line, note, prev, new;
3788: int notes = 0;
3789:
3790: head = basic_block_head[b];
3791: next_tail = NEXT_INSN (basic_block_end[b]);
3792:
3793: /* Determine the current line-number. We want to know the current
3794: line number of the first insn of the block here, in case it is
3795: different from the true line number that was saved earlier. If
3796: different, then we need a line number note before the first insn
3797: of this block. If it happens to be the same, then we don't want to
3798: emit another line number note here. */
3799: for (line = head; line; line = PREV_INSN (line))
3800: if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
3801: break;
3802:
3803: /* Walk the insns keeping track of the current line-number and inserting
3804: the line-number notes as needed. */
3805: for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
3806: if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
3807: line = insn;
3808: /* This used to emit line number notes before every non-deleted note.
3809: However, this confuses a debugger, because line notes not separated
3810: by real instructions all end up at the same address. I can find no
3811: use for line number notes before other notes, so none are emitted. */
3812: else if (GET_CODE (insn) != NOTE
3813: && (note = LINE_NOTE (insn)) != 0
3814: && note != line
3815: && (line == 0
3816: || NOTE_LINE_NUMBER (note) != NOTE_LINE_NUMBER (line)
3817: || NOTE_SOURCE_FILE (note) != NOTE_SOURCE_FILE (line)))
3818: {
3819: line = note;
3820: prev = PREV_INSN (insn);
3821: if (LINE_NOTE (note))
3822: {
3823: /* Re-use the original line-number note. */
3824: LINE_NOTE (note) = 0;
3825: PREV_INSN (note) = prev;
3826: NEXT_INSN (prev) = note;
3827: PREV_INSN (insn) = note;
3828: NEXT_INSN (note) = insn;
3829: }
3830: else
3831: {
3832: notes++;
3833: new = emit_note_after (NOTE_LINE_NUMBER (note), prev);
3834: NOTE_SOURCE_FILE (new) = NOTE_SOURCE_FILE (note);
3835: }
3836: }
3837: if (file && notes)
3838: fprintf (file, ";; added %d line-number notes\n", notes);
3839: }
3840:
3841: if (file)
3842: {
3843: fprintf (file, ";; total time = %d\n;; new basic block head = %d\n;; new basic block end = %d\n\n",
3844: clock, INSN_UID (basic_block_head[b]), INSN_UID (basic_block_end[b]));
3845: }
3846:
3847: /* Yow! We're done! */
3848: free_pending_lists ();
3849:
3850: return;
3851: }
3852:
3853: /* Subroutine of split_hard_reg_notes. Searches X for any reference to
3854: REGNO, returning the rtx of the reference found if any. Otherwise,
3855: returns 0. */
3856:
3857: static rtx
3858: regno_use_in (regno, x)
3859: int regno;
3860: rtx x;
3861: {
3862: register char *fmt;
3863: int i, j;
3864: rtx tem;
3865:
3866: if (GET_CODE (x) == REG && REGNO (x) == regno)
3867: return x;
3868:
3869: fmt = GET_RTX_FORMAT (GET_CODE (x));
3870: for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
3871: {
3872: if (fmt[i] == 'e')
3873: {
3874: if (tem = regno_use_in (regno, XEXP (x, i)))
3875: return tem;
3876: }
3877: else if (fmt[i] == 'E')
3878: for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3879: if (tem = regno_use_in (regno , XVECEXP (x, i, j)))
3880: return tem;
3881: }
3882:
3883: return 0;
3884: }
3885:
3886: /* Subroutine of update_flow_info. Determines whether any new REG_NOTEs are
3887: needed for the hard register mentioned in the note. This can happen
3888: if the reference to the hard register in the original insn was split into
3889: several smaller hard register references in the split insns. */
3890:
3891: static void
3892: split_hard_reg_notes (note, first, last, orig_insn)
3893: rtx note, first, last, orig_insn;
3894: {
3895: rtx reg, temp, link;
3896: int n_regs, i, new_reg;
3897: rtx insn;
3898:
3899: /* Assume that this is a REG_DEAD note. */
3900: if (REG_NOTE_KIND (note) != REG_DEAD)
3901: abort ();
3902:
3903: reg = XEXP (note, 0);
3904:
3905: n_regs = HARD_REGNO_NREGS (REGNO (reg), GET_MODE (reg));
3906:
3907: for (i = 0; i < n_regs; i++)
3908: {
3909: new_reg = REGNO (reg) + i;
3910:
3911: /* Check for references to new_reg in the split insns. */
3912: for (insn = last; ; insn = PREV_INSN (insn))
3913: {
3914: if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
3915: && (temp = regno_use_in (new_reg, PATTERN (insn))))
3916: {
3917: /* Create a new reg dead note here. */
3918: link = rtx_alloc (EXPR_LIST);
3919: PUT_REG_NOTE_KIND (link, REG_DEAD);
3920: XEXP (link, 0) = temp;
3921: XEXP (link, 1) = REG_NOTES (insn);
3922: REG_NOTES (insn) = link;
3923:
3924: /* If killed multiple registers here, then add in the excess. */
3925: i += HARD_REGNO_NREGS (REGNO (temp), GET_MODE (temp)) - 1;
3926:
3927: break;
3928: }
3929: /* It isn't mentioned anywhere, so no new reg note is needed for
3930: this register. */
3931: if (insn == first)
3932: break;
3933: }
3934: }
3935: }
3936:
3937: /* Subroutine of update_flow_info. Determines whether a SET or CLOBBER in an
3938: insn created by splitting needs a REG_DEAD or REG_UNUSED note added. */
3939:
3940: static void
3941: new_insn_dead_notes (pat, insn, last, orig_insn)
3942: rtx pat, insn, last, orig_insn;
3943: {
3944: rtx dest, tem, set;
3945:
3946: /* PAT is either a CLOBBER or a SET here. */
3947: dest = XEXP (pat, 0);
3948:
3949: while (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SUBREG
3950: || GET_CODE (dest) == STRICT_LOW_PART
3951: || GET_CODE (dest) == SIGN_EXTRACT)
3952: dest = XEXP (dest, 0);
3953:
3954: if (GET_CODE (dest) == REG)
3955: {
3956: for (tem = last; tem != insn; tem = PREV_INSN (tem))
3957: {
3958: if (GET_RTX_CLASS (GET_CODE (tem)) == 'i'
3959: && reg_overlap_mentioned_p (dest, PATTERN (tem))
3960: && (set = single_set (tem)))
3961: {
3962: rtx tem_dest = SET_DEST (set);
3963:
3964: while (GET_CODE (tem_dest) == ZERO_EXTRACT
3965: || GET_CODE (tem_dest) == SUBREG
3966: || GET_CODE (tem_dest) == STRICT_LOW_PART
3967: || GET_CODE (tem_dest) == SIGN_EXTRACT)
3968: tem_dest = XEXP (tem_dest, 0);
3969:
3970: if (tem_dest != dest)
3971: {
3972: /* Use the same scheme as combine.c, don't put both REG_DEAD
3973: and REG_UNUSED notes on the same insn. */
3974: if (! find_regno_note (tem, REG_UNUSED, REGNO (dest))
3975: && ! find_regno_note (tem, REG_DEAD, REGNO (dest)))
3976: {
3977: rtx note = rtx_alloc (EXPR_LIST);
3978: PUT_REG_NOTE_KIND (note, REG_DEAD);
3979: XEXP (note, 0) = dest;
3980: XEXP (note, 1) = REG_NOTES (tem);
3981: REG_NOTES (tem) = note;
3982: }
3983: /* The reg only dies in one insn, the last one that uses
3984: it. */
3985: break;
3986: }
3987: else if (reg_overlap_mentioned_p (dest, SET_SRC (set)))
3988: /* We found an instruction that both uses the register,
3989: and sets it, so no new REG_NOTE is needed for this set. */
3990: break;
3991: }
3992: }
3993: /* If this is a set, it must die somewhere, unless it is the dest of
3994: the original insn, and hence is live after the original insn. Abort
3995: if it isn't supposed to be live after the original insn.
3996:
3997: If this is a clobber, then just add a REG_UNUSED note. */
3998: if (tem == insn)
3999: {
4000: int live_after_orig_insn = 0;
4001: rtx pattern = PATTERN (orig_insn);
4002: int i;
4003:
4004: if (GET_CODE (pat) == CLOBBER)
4005: {
4006: rtx note = rtx_alloc (EXPR_LIST);
4007: PUT_REG_NOTE_KIND (note, REG_UNUSED);
4008: XEXP (note, 0) = dest;
4009: XEXP (note, 1) = REG_NOTES (insn);
4010: REG_NOTES (insn) = note;
4011: return;
4012: }
4013:
4014: /* The original insn could have multiple sets, so search the
4015: insn for all sets. */
4016: if (GET_CODE (pattern) == SET)
4017: {
4018: if (reg_overlap_mentioned_p (dest, SET_DEST (pattern)))
4019: live_after_orig_insn = 1;
4020: }
4021: else if (GET_CODE (pattern) == PARALLEL)
4022: {
4023: for (i = 0; i < XVECLEN (pattern, 0); i++)
4024: if (GET_CODE (XVECEXP (pattern, 0, i)) == SET
4025: && reg_overlap_mentioned_p (dest,
4026: SET_DEST (XVECEXP (pattern,
4027: 0, i))))
4028: live_after_orig_insn = 1;
4029: }
4030:
4031: if (! live_after_orig_insn)
4032: abort ();
4033: }
4034: }
4035: }
4036:
4037: /* Subroutine of update_flow_info. Update the value of reg_n_sets for all
4038: registers modified by X. INC is -1 if the containing insn is being deleted,
4039: and is 1 if the containing insn is a newly generated insn. */
4040:
4041: static void
4042: update_n_sets (x, inc)
4043: rtx x;
4044: int inc;
4045: {
4046: rtx dest = SET_DEST (x);
4047:
4048: while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
4049: || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
4050: dest = SUBREG_REG (dest);
4051:
4052: if (GET_CODE (dest) == REG)
4053: {
4054: int regno = REGNO (dest);
4055:
4056: if (regno < FIRST_PSEUDO_REGISTER)
4057: {
4058: register int i;
4059: int endregno = regno + HARD_REGNO_NREGS (regno, GET_MODE (dest));
4060:
4061: for (i = regno; i < endregno; i++)
4062: reg_n_sets[i] += inc;
4063: }
4064: else
4065: reg_n_sets[regno] += inc;
4066: }
4067: }
4068:
4069: /* Updates all flow-analysis related quantities (including REG_NOTES) for
4070: the insns from FIRST to LAST inclusive that were created by splitting
4071: ORIG_INSN. NOTES are the original REG_NOTES. */
4072:
4073: static void
4074: update_flow_info (notes, first, last, orig_insn)
4075: rtx notes;
4076: rtx first, last;
4077: rtx orig_insn;
4078: {
4079: rtx insn, note;
4080: rtx next;
4081: rtx orig_dest, temp;
4082: rtx set;
4083:
4084: /* Get and save the destination set by the original insn. */
4085:
4086: orig_dest = single_set (orig_insn);
4087: if (orig_dest)
4088: orig_dest = SET_DEST (orig_dest);
4089:
4090: /* Move REG_NOTES from the original insn to where they now belong. */
4091:
4092: for (note = notes; note; note = next)
4093: {
4094: next = XEXP (note, 1);
4095: switch (REG_NOTE_KIND (note))
4096: {
4097: case REG_DEAD:
4098: case REG_UNUSED:
4099: /* Move these notes from the original insn to the last new insn where
4100: the register is now set. */
4101:
4102: for (insn = last; ; insn = PREV_INSN (insn))
4103: {
4104: if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
4105: && reg_mentioned_p (XEXP (note, 0), PATTERN (insn)))
4106: {
4107: /* If this note refers to a multiple word hard register, it
4108: may have been split into several smaller hard register
4109: references, so handle it specially. */
4110: temp = XEXP (note, 0);
4111: if (REG_NOTE_KIND (note) == REG_DEAD
4112: && GET_CODE (temp) == REG
4113: && REGNO (temp) < FIRST_PSEUDO_REGISTER
4114: && HARD_REGNO_NREGS (REGNO (temp), GET_MODE (temp)) > 1)
4115: split_hard_reg_notes (note, first, last, orig_insn);
4116: else
4117: {
4118: XEXP (note, 1) = REG_NOTES (insn);
4119: REG_NOTES (insn) = note;
4120: }
4121:
4122: /* Sometimes need to convert REG_UNUSED notes to REG_DEAD
4123: notes. */
4124: /* ??? This won't handle multiple word registers correctly,
4125: but should be good enough for now. */
4126: if (REG_NOTE_KIND (note) == REG_UNUSED
4127: && ! dead_or_set_p (insn, XEXP (note, 0)))
4128: PUT_REG_NOTE_KIND (note, REG_DEAD);
4129:
4130: /* The reg only dies in one insn, the last one that uses
4131: it. */
4132: break;
4133: }
4134: /* It must die somewhere, fail it we couldn't find where it died.
4135:
4136: If this is a REG_UNUSED note, then it must be a temporary
4137: register that was not needed by this instantiation of the
4138: pattern, so we can safely ignore it. */
4139: if (insn == first)
4140: {
4141: if (REG_NOTE_KIND (note) != REG_UNUSED)
4142: abort ();
4143:
4144: break;
4145: }
4146: }
4147: break;
4148:
4149: case REG_WAS_0:
4150: /* This note applies to the dest of the original insn. Find the
4151: first new insn that now has the same dest, and move the note
4152: there. */
4153:
4154: if (! orig_dest)
4155: abort ();
4156:
4157: for (insn = first; ; insn = NEXT_INSN (insn))
4158: {
4159: if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
4160: && (temp = single_set (insn))
4161: && rtx_equal_p (SET_DEST (temp), orig_dest))
4162: {
4163: XEXP (note, 1) = REG_NOTES (insn);
4164: REG_NOTES (insn) = note;
4165: /* The reg is only zero before one insn, the first that
4166: uses it. */
4167: break;
4168: }
4169: /* It must be set somewhere, fail if we couldn't find where it
4170: was set. */
4171: if (insn == last)
4172: abort ();
4173: }
4174: break;
4175:
4176: case REG_EQUAL:
4177: case REG_EQUIV:
4178: /* A REG_EQUIV or REG_EQUAL note on an insn with more than one
4179: set is meaningless. Just drop the note. */
4180: if (! orig_dest)
4181: break;
4182:
4183: case REG_NO_CONFLICT:
4184: /* These notes apply to the dest of the original insn. Find the last
4185: new insn that now has the same dest, and move the note there. */
4186:
4187: if (! orig_dest)
4188: abort ();
4189:
4190: for (insn = last; ; insn = PREV_INSN (insn))
4191: {
4192: if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
4193: && (temp = single_set (insn))
4194: && rtx_equal_p (SET_DEST (temp), orig_dest))
4195: {
4196: XEXP (note, 1) = REG_NOTES (insn);
4197: REG_NOTES (insn) = note;
4198: /* Only put this note on one of the new insns. */
4199: break;
4200: }
4201:
4202: /* The original dest must still be set someplace. Abort if we
4203: couldn't find it. */
4204: if (insn == first)
4205: abort ();
4206: }
4207: break;
4208:
4209: case REG_LIBCALL:
4210: /* Move a REG_LIBCALL note to the first insn created, and update
4211: the corresponding REG_RETVAL note. */
4212: XEXP (note, 1) = REG_NOTES (first);
4213: REG_NOTES (first) = note;
4214:
4215: insn = XEXP (note, 0);
4216: note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
4217: if (note)
4218: XEXP (note, 0) = first;
4219: break;
4220:
4221: case REG_RETVAL:
4222: /* Move a REG_RETVAL note to the last insn created, and update
4223: the corresponding REG_LIBCALL note. */
4224: XEXP (note, 1) = REG_NOTES (last);
4225: REG_NOTES (last) = note;
4226:
4227: insn = XEXP (note, 0);
4228: note = find_reg_note (insn, REG_LIBCALL, NULL_RTX);
4229: if (note)
4230: XEXP (note, 0) = last;
4231: break;
4232:
4233: case REG_NONNEG:
4234: /* This should be moved to whichever instruction is a JUMP_INSN. */
4235:
4236: for (insn = last; ; insn = PREV_INSN (insn))
4237: {
4238: if (GET_CODE (insn) == JUMP_INSN)
4239: {
4240: XEXP (note, 1) = REG_NOTES (insn);
4241: REG_NOTES (insn) = note;
4242: /* Only put this note on one of the new insns. */
4243: break;
4244: }
4245: /* Fail if we couldn't find a JUMP_INSN. */
4246: if (insn == first)
4247: abort ();
4248: }
4249: break;
4250:
4251: case REG_INC:
4252: /* This should be moved to whichever instruction now has the
4253: increment operation. */
4254: abort ();
4255:
4256: case REG_LABEL:
4257: /* Should be moved to the new insn(s) which use the label. */
4258: for (insn = first; insn != NEXT_INSN (last); insn = NEXT_INSN (insn))
4259: if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
4260: && reg_mentioned_p (XEXP (note, 0), PATTERN (insn)))
4261: REG_NOTES (insn) = gen_rtx (EXPR_LIST, REG_LABEL,
4262: XEXP (note, 0), REG_NOTES (insn));
4263: break;
4264:
4265: case REG_CC_SETTER:
4266: case REG_CC_USER:
4267: /* These two notes will never appear until after reorg, so we don't
4268: have to handle them here. */
4269: default:
4270: abort ();
4271: }
4272: }
4273:
4274: /* Each new insn created, except the last, has a new set. If the destination
4275: is a register, then this reg is now live across several insns, whereas
4276: previously the dest reg was born and died within the same insn. To
4277: reflect this, we now need a REG_DEAD note on the insn where this
4278: dest reg dies.
4279:
4280: Similarly, the new insns may have clobbers that need REG_UNUSED notes. */
4281:
4282: for (insn = first; insn != last; insn = NEXT_INSN (insn))
4283: {
4284: rtx pat;
4285: int i;
4286:
4287: pat = PATTERN (insn);
4288: if (GET_CODE (pat) == SET || GET_CODE (pat) == CLOBBER)
4289: new_insn_dead_notes (pat, insn, last, orig_insn);
4290: else if (GET_CODE (pat) == PARALLEL)
4291: {
4292: for (i = 0; i < XVECLEN (pat, 0); i++)
4293: if (GET_CODE (XVECEXP (pat, 0, i)) == SET
4294: || GET_CODE (XVECEXP (pat, 0, i)) == CLOBBER)
4295: new_insn_dead_notes (XVECEXP (pat, 0, i), insn, last, orig_insn);
4296: }
4297: }
4298:
4299: /* If any insn, except the last, uses the register set by the last insn,
4300: then we need a new REG_DEAD note on that insn. In this case, there
4301: would not have been a REG_DEAD note for this register in the original
4302: insn because it was used and set within one insn.
4303:
4304: There is no new REG_DEAD note needed if the last insn uses the register
4305: that it is setting. */
4306:
4307: set = single_set (last);
4308: if (set)
4309: {
4310: rtx dest = SET_DEST (set);
4311:
4312: while (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SUBREG
4313: || GET_CODE (dest) == STRICT_LOW_PART
4314: || GET_CODE (dest) == SIGN_EXTRACT)
4315: dest = XEXP (dest, 0);
4316:
4317: if (GET_CODE (dest) == REG
4318: && ! reg_overlap_mentioned_p (dest, SET_SRC (set)))
4319: {
4320: for (insn = PREV_INSN (last); ; insn = PREV_INSN (insn))
4321: {
4322: if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
4323: && reg_mentioned_p (dest, PATTERN (insn))
4324: && (set = single_set (insn)))
4325: {
4326: rtx insn_dest = SET_DEST (set);
4327:
4328: while (GET_CODE (insn_dest) == ZERO_EXTRACT
4329: || GET_CODE (insn_dest) == SUBREG
4330: || GET_CODE (insn_dest) == STRICT_LOW_PART
4331: || GET_CODE (insn_dest) == SIGN_EXTRACT)
4332: insn_dest = XEXP (insn_dest, 0);
4333:
4334: if (insn_dest != dest)
4335: {
4336: note = rtx_alloc (EXPR_LIST);
4337: PUT_REG_NOTE_KIND (note, REG_DEAD);
4338: XEXP (note, 0) = dest;
4339: XEXP (note, 1) = REG_NOTES (insn);
4340: REG_NOTES (insn) = note;
4341: /* The reg only dies in one insn, the last one
4342: that uses it. */
4343: break;
4344: }
4345: }
4346: if (insn == first)
4347: break;
4348: }
4349: }
4350: }
4351:
4352: /* If the original dest is modifying a multiple register target, and the
4353: original instruction was split such that the original dest is now set
4354: by two or more SUBREG sets, then the split insns no longer kill the
4355: destination of the original insn.
4356:
4357: In this case, if there exists an instruction in the same basic block,
4358: before the split insn, which uses the original dest, and this use is
4359: killed by the original insn, then we must remove the REG_DEAD note on
4360: this insn, because it is now superfluous.
4361:
4362: This does not apply when a hard register gets split, because the code
4363: knows how to handle overlapping hard registers properly. */
4364: if (orig_dest && GET_CODE (orig_dest) == REG)
4365: {
4366: int found_orig_dest = 0;
4367: int found_split_dest = 0;
4368:
4369: for (insn = first; ; insn = NEXT_INSN (insn))
4370: {
4371: set = single_set (insn);
4372: if (set)
4373: {
4374: if (GET_CODE (SET_DEST (set)) == REG
4375: && REGNO (SET_DEST (set)) == REGNO (orig_dest))
4376: {
4377: found_orig_dest = 1;
4378: break;
4379: }
4380: else if (GET_CODE (SET_DEST (set)) == SUBREG
4381: && SUBREG_REG (SET_DEST (set)) == orig_dest)
4382: {
4383: found_split_dest = 1;
4384: break;
4385: }
4386: }
4387:
4388: if (insn == last)
4389: break;
4390: }
4391:
4392: if (found_split_dest)
4393: {
4394: /* Search backwards from FIRST, looking for the first insn that uses
4395: the original dest. Stop if we pass a CODE_LABEL or a JUMP_INSN.
4396: If we find an insn, and it has a REG_DEAD note, then delete the
4397: note. */
4398:
4399: for (insn = first; insn; insn = PREV_INSN (insn))
4400: {
4401: if (GET_CODE (insn) == CODE_LABEL
4402: || GET_CODE (insn) == JUMP_INSN)
4403: break;
4404: else if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
4405: && reg_mentioned_p (orig_dest, insn))
4406: {
4407: note = find_regno_note (insn, REG_DEAD, REGNO (orig_dest));
4408: if (note)
4409: remove_note (insn, note);
4410: }
4411: }
4412: }
4413: else if (! found_orig_dest)
4414: {
4415: /* This should never happen. */
4416: abort ();
4417: }
4418: }
4419:
4420: /* Update reg_n_sets. This is necessary to prevent local alloc from
4421: converting REG_EQUAL notes to REG_EQUIV when splitting has modified
4422: a reg from set once to set multiple times. */
4423:
4424: {
4425: rtx x = PATTERN (orig_insn);
4426: RTX_CODE code = GET_CODE (x);
4427:
4428: if (code == SET || code == CLOBBER)
4429: update_n_sets (x, -1);
4430: else if (code == PARALLEL)
4431: {
4432: int i;
4433: for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
4434: {
4435: code = GET_CODE (XVECEXP (x, 0, i));
4436: if (code == SET || code == CLOBBER)
4437: update_n_sets (XVECEXP (x, 0, i), -1);
4438: }
4439: }
4440:
4441: for (insn = first; ; insn = NEXT_INSN (insn))
4442: {
4443: x = PATTERN (insn);
4444: code = GET_CODE (x);
4445:
4446: if (code == SET || code == CLOBBER)
4447: update_n_sets (x, 1);
4448: else if (code == PARALLEL)
4449: {
4450: int i;
4451: for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
4452: {
4453: code = GET_CODE (XVECEXP (x, 0, i));
4454: if (code == SET || code == CLOBBER)
4455: update_n_sets (XVECEXP (x, 0, i), 1);
4456: }
4457: }
4458:
4459: if (insn == last)
4460: break;
4461: }
4462: }
4463: }
4464:
4465: /* The one entry point in this file. DUMP_FILE is the dump file for
4466: this pass. */
4467:
4468: void
4469: schedule_insns (dump_file)
4470: FILE *dump_file;
4471: {
4472: int max_uid = MAX_INSNS_PER_SPLIT * (get_max_uid () + 1);
4473: int i, b;
4474: rtx insn;
4475:
4476: /* Taking care of this degenerate case makes the rest of
4477: this code simpler. */
4478: if (n_basic_blocks == 0)
4479: return;
4480:
4481: /* Create an insn here so that we can hang dependencies off of it later. */
4482: sched_before_next_call
4483: = gen_rtx (INSN, VOIDmode, 0, NULL_RTX, NULL_RTX,
4484: NULL_RTX, 0, NULL_RTX, 0);
4485:
4486: /* Initialize the unused_*_lists. We can't use the ones left over from
4487: the previous function, because gcc has freed that memory. We can use
4488: the ones left over from the first sched pass in the second pass however,
4489: so only clear them on the first sched pass. The first pass is before
4490: reload if flag_schedule_insns is set, otherwise it is afterwards. */
4491:
4492: if (reload_completed == 0 || ! flag_schedule_insns)
4493: {
4494: unused_insn_list = 0;
4495: unused_expr_list = 0;
4496: }
4497:
4498: /* We create no insns here, only reorder them, so we
4499: remember how far we can cut back the stack on exit. */
4500:
4501: /* Allocate data for this pass. See comments, above,
4502: for what these vectors do. */
4503: insn_luid = (int *) alloca (max_uid * sizeof (int));
4504: insn_priority = (int *) alloca (max_uid * sizeof (int));
4505: insn_tick = (int *) alloca (max_uid * sizeof (int));
4506: insn_costs = (short *) alloca (max_uid * sizeof (short));
4507: insn_units = (short *) alloca (max_uid * sizeof (short));
4508: insn_blockage = (unsigned int *) alloca (max_uid * sizeof (unsigned int));
4509: insn_ref_count = (int *) alloca (max_uid * sizeof (int));
4510:
4511: if (reload_completed == 0)
4512: {
4513: sched_reg_n_deaths = (short *) alloca (max_regno * sizeof (short));
4514: sched_reg_n_calls_crossed = (int *) alloca (max_regno * sizeof (int));
4515: sched_reg_live_length = (int *) alloca (max_regno * sizeof (int));
4516: bb_dead_regs = (regset) alloca (regset_bytes);
4517: bb_live_regs = (regset) alloca (regset_bytes);
4518: bzero (sched_reg_n_calls_crossed, max_regno * sizeof (int));
4519: bzero (sched_reg_live_length, max_regno * sizeof (int));
4520: bcopy (reg_n_deaths, sched_reg_n_deaths, max_regno * sizeof (short));
4521: init_alias_analysis ();
4522: }
4523: else
4524: {
4525: sched_reg_n_deaths = 0;
4526: sched_reg_n_calls_crossed = 0;
4527: sched_reg_live_length = 0;
4528: bb_dead_regs = 0;
4529: bb_live_regs = 0;
4530: if (! flag_schedule_insns)
4531: init_alias_analysis ();
4532: }
4533:
4534: if (write_symbols != NO_DEBUG)
4535: {
4536: rtx line;
4537:
4538: line_note = (rtx *) alloca (max_uid * sizeof (rtx));
4539: bzero (line_note, max_uid * sizeof (rtx));
4540: line_note_head = (rtx *) alloca (n_basic_blocks * sizeof (rtx));
4541: bzero (line_note_head, n_basic_blocks * sizeof (rtx));
4542:
4543: /* Determine the line-number at the start of each basic block.
4544: This must be computed and saved now, because after a basic block's
4545: predecessor has been scheduled, it is impossible to accurately
4546: determine the correct line number for the first insn of the block. */
4547:
4548: for (b = 0; b < n_basic_blocks; b++)
4549: for (line = basic_block_head[b]; line; line = PREV_INSN (line))
4550: if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
4551: {
4552: line_note_head[b] = line;
4553: break;
4554: }
4555: }
4556:
4557: bzero (insn_luid, max_uid * sizeof (int));
4558: bzero (insn_priority, max_uid * sizeof (int));
4559: bzero (insn_tick, max_uid * sizeof (int));
4560: bzero (insn_costs, max_uid * sizeof (short));
4561: bzero (insn_units, max_uid * sizeof (short));
4562: bzero (insn_blockage, max_uid * sizeof (unsigned int));
4563: bzero (insn_ref_count, max_uid * sizeof (int));
4564:
4565: /* Schedule each basic block, block by block. */
4566:
4567: /* ??? Add a NOTE after the last insn of the last basic block. It is not
4568: known why this is done. */
4569:
4570: insn = basic_block_end[n_basic_blocks-1];
4571: if (NEXT_INSN (insn) == 0
4572: || (GET_CODE (insn) != NOTE
4573: && GET_CODE (insn) != CODE_LABEL
4574: /* Don't emit a NOTE if it would end up between an unconditional
4575: jump and a BARRIER. */
4576: && ! (GET_CODE (insn) == JUMP_INSN
4577: && GET_CODE (NEXT_INSN (insn)) == BARRIER)))
4578: emit_note_after (NOTE_INSN_DELETED, basic_block_end[n_basic_blocks-1]);
4579:
4580: for (b = 0; b < n_basic_blocks; b++)
4581: {
4582: rtx insn, next;
4583: rtx insns;
4584:
4585: note_list = 0;
4586:
4587: for (insn = basic_block_head[b]; ; insn = next)
4588: {
4589: rtx prev;
4590: rtx set;
4591:
4592: /* Can't use `next_real_insn' because that
4593: might go across CODE_LABELS and short-out basic blocks. */
4594: next = NEXT_INSN (insn);
4595: if (GET_CODE (insn) != INSN)
4596: {
4597: if (insn == basic_block_end[b])
4598: break;
4599:
4600: continue;
4601: }
4602:
4603: /* Don't split no-op move insns. These should silently disappear
4604: later in final. Splitting such insns would break the code
4605: that handles REG_NO_CONFLICT blocks. */
4606: set = single_set (insn);
4607: if (set && rtx_equal_p (SET_SRC (set), SET_DEST (set)))
4608: {
4609: if (insn == basic_block_end[b])
4610: break;
4611:
4612: /* Nops get in the way while scheduling, so delete them now if
4613: register allocation has already been done. It is too risky
4614: to try to do this before register allocation, and there are
4615: unlikely to be very many nops then anyways. */
4616: if (reload_completed)
4617: {
4618: PUT_CODE (insn, NOTE);
4619: NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
4620: NOTE_SOURCE_FILE (insn) = 0;
4621: }
4622:
4623: continue;
4624: }
4625:
4626: /* Split insns here to get max fine-grain parallelism. */
4627: prev = PREV_INSN (insn);
4628: if (reload_completed == 0)
4629: {
4630: rtx last, first = PREV_INSN (insn);
4631: rtx notes = REG_NOTES (insn);
4632:
4633: last = try_split (PATTERN (insn), insn, 1);
4634: if (last != insn)
4635: {
4636: /* try_split returns the NOTE that INSN became. */
4637: first = NEXT_INSN (first);
4638: update_flow_info (notes, first, last, insn);
4639:
4640: PUT_CODE (insn, NOTE);
4641: NOTE_SOURCE_FILE (insn) = 0;
4642: NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
4643: if (insn == basic_block_head[b])
4644: basic_block_head[b] = first;
4645: if (insn == basic_block_end[b])
4646: {
4647: basic_block_end[b] = last;
4648: break;
4649: }
4650: }
4651: }
4652:
4653: if (insn == basic_block_end[b])
4654: break;
4655: }
4656:
4657: schedule_block (b, dump_file);
4658:
4659: #ifdef USE_C_ALLOCA
4660: alloca (0);
4661: #endif
4662: }
4663:
4664: /* Reposition the prologue and epilogue notes in case we moved the
4665: prologue/epilogue insns. */
4666: if (reload_completed)
4667: reposition_prologue_and_epilogue_notes (get_insns ());
4668:
4669: if (write_symbols != NO_DEBUG)
4670: {
4671: rtx line = 0;
4672: rtx insn = get_insns ();
4673: int active_insn = 0;
4674: int notes = 0;
4675:
4676: /* Walk the insns deleting redundant line-number notes. Many of these
4677: are already present. The remainder tend to occur at basic
4678: block boundaries. */
4679: for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
4680: if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
4681: {
4682: /* If there are no active insns following, INSN is redundant. */
4683: if (active_insn == 0)
4684: {
4685: notes++;
4686: NOTE_SOURCE_FILE (insn) = 0;
4687: NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
4688: }
4689: /* If the line number is unchanged, LINE is redundant. */
4690: else if (line
4691: && NOTE_LINE_NUMBER (line) == NOTE_LINE_NUMBER (insn)
4692: && NOTE_SOURCE_FILE (line) == NOTE_SOURCE_FILE (insn))
4693: {
4694: notes++;
4695: NOTE_SOURCE_FILE (line) = 0;
4696: NOTE_LINE_NUMBER (line) = NOTE_INSN_DELETED;
4697: line = insn;
4698: }
4699: else
4700: line = insn;
4701: active_insn = 0;
4702: }
4703: else if (! ((GET_CODE (insn) == NOTE
4704: && NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED)
4705: || (GET_CODE (insn) == INSN
4706: && (GET_CODE (PATTERN (insn)) == USE
4707: || GET_CODE (PATTERN (insn)) == CLOBBER))))
4708: active_insn++;
4709:
4710: if (dump_file && notes)
4711: fprintf (dump_file, ";; deleted %d line-number notes\n", notes);
4712: }
4713:
4714: if (reload_completed == 0)
4715: {
4716: int regno;
4717: for (regno = 0; regno < max_regno; regno++)
4718: if (sched_reg_live_length[regno])
4719: {
4720: if (dump_file)
4721: {
4722: if (reg_live_length[regno] > sched_reg_live_length[regno])
4723: fprintf (dump_file,
4724: ";; register %d life shortened from %d to %d\n",
4725: regno, reg_live_length[regno],
4726: sched_reg_live_length[regno]);
4727: /* Negative values are special; don't overwrite the current
4728: reg_live_length value if it is negative. */
4729: else if (reg_live_length[regno] < sched_reg_live_length[regno]
4730: && reg_live_length[regno] >= 0)
4731: fprintf (dump_file,
4732: ";; register %d life extended from %d to %d\n",
4733: regno, reg_live_length[regno],
4734: sched_reg_live_length[regno]);
4735:
4736: if (! reg_n_calls_crossed[regno]
4737: && sched_reg_n_calls_crossed[regno])
4738: fprintf (dump_file,
4739: ";; register %d now crosses calls\n", regno);
4740: else if (reg_n_calls_crossed[regno]
4741: && ! sched_reg_n_calls_crossed[regno]
4742: && reg_basic_block[regno] != REG_BLOCK_GLOBAL)
4743: fprintf (dump_file,
4744: ";; register %d no longer crosses calls\n", regno);
4745:
4746: }
4747: /* Negative values are special; don't overwrite the current
4748: reg_live_length value if it is negative. */
4749: if (reg_live_length[regno] >= 0)
4750: reg_live_length[regno] = sched_reg_live_length[regno];
4751:
4752: /* We can't change the value of reg_n_calls_crossed to zero for
4753: pseudos which are live in more than one block.
4754:
4755: This is because combine might have made an optimization which
4756: invalidated basic_block_live_at_start and reg_n_calls_crossed,
4757: but it does not update them. If we update reg_n_calls_crossed
4758: here, the two variables are now inconsistent, and this might
4759: confuse the caller-save code into saving a register that doesn't
4760: need to be saved. This is only a problem when we zero calls
4761: crossed for a pseudo live in multiple basic blocks.
4762:
4763: Alternatively, we could try to correctly update basic block live
4764: at start here in sched, but that seems complicated. */
4765: if (sched_reg_n_calls_crossed[regno]
4766: || reg_basic_block[regno] != REG_BLOCK_GLOBAL)
4767: reg_n_calls_crossed[regno] = sched_reg_n_calls_crossed[regno];
4768: }
4769: }
4770: }
4771: #endif /* INSN_SCHEDULING */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.