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