![[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:
147: /* Vector indexed by INSN_UID giving number of insns refering to this insn. */
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: else if (GET_CODE (x) != CLOBBER)
1184: sched_analyze_2 (dest, insn);
1185: }
1186:
1187: /* Analyze the uses of memory and registers in rtx X in INSN. */
1188:
1189: static void
1190: sched_analyze_2 (x, insn)
1191: rtx x;
1192: rtx insn;
1193: {
1194: register int i;
1195: register int j;
1196: register enum rtx_code code;
1197: register char *fmt;
1198:
1199: if (x == 0)
1200: return;
1201:
1202: code = GET_CODE (x);
1203:
1204: /* Get rid of the easy cases first. */
1205:
1206: /* Ignore constants. Note that we must handle CONST_DOUBLE here
1207: because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but
1208: this does not mean that this insn is using cc0. */
1209: if (code == CONST_INT || code == CONST_DOUBLE || code == SYMBOL_REF
1210: || code == CONST || code == LABEL_REF)
1211: return;
1212:
1213: #ifdef HAVE_cc0
1214: else if (code == CC0)
1215: {
1216: rtx link;
1217:
1218: /* User of CC0 depends on immediately preceding insn.
1219: All notes are removed from the list of insns to schedule before we
1220: reach here, so the previous insn must be the setter of cc0. */
1221: if (GET_CODE (PREV_INSN (insn)) != INSN)
1222: abort ();
1223: SCHED_GROUP_P (insn) = 1;
1224:
1225: /* Make a copy of all dependencies on PREV_INSN, and add to this insn.
1226: This is so that all the dependencies will apply to the group. */
1227:
1228: for (link = LOG_LINKS (PREV_INSN (insn)); link; link = XEXP (link, 1))
1229: add_dependence (insn, XEXP (link, 0), GET_MODE (link));
1230:
1231: return;
1232: }
1233: #endif
1234:
1235: else if (code == REG)
1236: {
1237: int regno = REGNO (x);
1238: if (regno < FIRST_PSEUDO_REGISTER)
1239: {
1240: int i;
1241:
1242: i = HARD_REGNO_NREGS (regno, GET_MODE (x));
1243: while (--i >= 0)
1244: {
1245: reg_last_uses[regno + i]
1246: = gen_rtx (INSN_LIST, VOIDmode,
1247: insn, reg_last_uses[regno + i]);
1248: if (reg_last_sets[regno + i])
1249: add_dependence (insn, reg_last_sets[regno + i], 0);
1250: if ((call_used_regs[regno + i] || global_regs[regno + i])
1251: && last_function_call)
1252: /* Function calls clobber all call_used regs. */
1253: add_dependence (insn, last_function_call, REG_DEP_ANTI);
1254: }
1255: }
1256: else
1257: {
1258: reg_last_uses[regno]
1259: = gen_rtx (INSN_LIST, VOIDmode, insn, reg_last_uses[regno]);
1260: if (reg_last_sets[regno])
1261: add_dependence (insn, reg_last_sets[regno], 0);
1262:
1263: /* If the register does not already cross any calls, then add this
1264: insn to the sched_before_next_call list so that it will still
1265: not cross calls after scheduling. */
1266: if (reg_n_calls_crossed[regno] == 0)
1267: add_dependence (sched_before_next_call, insn, REG_DEP_ANTI);
1268: }
1269: return;
1270: }
1271:
1272: /* The interesting case. */
1273: else if (code == MEM)
1274: {
1275: /* Reading memory. */
1276:
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;
1283:
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);
1292:
1293: pending = XEXP (pending, 1);
1294: pending_mem = XEXP (pending_mem, 1);
1295: }
1296:
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);
1305:
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);
1311:
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: }
1321:
1322: else if (code == ASM_OPERANDS || code == ASM_INPUT
1323: || code == UNSPEC_VOLATILE)
1324: {
1325: rtx u;
1326:
1327: /* Traditional and volatile asm instructions must be considered to use
1328: and clobber all hard registers and all of memory. So must
1329: UNSPEC_VOLATILE operations. */
1330: if ((code == ASM_OPERANDS && MEM_VOLATILE_P (x)) || code == ASM_INPUT
1331: || code == UNSPEC_VOLATILE)
1332: {
1333: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1334: {
1335: for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
1336: if (GET_CODE (PATTERN (XEXP (u, 0))) != USE)
1337: add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
1338: reg_last_uses[i] = 0;
1339: if (reg_last_sets[i]
1340: && GET_CODE (PATTERN (reg_last_sets[i])) != USE)
1341: add_dependence (insn, reg_last_sets[i], 0);
1342: reg_last_sets[i] = insn;
1343: }
1344:
1345: flush_pending_lists (insn);
1346: }
1347:
1348: /* For all ASM_OPERANDS, we must traverse the vector of input operands.
1349: We can not just fall through here since then we would be confused
1350: by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
1351: traditional asms unlike their normal usage. */
1352:
1353: if (code == ASM_OPERANDS)
1354: {
1355: for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
1356: sched_analyze_2 (ASM_OPERANDS_INPUT (x, j), insn);
1357: return;
1358: }
1359: }
1360:
1361: /* Other cases: walk the insn. */
1362: fmt = GET_RTX_FORMAT (code);
1363: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1364: {
1365: if (fmt[i] == 'e')
1366: sched_analyze_2 (XEXP (x, i), insn);
1367: else if (fmt[i] == 'E')
1368: for (j = 0; j < XVECLEN (x, i); j++)
1369: sched_analyze_2 (XVECEXP (x, i, j), insn);
1370: }
1371: }
1372:
1373: /* Analyze an INSN with pattern X to find all dependencies. */
1374:
1375: static void
1376: sched_analyze_insn (x, insn)
1377: rtx x, insn;
1378: {
1379: register RTX_CODE code = GET_CODE (x);
1380: rtx link;
1381:
1382: if (code == SET || code == CLOBBER)
1383: sched_analyze_1 (x, insn);
1384: else if (code == PARALLEL)
1385: {
1386: register int i;
1387: for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
1388: {
1389: code = GET_CODE (XVECEXP (x, 0, i));
1390: if (code == SET || code == CLOBBER)
1391: sched_analyze_1 (XVECEXP (x, 0, i), insn);
1392: else
1393: sched_analyze_2 (XVECEXP (x, 0, i), insn);
1394: }
1395: }
1396: else
1397: sched_analyze_2 (x, insn);
1398:
1399: for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1400: {
1401: /* Any REG_INC note is a SET of the register indicated. */
1402: if (REG_NOTE_KIND (link) == REG_INC)
1403: {
1404: rtx dest = XEXP (link, 0);
1405: int regno = REGNO (dest);
1406: int i;
1407:
1408: /* A hard reg in a wide mode may really be multiple registers.
1409: If so, mark all of them just like the first. */
1410: if (regno < FIRST_PSEUDO_REGISTER)
1411: {
1412: i = HARD_REGNO_NREGS (regno, GET_MODE (dest));
1413: while (--i >= 0)
1414: {
1415: rtx u;
1416:
1417: for (u = reg_last_uses[regno+i]; u; u = XEXP (u, 1))
1418: add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
1419: reg_last_uses[regno + i] = 0;
1420: if (reg_last_sets[regno + i])
1421: add_dependence (insn, reg_last_sets[regno + i],
1422: REG_DEP_OUTPUT);
1423: reg_last_sets[regno + i] = insn;
1424: if ((call_used_regs[i] || global_regs[i])
1425: && last_function_call)
1426: /* Function calls clobber all call_used regs. */
1427: add_dependence (insn, last_function_call, REG_DEP_ANTI);
1428: }
1429: }
1430: else
1431: {
1432: rtx u;
1433:
1434: for (u = reg_last_uses[regno]; u; u = XEXP (u, 1))
1435: add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
1436: reg_last_uses[regno] = 0;
1437: if (reg_last_sets[regno])
1438: add_dependence (insn, reg_last_sets[regno], REG_DEP_OUTPUT);
1439: reg_last_sets[regno] = insn;
1440:
1441: /* Don't let it cross a call after scheduling if it doesn't
1442: already cross one. */
1443: if (reg_n_calls_crossed[regno] == 0 && last_function_call)
1444: add_dependence (insn, last_function_call, 0);
1445: }
1446: }
1447: }
1448:
1449: /* Handle function calls. */
1450: if (GET_CODE (insn) == CALL_INSN)
1451: {
1452: rtx dep_insn;
1453: rtx prev_dep_insn;
1454:
1455: /* When scheduling instructions, we make sure calls don't lose their
1456: accompanying USE insns by depending them one on another in order. */
1457:
1458: prev_dep_insn = insn;
1459: dep_insn = PREV_INSN (insn);
1460: while (GET_CODE (dep_insn) == INSN
1461: && GET_CODE (PATTERN (dep_insn)) == USE)
1462: {
1463: SCHED_GROUP_P (prev_dep_insn) = 1;
1464:
1465: /* Make a copy of all dependencies on dep_insn, and add to insn.
1466: This is so that all of the dependencies will apply to the
1467: group. */
1468:
1469: for (link = LOG_LINKS (dep_insn); link; link = XEXP (link, 1))
1470: add_dependence (insn, XEXP (link, 0), GET_MODE (link));
1471:
1472: prev_dep_insn = dep_insn;
1473: dep_insn = PREV_INSN (dep_insn);
1474: }
1475: }
1476: }
1477:
1478: /* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
1479: for every dependency. */
1480:
1481: static int
1482: sched_analyze (head, tail)
1483: rtx head, tail;
1484: {
1485: register rtx insn;
1486: register int n_insns = 0;
1487: register rtx u;
1488: register int luid = 0;
1489:
1490: for (insn = head; ; insn = NEXT_INSN (insn))
1491: {
1492: INSN_LUID (insn) = luid++;
1493:
1494: if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
1495: {
1496: sched_analyze_insn (PATTERN (insn), insn);
1497: n_insns += 1;
1498: }
1499: else if (GET_CODE (insn) == CALL_INSN)
1500: {
1501: rtx dest = 0;
1502: rtx x;
1503: register int i;
1504:
1505: /* Any instruction using a hard register which may get clobbered
1506: by a call needs to be marked as dependent on this call.
1507: This prevents a use of a hard return reg from being moved
1508: past a void call (i.e. it does not explicitly set the hard
1509: return reg). */
1510:
1511: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1512: if (call_used_regs[i] || global_regs[i])
1513: {
1514: for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
1515: if (GET_CODE (PATTERN (XEXP (u, 0))) != USE)
1516: add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
1517: reg_last_uses[i] = 0;
1518: if (reg_last_sets[i]
1519: && GET_CODE (PATTERN (reg_last_sets[i])) != USE)
1520: add_dependence (insn, reg_last_sets[i], REG_DEP_ANTI);
1521: reg_last_sets[i] = insn;
1522: /* Insn, being a CALL_INSN, magically depends on
1523: `last_function_call' already. */
1524: }
1525:
1526: /* For each insn which shouldn't cross a call, add a dependence
1527: between that insn and this call insn. */
1528: x = LOG_LINKS (sched_before_next_call);
1529: while (x)
1530: {
1531: add_dependence (insn, XEXP (x, 0), REG_DEP_ANTI);
1532: x = XEXP (x, 1);
1533: }
1534: LOG_LINKS (sched_before_next_call) = 0;
1535:
1536: sched_analyze_insn (PATTERN (insn), insn);
1537:
1538: /* We don't need to flush memory for a function call which does
1539: not involve memory. */
1540: if (! CONST_CALL_P (insn))
1541: {
1542: /* In the absence of interprocedural alias analysis,
1543: we must flush all pending reads and writes, and
1544: start new dependencies starting from here. */
1545: flush_pending_lists (insn);
1546: }
1547:
1548: /* Depend this function call (actually, the user of this
1549: function call) on all hard register clobberage. */
1550: last_function_call = insn;
1551: n_insns += 1;
1552: }
1553:
1554: if (insn == tail)
1555: return n_insns;
1556: }
1557: }
1558:
1559: /* Called when we see a set of a register. If death is true, then we are
1560: scanning backwards. Mark that register as unborn. If nobody says
1561: otherwise, that is how things will remain. If death is false, then we
1562: are scanning forwards. Mark that register as being born. */
1563:
1564: static void
1565: sched_note_set (b, x, death)
1566: int b;
1567: rtx x;
1568: int death;
1569: {
1570: register int regno, j;
1571: register rtx reg = SET_DEST (x);
1572: int subreg_p = 0;
1573:
1574: if (reg == 0)
1575: return;
1576:
1577: while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == STRICT_LOW_PART
1578: || GET_CODE (reg) == SIGN_EXTRACT || GET_CODE (reg) == ZERO_EXTRACT)
1579: {
1580: /* Must treat modification of just one hardware register of a multi-reg
1581: value or just a byte field of a register exactly the same way that
1582: mark_set_1 in flow.c does. */
1583: if (GET_CODE (reg) == ZERO_EXTRACT
1584: || GET_CODE (reg) == SIGN_EXTRACT
1585: || (GET_CODE (reg) == SUBREG
1586: && REG_SIZE (SUBREG_REG (reg)) > REG_SIZE (reg)))
1587: subreg_p = 1;
1588:
1589: reg = SUBREG_REG (reg);
1590: }
1591:
1592: if (GET_CODE (reg) != REG)
1593: return;
1594:
1595: /* Global registers are always live, so the code below does not apply
1596: to them. */
1597:
1598: regno = REGNO (reg);
1599: if (regno >= FIRST_PSEUDO_REGISTER || ! global_regs[regno])
1600: {
1601: register int offset = regno / REGSET_ELT_BITS;
1602: register int bit = 1 << (regno % REGSET_ELT_BITS);
1603:
1604: if (death)
1605: {
1606: /* If we only set part of the register, then this set does not
1607: kill it. */
1608: if (subreg_p)
1609: return;
1610:
1611: /* Try killing this register. */
1612: if (regno < FIRST_PSEUDO_REGISTER)
1613: {
1614: int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
1615: while (--j >= 0)
1616: {
1617: offset = (regno + j) / REGSET_ELT_BITS;
1618: bit = 1 << ((regno + j) % REGSET_ELT_BITS);
1619:
1620: bb_live_regs[offset] &= ~bit;
1621: bb_dead_regs[offset] |= bit;
1622: }
1623: }
1624: else
1625: {
1626: bb_live_regs[offset] &= ~bit;
1627: bb_dead_regs[offset] |= bit;
1628: }
1629: }
1630: else
1631: {
1632: /* Make the register live again. */
1633: if (regno < FIRST_PSEUDO_REGISTER)
1634: {
1635: int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
1636: while (--j >= 0)
1637: {
1638: offset = (regno + j) / REGSET_ELT_BITS;
1639: bit = 1 << ((regno + j) % REGSET_ELT_BITS);
1640:
1641: bb_live_regs[offset] |= bit;
1642: bb_dead_regs[offset] &= ~bit;
1643: }
1644: }
1645: else
1646: {
1647: bb_live_regs[offset] |= bit;
1648: bb_dead_regs[offset] &= ~bit;
1649: }
1650: }
1651: }
1652: }
1653:
1654: /* Macros and functions for keeping the priority queue sorted, and
1655: dealing with queueing and unqueueing of instructions. */
1656:
1657: #define SCHED_SORT(READY, NEW_READY, OLD_READY) \
1658: do { if ((NEW_READY) - (OLD_READY) == 1) \
1659: swap_sort (READY, NEW_READY); \
1660: else if ((NEW_READY) - (OLD_READY) > 1) \
1661: qsort (READY, NEW_READY, sizeof (rtx), rank_for_schedule); } \
1662: while (0)
1663:
1664: /* Returns a positive value if y is preferred; returns a negative value if
1665: x is preferred. Should never return 0, since that will make the sort
1666: unstable. */
1667:
1668: static int
1669: rank_for_schedule (x, y)
1670: rtx *x, *y;
1671: {
1672: rtx tmp = *y;
1673: rtx tmp2 = *x;
1674: rtx tmp_dep, tmp2_dep;
1675: int tmp_class, tmp2_class;
1676: int value;
1677:
1678: /* Choose the instruction with the highest priority, if different. */
1679: if (value = INSN_PRIORITY (tmp) - INSN_PRIORITY (tmp2))
1680: return value;
1681:
1682: if (last_scheduled_insn)
1683: {
1684: /* Classify the instructions into three classes:
1685: 1) Data dependent on last schedule insn.
1686: 2) Anti/Output dependent on last scheduled insn.
1687: 3) Independent of last scheduled insn, or has latency of one.
1688: Choose the insn from the highest numbered class if different. */
1689: tmp_dep = find_insn_list (tmp, LOG_LINKS (last_scheduled_insn));
1690: if (tmp_dep == 0 || insn_cost (tmp) == 1)
1691: tmp_class = 3;
1692: else if (REG_NOTE_KIND (tmp_dep) == 0)
1693: tmp_class = 1;
1694: else
1695: tmp_class = 2;
1696:
1697: tmp2_dep = find_insn_list (tmp2, LOG_LINKS (last_scheduled_insn));
1698: if (tmp2_dep == 0 || insn_cost (tmp2) == 1)
1699: tmp2_class = 3;
1700: else if (REG_NOTE_KIND (tmp2_dep) == 0)
1701: tmp2_class = 1;
1702: else
1703: tmp2_class = 2;
1704:
1705: if (value = tmp_class - tmp2_class)
1706: return value;
1707: }
1708:
1709: /* If insns are equally good, sort by INSN_LUID (original insn order),
1710: so that we make the sort stable. This minimizes instruction movement,
1711: thus minimizing sched's effect on debugging and cross-jumping. */
1712: return INSN_LUID (tmp) - INSN_LUID (tmp2);
1713: }
1714:
1715: /* Resort the array A in which only element at index N may be out of order. */
1716:
1717: __inline static void
1718: swap_sort (a, n)
1719: rtx *a;
1720: int n;
1721: {
1722: rtx insn = a[n-1];
1723: int i = n-2;
1724:
1725: while (i >= 0 && rank_for_schedule (a+i, &insn) >= 0)
1726: {
1727: a[i+1] = a[i];
1728: i -= 1;
1729: }
1730: a[i+1] = insn;
1731: }
1732:
1733: static int max_priority;
1734:
1735: /* Add INSN to the insn queue so that it fires at least N_CYCLES
1736: before the currently executing insn. */
1737:
1738: __inline static void
1739: queue_insn (insn, n_cycles)
1740: rtx insn;
1741: int n_cycles;
1742: {
1743: int next_q = NEXT_Q_AFTER (q_ptr, n_cycles);
1744: NEXT_INSN (insn) = insn_queue[next_q];
1745: insn_queue[next_q] = insn;
1746: q_size += 1;
1747: }
1748:
1749: /* Return nonzero if PAT is the pattern of an insn which makes a
1750: register live. */
1751:
1752: __inline static int
1753: birthing_insn_p (pat)
1754: rtx pat;
1755: {
1756: int j;
1757:
1758: if (reload_completed == 1)
1759: return 0;
1760:
1761: if (GET_CODE (pat) == SET
1762: && GET_CODE (SET_DEST (pat)) == REG)
1763: {
1764: rtx dest = SET_DEST (pat);
1765: int i = REGNO (dest);
1766: int offset = i / REGSET_ELT_BITS;
1767: int bit = 1 << (i % REGSET_ELT_BITS);
1768:
1769: /* It would be more accurate to use refers_to_regno_p or
1770: reg_mentioned_p to determine when the dest is not live before this
1771: insn. */
1772:
1773: if (bb_live_regs[offset] & bit)
1774: return (reg_n_sets[i] == 1);
1775:
1776: return 0;
1777: }
1778: if (GET_CODE (pat) == PARALLEL)
1779: {
1780: for (j = 0; j < XVECLEN (pat, 0); j++)
1781: if (birthing_insn_p (XVECEXP (pat, 0, j)))
1782: return 1;
1783: }
1784: return 0;
1785: }
1786:
1787: /* If PREV is an insn which is immediately ready to execute, return 1,
1788: otherwise return 0. We may adjust its priority if that will help shorten
1789: register lifetimes. */
1790:
1791: static int
1792: launch_link (prev)
1793: rtx prev;
1794: {
1795: rtx pat = PATTERN (prev);
1796: rtx note;
1797: /* MAX of (a) number of cycles needed by prev
1798: (b) number of cycles before needed resources are free. */
1799: int n_cycles = insn_cost (prev);
1800: int n_deaths = 0;
1801:
1802: /* Trying to shorten register lives after reload has completed
1803: is useless and wrong. It gives inaccurate schedules. */
1804: if (reload_completed == 0)
1805: {
1806: for (note = REG_NOTES (prev); note; note = XEXP (note, 1))
1807: if (REG_NOTE_KIND (note) == REG_DEAD)
1808: n_deaths += 1;
1809:
1810: /* Defer scheduling insns which kill registers, since that
1811: shortens register lives. Prefer scheduling insns which
1812: make registers live for the same reason. */
1813: switch (n_deaths)
1814: {
1815: default:
1816: INSN_PRIORITY (prev) >>= 3;
1817: break;
1818: case 3:
1819: INSN_PRIORITY (prev) >>= 2;
1820: break;
1821: case 2:
1822: case 1:
1823: INSN_PRIORITY (prev) >>= 1;
1824: break;
1825: case 0:
1826: if (birthing_insn_p (pat))
1827: {
1828: int max = max_priority;
1829:
1830: if (max > INSN_PRIORITY (prev))
1831: INSN_PRIORITY (prev) = max;
1832: }
1833: break;
1834: }
1835: }
1836:
1837: if (n_cycles <= 1)
1838: return 1;
1839: queue_insn (prev, n_cycles);
1840: return 0;
1841: }
1842:
1843: /* INSN is the "currently executing insn". Launch each insn which was
1844: waiting on INSN (in the backwards dataflow sense). READY is a
1845: vector of insns which are ready to fire. N_READY is the number of
1846: elements in READY. */
1847:
1848: static int
1849: launch_links (insn, ready, n_ready)
1850: rtx insn;
1851: rtx *ready;
1852: int n_ready;
1853: {
1854: rtx link;
1855: int new_ready = n_ready;
1856:
1857: if (LOG_LINKS (insn) == 0)
1858: return n_ready;
1859:
1860: /* This is used by the function launch_link above. */
1861: if (n_ready > 0)
1862: max_priority = MAX (INSN_PRIORITY (ready[0]), INSN_PRIORITY (insn));
1863: else
1864: max_priority = INSN_PRIORITY (insn);
1865:
1866: for (link = LOG_LINKS (insn); link != 0; link = XEXP (link, 1))
1867: {
1868: rtx prev = XEXP (link, 0);
1869:
1870: if ((INSN_REF_COUNT (prev) -= 1) == 0 && launch_link (prev))
1871: ready[new_ready++] = prev;
1872: }
1873:
1874: return new_ready;
1875: }
1876:
1877: /* Add a REG_DEAD note for REG to INSN, reusing a REG_DEAD note from the
1878: dead_notes list. */
1879:
1880: static void
1881: create_reg_dead_note (reg, insn)
1882: rtx reg, insn;
1883: {
1884: rtx link = dead_notes;
1885:
1886: if (link == 0)
1887: /* In theory, we should not end up with more REG_DEAD reg notes than we
1888: started with. In practice, this can occur as the result of bugs in
1889: flow, combine and/or sched. */
1890: {
1891: #if 1
1892: abort ();
1893: #else
1894: link = rtx_alloc (EXPR_LIST);
1895: PUT_REG_NOTE_KIND (link, REG_DEAD);
1896: #endif
1897: }
1898: else
1899: dead_notes = XEXP (dead_notes, 1);
1900:
1901: XEXP (link, 0) = reg;
1902: XEXP (link, 1) = REG_NOTES (insn);
1903: REG_NOTES (insn) = link;
1904: }
1905:
1906: /* Subroutine on attach_deaths_insn--handles the recursive search
1907: through INSN. If SET_P is true, then x is being modified by the insn. */
1908:
1909: static void
1910: attach_deaths (x, insn, set_p)
1911: rtx x;
1912: rtx insn;
1913: int set_p;
1914: {
1915: register int i;
1916: register int j;
1917: register enum rtx_code code;
1918: register char *fmt;
1919:
1920: if (x == 0)
1921: return;
1922:
1923: code = GET_CODE (x);
1924:
1925: switch (code)
1926: {
1927: case CONST_INT:
1928: case CONST_DOUBLE:
1929: case LABEL_REF:
1930: case SYMBOL_REF:
1931: case CONST:
1932: case CODE_LABEL:
1933: case PC:
1934: case CC0:
1935: /* Get rid of the easy cases first. */
1936: return;
1937:
1938: case REG:
1939: {
1940: /* If the register dies in this insn, queue that note, and mark
1941: this register as needing to die. */
1942: /* This code is very similar to mark_used_1 (if set_p is false)
1943: and mark_set_1 (if set_p is true) in flow.c. */
1944:
1945: register int regno = REGNO (x);
1946: register int offset = regno / REGSET_ELT_BITS;
1947: register int bit = 1 << (regno % REGSET_ELT_BITS);
1948: int all_needed = (old_live_regs[offset] & bit);
1949: int some_needed = (old_live_regs[offset] & bit);
1950:
1951: if (set_p)
1952: return;
1953:
1954: if (regno < FIRST_PSEUDO_REGISTER)
1955: {
1956: int n;
1957:
1958: n = HARD_REGNO_NREGS (regno, GET_MODE (x));
1959: while (--n > 0)
1960: {
1961: some_needed |= (old_live_regs[(regno + n) / REGSET_ELT_BITS]
1962: & 1 << ((regno + n) % REGSET_ELT_BITS));
1963: all_needed &= (old_live_regs[(regno + n) / REGSET_ELT_BITS]
1964: & 1 << ((regno + n) % REGSET_ELT_BITS));
1965: }
1966: }
1967:
1968: /* If it wasn't live before we started, then add a REG_DEAD note.
1969: We must check the previous lifetime info not the current info,
1970: because we may have to execute this code several times, e.g.
1971: once for a clobber (which doesn't add a note) and later
1972: for a use (which does add a note).
1973:
1974: Always make the register live. We must do this even if it was
1975: live before, because this may be an insn which sets and uses
1976: the same register, in which case the register has already been
1977: killed, so we must make it live again.
1978:
1979: Global registers are always live, and should never have a REG_DEAD
1980: note added for them, so none of the code below applies to them. */
1981:
1982: if (regno >= FIRST_PSEUDO_REGISTER || ! global_regs[regno])
1983: {
1984: /* Never add REG_DEAD notes for the FRAME_POINTER_REGNUM or the
1985: STACK_POINTER_REGNUM, since these are always considered to be
1986: live. Similarly for ARG_POINTER_REGNUM if it is fixed. */
1987: if (regno != FRAME_POINTER_REGNUM
1988: #if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
1989: && ! (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
1990: #endif
1991: && regno != STACK_POINTER_REGNUM)
1992: {
1993: if (! all_needed && ! dead_or_set_p (insn, x))
1994: {
1995: /* If none of the words in X is needed, make a REG_DEAD
1996: note. Otherwise, we must make partial REG_DEAD
1997: notes. */
1998: if (! some_needed)
1999: create_reg_dead_note (x, insn);
2000: else
2001: {
2002: int i;
2003:
2004: /* Don't make a REG_DEAD note for a part of a
2005: register that is set in the insn. */
2006: for (i = HARD_REGNO_NREGS (regno, GET_MODE (x)) - 1;
2007: i >= 0; i--)
2008: if ((old_live_regs[(regno + i) / REGSET_ELT_BITS]
2009: & 1 << ((regno +i) % REGSET_ELT_BITS)) == 0
2010: && ! dead_or_set_regno_p (insn, regno + i))
2011: create_reg_dead_note (gen_rtx (REG, word_mode,
2012: regno + i),
2013: insn);
2014: }
2015: }
2016: }
2017:
2018: if (regno < FIRST_PSEUDO_REGISTER)
2019: {
2020: int j = HARD_REGNO_NREGS (regno, GET_MODE (x));
2021: while (--j >= 0)
2022: {
2023: offset = (regno + j) / REGSET_ELT_BITS;
2024: bit = 1 << ((regno + j) % REGSET_ELT_BITS);
2025:
2026: bb_dead_regs[offset] &= ~bit;
2027: bb_live_regs[offset] |= bit;
2028: }
2029: }
2030: else
2031: {
2032: bb_dead_regs[offset] &= ~bit;
2033: bb_live_regs[offset] |= bit;
2034: }
2035: }
2036: return;
2037: }
2038:
2039: case MEM:
2040: /* Handle tail-recursive case. */
2041: attach_deaths (XEXP (x, 0), insn, 0);
2042: return;
2043:
2044: case SUBREG:
2045: case STRICT_LOW_PART:
2046: /* These two cases preserve the value of SET_P, so handle them
2047: separately. */
2048: attach_deaths (XEXP (x, 0), insn, set_p);
2049: return;
2050:
2051: case ZERO_EXTRACT:
2052: case SIGN_EXTRACT:
2053: /* This case preserves the value of SET_P for the first operand, but
2054: clears it for the other two. */
2055: attach_deaths (XEXP (x, 0), insn, set_p);
2056: attach_deaths (XEXP (x, 1), insn, 0);
2057: attach_deaths (XEXP (x, 2), insn, 0);
2058: return;
2059:
2060: default:
2061: /* Other cases: walk the insn. */
2062: fmt = GET_RTX_FORMAT (code);
2063: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2064: {
2065: if (fmt[i] == 'e')
2066: attach_deaths (XEXP (x, i), insn, 0);
2067: else if (fmt[i] == 'E')
2068: for (j = 0; j < XVECLEN (x, i); j++)
2069: attach_deaths (XVECEXP (x, i, j), insn, 0);
2070: }
2071: }
2072: }
2073:
2074: /* After INSN has executed, add register death notes for each register
2075: that is dead after INSN. */
2076:
2077: static void
2078: attach_deaths_insn (insn)
2079: rtx insn;
2080: {
2081: rtx x = PATTERN (insn);
2082: register RTX_CODE code = GET_CODE (x);
2083:
2084: if (code == SET)
2085: {
2086: attach_deaths (SET_SRC (x), insn, 0);
2087:
2088: /* A register might die here even if it is the destination, e.g.
2089: it is the target of a volatile read and is otherwise unused.
2090: Hence we must always call attach_deaths for the SET_DEST. */
2091: attach_deaths (SET_DEST (x), insn, 1);
2092: }
2093: else if (code == PARALLEL)
2094: {
2095: register int i;
2096: for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
2097: {
2098: code = GET_CODE (XVECEXP (x, 0, i));
2099: if (code == SET)
2100: {
2101: attach_deaths (SET_SRC (XVECEXP (x, 0, i)), insn, 0);
2102:
2103: attach_deaths (SET_DEST (XVECEXP (x, 0, i)), insn, 1);
2104: }
2105: else if (code == CLOBBER)
2106: attach_deaths (XEXP (XVECEXP (x, 0, i), 0), insn, 1);
2107: else
2108: attach_deaths (XVECEXP (x, 0, i), insn, 0);
2109: }
2110: }
2111: else if (code == CLOBBER)
2112: attach_deaths (XEXP (x, 0), insn, 1);
2113: else
2114: attach_deaths (x, insn, 0);
2115: }
2116:
2117: /* Delete notes beginning with INSN and maybe put them in the chain
2118: of notes ended by NOTE_LIST.
2119: Returns the insn following the notes. */
2120:
2121: static rtx
2122: unlink_notes (insn, tail)
2123: rtx insn, tail;
2124: {
2125: rtx prev = PREV_INSN (insn);
2126:
2127: while (insn != tail && GET_CODE (insn) == NOTE)
2128: {
2129: rtx next = NEXT_INSN (insn);
2130: /* Delete the note from its current position. */
2131: if (prev)
2132: NEXT_INSN (prev) = next;
2133: if (next)
2134: PREV_INSN (next) = prev;
2135:
2136: if (write_symbols != NO_DEBUG && NOTE_LINE_NUMBER (insn) > 0)
2137: /* Record line-number notes so they can be reused. */
2138: LINE_NOTE (insn) = insn;
2139: else
2140: {
2141: /* Insert the note at the end of the notes list. */
2142: PREV_INSN (insn) = note_list;
2143: if (note_list)
2144: NEXT_INSN (note_list) = insn;
2145: note_list = insn;
2146: }
2147:
2148: insn = next;
2149: }
2150: return insn;
2151: }
2152:
2153: /* Data structure for keeping track of register information
2154: during that register's life. */
2155:
2156: struct sometimes
2157: {
2158: short offset; short bit;
2159: short live_length; short calls_crossed;
2160: };
2161:
2162: /* Constructor for `sometimes' data structure. */
2163:
2164: static int
2165: new_sometimes_live (regs_sometimes_live, offset, bit, sometimes_max)
2166: struct sometimes *regs_sometimes_live;
2167: int offset, bit;
2168: int sometimes_max;
2169: {
2170: register struct sometimes *p;
2171: register int regno = offset * REGSET_ELT_BITS + bit;
2172: int i;
2173:
2174: /* There should never be a register greater than max_regno here. If there
2175: is, it means that a define_split has created a new pseudo reg. This
2176: is not allowed, since there will not be flow info available for any
2177: new register, so catch the error here. */
2178: if (regno >= max_regno)
2179: abort ();
2180:
2181: p = ®s_sometimes_live[sometimes_max];
2182: p->offset = offset;
2183: p->bit = bit;
2184: p->live_length = 0;
2185: p->calls_crossed = 0;
2186: sometimes_max++;
2187: return sometimes_max;
2188: }
2189:
2190: /* Count lengths of all regs we are currently tracking,
2191: and find new registers no longer live. */
2192:
2193: static void
2194: finish_sometimes_live (regs_sometimes_live, sometimes_max)
2195: struct sometimes *regs_sometimes_live;
2196: int sometimes_max;
2197: {
2198: int i;
2199:
2200: for (i = 0; i < sometimes_max; i++)
2201: {
2202: register struct sometimes *p = ®s_sometimes_live[i];
2203: int regno;
2204:
2205: regno = p->offset * REGSET_ELT_BITS + p->bit;
2206:
2207: sched_reg_live_length[regno] += p->live_length;
2208: sched_reg_n_calls_crossed[regno] += p->calls_crossed;
2209: }
2210: }
2211:
2212: /* Use modified list scheduling to rearrange insns in basic block
2213: B. FILE, if nonzero, is where we dump interesting output about
2214: this pass. */
2215:
2216: static void
2217: schedule_block (b, file)
2218: int b;
2219: FILE *file;
2220: {
2221: rtx insn, last;
2222: rtx last_note = 0;
2223: rtx *ready, link;
2224: int i, j, n_ready = 0, new_ready, n_insns = 0;
2225: int sched_n_insns = 0;
2226: #define NEED_NOTHING 0
2227: #define NEED_HEAD 1
2228: #define NEED_TAIL 2
2229: int new_needs;
2230:
2231: /* HEAD and TAIL delimit the region being scheduled. */
2232: rtx head = basic_block_head[b];
2233: rtx tail = basic_block_end[b];
2234: /* PREV_HEAD and NEXT_TAIL are the boundaries of the insns
2235: being scheduled. When the insns have been ordered,
2236: these insns delimit where the new insns are to be
2237: spliced back into the insn chain. */
2238: rtx next_tail;
2239: rtx prev_head;
2240:
2241: /* Keep life information accurate. */
2242: register struct sometimes *regs_sometimes_live;
2243: int sometimes_max;
2244:
2245: if (file)
2246: fprintf (file, ";;\t -- basic block number %d from %d to %d --\n",
2247: b, INSN_UID (basic_block_head[b]), INSN_UID (basic_block_end[b]));
2248:
2249: i = max_reg_num ();
2250: reg_last_uses = (rtx *) alloca (i * sizeof (rtx));
2251: bzero (reg_last_uses, i * sizeof (rtx));
2252: reg_last_sets = (rtx *) alloca (i * sizeof (rtx));
2253: bzero (reg_last_sets, i * sizeof (rtx));
2254:
2255: /* Remove certain insns at the beginning from scheduling,
2256: by advancing HEAD. */
2257:
2258: /* At the start of a function, before reload has run, don't delay getting
2259: parameters from hard registers into pseudo registers. */
2260: if (reload_completed == 0 && b == 0)
2261: {
2262: while (head != tail
2263: && GET_CODE (head) == NOTE
2264: && NOTE_LINE_NUMBER (head) != NOTE_INSN_FUNCTION_BEG)
2265: head = NEXT_INSN (head);
2266: while (head != tail
2267: && GET_CODE (head) == INSN
2268: && GET_CODE (PATTERN (head)) == SET)
2269: {
2270: rtx src = SET_SRC (PATTERN (head));
2271: while (GET_CODE (src) == SUBREG
2272: || GET_CODE (src) == SIGN_EXTEND
2273: || GET_CODE (src) == ZERO_EXTEND
2274: || GET_CODE (src) == SIGN_EXTRACT
2275: || GET_CODE (src) == ZERO_EXTRACT)
2276: src = XEXP (src, 0);
2277: if (GET_CODE (src) != REG
2278: || REGNO (src) >= FIRST_PSEUDO_REGISTER)
2279: break;
2280: /* Keep this insn from ever being scheduled. */
2281: INSN_REF_COUNT (head) = 1;
2282: head = NEXT_INSN (head);
2283: }
2284: }
2285:
2286: /* Don't include any notes or labels at the beginning of the
2287: basic block, or notes at the ends of basic blocks. */
2288: while (head != tail)
2289: {
2290: if (GET_CODE (head) == NOTE)
2291: head = NEXT_INSN (head);
2292: else if (GET_CODE (tail) == NOTE)
2293: tail = PREV_INSN (tail);
2294: else if (GET_CODE (head) == CODE_LABEL)
2295: head = NEXT_INSN (head);
2296: else break;
2297: }
2298: /* If the only insn left is a NOTE or a CODE_LABEL, then there is no need
2299: to schedule this block. */
2300: if (head == tail
2301: && (GET_CODE (head) == NOTE || GET_CODE (head) == CODE_LABEL))
2302: return;
2303:
2304: #if 0
2305: /* This short-cut doesn't work. It does not count call insns crossed by
2306: registers in reg_sometimes_live. It does not mark these registers as
2307: dead if they die in this block. It does not mark these registers live
2308: (or create new reg_sometimes_live entries if necessary) if they are born
2309: in this block.
2310:
2311: The easy solution is to just always schedule a block. This block only
2312: has one insn, so this won't slow down this pass by much. */
2313:
2314: if (head == tail)
2315: return;
2316: #endif
2317:
2318: /* Exclude certain insns at the end of the basic block by advancing TAIL. */
2319: /* This isn't correct. Instead of advancing TAIL, should assign very
2320: high priorities to these insns to guarantee that they get scheduled last.
2321: If these insns are ignored, as is currently done, the register life info
2322: may be incorrectly computed. */
2323: if (GET_CODE (tail) == INSN
2324: && GET_CODE (PATTERN (tail)) == USE
2325: && next_nonnote_insn (tail) == 0)
2326: {
2327: /* If this was the only insn in the block, then there are no insns to
2328: schedule. */
2329: if (head == tail)
2330: return;
2331:
2332: /* We don't try to reorder the USE at the end of a function. */
2333: tail = prev_nonnote_insn (tail);
2334:
2335: #if 0
2336: /* This short-cut does not work. See comment above. */
2337: if (head == tail)
2338: return;
2339: #endif
2340: }
2341: else if (GET_CODE (tail) == JUMP_INSN
2342: && SCHED_GROUP_P (tail) == 0
2343: && GET_CODE (PREV_INSN (tail)) == INSN
2344: && GET_CODE (PATTERN (PREV_INSN (tail))) == USE
2345: && REG_FUNCTION_VALUE_P (XEXP (PATTERN (PREV_INSN (tail)), 0)))
2346: {
2347: /* Don't let the setting of the function's return value register
2348: move from this jump. For the same reason we want to get the
2349: parameters into pseudo registers as quickly as possible, we
2350: want to set the function's return value register as late as
2351: possible. */
2352:
2353: /* If this is the only insn in the block, then there is no need to
2354: schedule the block. */
2355: if (head == tail)
2356: return;
2357:
2358: tail = PREV_INSN (tail);
2359: if (head == tail)
2360: return;
2361:
2362: tail = prev_nonnote_insn (tail);
2363:
2364: #if 0
2365: /* This shortcut does not work. See comment above. */
2366: if (head == tail)
2367: return;
2368: #endif
2369: }
2370:
2371: #ifdef HAVE_cc0
2372: /* This is probably wrong. Instead of doing this, should give this insn
2373: a very high priority to guarantee that it gets scheduled last. */
2374: /* Can not separate an insn that sets the condition code from one that
2375: uses it. So we must leave an insn that sets cc0 where it is. */
2376: if (sets_cc0_p (PATTERN (tail)))
2377: tail = PREV_INSN (tail);
2378: #endif
2379:
2380: /* Now HEAD through TAIL are the insns actually to be rearranged;
2381: Let PREV_HEAD and NEXT_TAIL enclose them. */
2382: prev_head = PREV_INSN (head);
2383: next_tail = NEXT_INSN (tail);
2384:
2385: /* Initialize basic block data structures. */
2386: dead_notes = 0;
2387: pending_read_insns = 0;
2388: pending_read_mems = 0;
2389: pending_write_insns = 0;
2390: pending_write_mems = 0;
2391: pending_lists_length = 0;
2392: last_pending_memory_flush = 0;
2393: last_function_call = 0;
2394: last_scheduled_insn = 0;
2395:
2396: LOG_LINKS (sched_before_next_call) = 0;
2397:
2398: n_insns += sched_analyze (head, tail);
2399: if (n_insns == 0)
2400: {
2401: free_pending_lists ();
2402: return;
2403: }
2404:
2405: /* Allocate vector to hold insns to be rearranged (except those
2406: insns which are controlled by an insn with SCHED_GROUP_P set).
2407: All these insns are included between ORIG_HEAD and ORIG_TAIL,
2408: as those variables ultimately are set up. */
2409: ready = (rtx *) alloca ((n_insns+1) * sizeof (rtx));
2410:
2411: /* TAIL is now the last of the insns to be rearranged.
2412: Put those insns into the READY vector. */
2413: insn = tail;
2414:
2415: /* If the last insn is a branch, force it to be the last insn after
2416: scheduling. Also, don't try to reorder calls at the ends the basic
2417: block -- this will only lead to worse register allocation. */
2418: if (GET_CODE (tail) == CALL_INSN || GET_CODE (tail) == JUMP_INSN)
2419: {
2420: priority (tail);
2421: ready[n_ready++] = tail;
2422: INSN_PRIORITY (tail) = TAIL_PRIORITY;
2423: INSN_REF_COUNT (tail) = 0;
2424: insn = PREV_INSN (tail);
2425: }
2426:
2427: /* Assign priorities to instructions. Also check whether they
2428: are in priority order already. If so then I will be nonnegative.
2429: We use this shortcut only before reloading. */
2430: #if 0
2431: i = reload_completed ? DONE_PRIORITY : MAX_PRIORITY;
2432: #endif
2433:
2434: for (; insn != prev_head; insn = PREV_INSN (insn))
2435: {
2436: if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
2437: {
2438: priority (insn);
2439: if (INSN_REF_COUNT (insn) == 0)
2440: ready[n_ready++] = insn;
2441: if (SCHED_GROUP_P (insn))
2442: {
2443: while (SCHED_GROUP_P (insn))
2444: {
2445: insn = PREV_INSN (insn);
2446: while (GET_CODE (insn) == NOTE)
2447: insn = PREV_INSN (insn);
2448: priority (insn);
2449: }
2450: continue;
2451: }
2452: #if 0
2453: if (i < 0)
2454: continue;
2455: if (INSN_PRIORITY (insn) < i)
2456: i = INSN_PRIORITY (insn);
2457: else if (INSN_PRIORITY (insn) > i)
2458: i = DONE_PRIORITY;
2459: #endif
2460: }
2461: }
2462:
2463: #if 0
2464: /* This short-cut doesn't work. It does not count call insns crossed by
2465: registers in reg_sometimes_live. It does not mark these registers as
2466: dead if they die in this block. It does not mark these registers live
2467: (or create new reg_sometimes_live entries if necessary) if they are born
2468: in this block.
2469:
2470: The easy solution is to just always schedule a block. These blocks tend
2471: to be very short, so this doesn't slow down this pass by much. */
2472:
2473: /* If existing order is good, don't bother to reorder. */
2474: if (i != DONE_PRIORITY)
2475: {
2476: if (file)
2477: fprintf (file, ";; already scheduled\n");
2478:
2479: if (reload_completed == 0)
2480: {
2481: for (i = 0; i < sometimes_max; i++)
2482: regs_sometimes_live[i].live_length += n_insns;
2483:
2484: finish_sometimes_live (regs_sometimes_live, sometimes_max);
2485: }
2486: free_pending_lists ();
2487: return;
2488: }
2489: #endif
2490:
2491: /* Scan all the insns to be scheduled, removing NOTE insns
2492: and register death notes.
2493: Line number NOTE insns end up in NOTE_LIST.
2494: Register death notes end up in DEAD_NOTES.
2495:
2496: Recreate the register life information for the end of this basic
2497: block. */
2498:
2499: if (reload_completed == 0)
2500: {
2501: bcopy (basic_block_live_at_start[b], bb_live_regs, regset_bytes);
2502: bzero (bb_dead_regs, regset_bytes);
2503:
2504: if (b == 0)
2505: {
2506: /* This is the first block in the function. There may be insns
2507: before head that we can't schedule. We still need to examine
2508: them though for accurate register lifetime analysis. */
2509:
2510: /* We don't want to remove any REG_DEAD notes as the code below
2511: does. */
2512:
2513: for (insn = basic_block_head[b]; insn != head;
2514: insn = NEXT_INSN (insn))
2515: if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
2516: {
2517: /* See if the register gets born here. */
2518: /* We must check for registers being born before we check for
2519: registers dying. It is possible for a register to be born
2520: and die in the same insn, e.g. reading from a volatile
2521: memory location into an otherwise unused register. Such
2522: a register must be marked as dead after this insn. */
2523: if (GET_CODE (PATTERN (insn)) == SET
2524: || GET_CODE (PATTERN (insn)) == CLOBBER)
2525: sched_note_set (b, PATTERN (insn), 0);
2526: else if (GET_CODE (PATTERN (insn)) == PARALLEL)
2527: {
2528: int j;
2529: for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
2530: if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
2531: || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
2532: sched_note_set (b, XVECEXP (PATTERN (insn), 0, j), 0);
2533:
2534: /* ??? This code is obsolete and should be deleted. It
2535: is harmless though, so we will leave it in for now. */
2536: for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
2537: if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == USE)
2538: sched_note_set (b, XVECEXP (PATTERN (insn), 0, j), 0);
2539: }
2540:
2541: for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2542: {
2543: if ((REG_NOTE_KIND (link) == REG_DEAD
2544: || REG_NOTE_KIND (link) == REG_UNUSED)
2545: /* Verify that the REG_NOTE has a legal value. */
2546: && GET_CODE (XEXP (link, 0)) == REG)
2547: {
2548: register int regno = REGNO (XEXP (link, 0));
2549: register int offset = regno / REGSET_ELT_BITS;
2550: register int bit = 1 << (regno % REGSET_ELT_BITS);
2551:
2552: if (regno < FIRST_PSEUDO_REGISTER)
2553: {
2554: int j = HARD_REGNO_NREGS (regno,
2555: GET_MODE (XEXP (link, 0)));
2556: while (--j >= 0)
2557: {
2558: offset = (regno + j) / REGSET_ELT_BITS;
2559: bit = 1 << ((regno + j) % REGSET_ELT_BITS);
2560:
2561: bb_live_regs[offset] &= ~bit;
2562: bb_dead_regs[offset] |= bit;
2563: }
2564: }
2565: else
2566: {
2567: bb_live_regs[offset] &= ~bit;
2568: bb_dead_regs[offset] |= bit;
2569: }
2570: }
2571: }
2572: }
2573: }
2574: }
2575:
2576: /* If debugging information is being produced, keep track of the line
2577: number notes for each insn. */
2578: if (write_symbols != NO_DEBUG)
2579: {
2580: /* We must use the true line number for the first insn in the block
2581: that was computed and saved at the start of this pass. We can't
2582: use the current line number, because scheduling of the previous
2583: block may have changed the current line number. */
2584: rtx line = line_note_head[b];
2585:
2586: for (insn = basic_block_head[b];
2587: insn != next_tail;
2588: insn = NEXT_INSN (insn))
2589: if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
2590: line = insn;
2591: else
2592: LINE_NOTE (insn) = line;
2593: }
2594:
2595: for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
2596: {
2597: rtx prev, next, link;
2598:
2599: /* Farm out notes. This is needed to keep the debugger from
2600: getting completely deranged. */
2601: if (GET_CODE (insn) == NOTE)
2602: {
2603: prev = insn;
2604: insn = unlink_notes (insn, next_tail);
2605: if (prev == tail)
2606: abort ();
2607: if (prev == head)
2608: abort ();
2609: if (insn == next_tail)
2610: abort ();
2611: }
2612:
2613: if (reload_completed == 0
2614: && GET_RTX_CLASS (GET_CODE (insn)) == 'i')
2615: {
2616: /* See if the register gets born here. */
2617: /* We must check for registers being born before we check for
2618: registers dying. It is possible for a register to be born and
2619: die in the same insn, e.g. reading from a volatile memory
2620: location into an otherwise unused register. Such a register
2621: must be marked as dead after this insn. */
2622: if (GET_CODE (PATTERN (insn)) == SET
2623: || GET_CODE (PATTERN (insn)) == CLOBBER)
2624: sched_note_set (b, PATTERN (insn), 0);
2625: else if (GET_CODE (PATTERN (insn)) == PARALLEL)
2626: {
2627: int j;
2628: for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
2629: if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
2630: || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
2631: sched_note_set (b, XVECEXP (PATTERN (insn), 0, j), 0);
2632:
2633: /* ??? This code is obsolete and should be deleted. It
2634: is harmless though, so we will leave it in for now. */
2635: for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
2636: if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == USE)
2637: sched_note_set (b, XVECEXP (PATTERN (insn), 0, j), 0);
2638: }
2639:
2640: /* Need to know what registers this insn kills. */
2641: for (prev = 0, link = REG_NOTES (insn); link; link = next)
2642: {
2643: int regno;
2644:
2645: next = XEXP (link, 1);
2646: if ((REG_NOTE_KIND (link) == REG_DEAD
2647: || REG_NOTE_KIND (link) == REG_UNUSED)
2648: /* Verify that the REG_NOTE has a legal value. */
2649: && GET_CODE (XEXP (link, 0)) == REG)
2650: {
2651: register int regno = REGNO (XEXP (link, 0));
2652: register int offset = regno / REGSET_ELT_BITS;
2653: register int bit = 1 << (regno % REGSET_ELT_BITS);
2654:
2655: /* Only unlink REG_DEAD notes; leave REG_UNUSED notes
2656: alone. */
2657: if (REG_NOTE_KIND (link) == REG_DEAD)
2658: {
2659: if (prev)
2660: XEXP (prev, 1) = next;
2661: else
2662: REG_NOTES (insn) = next;
2663: XEXP (link, 1) = dead_notes;
2664: dead_notes = link;
2665: }
2666: else
2667: prev = link;
2668:
2669: if (regno < FIRST_PSEUDO_REGISTER)
2670: {
2671: int j = HARD_REGNO_NREGS (regno,
2672: GET_MODE (XEXP (link, 0)));
2673: while (--j >= 0)
2674: {
2675: offset = (regno + j) / REGSET_ELT_BITS;
2676: bit = 1 << ((regno + j) % REGSET_ELT_BITS);
2677:
2678: bb_live_regs[offset] &= ~bit;
2679: bb_dead_regs[offset] |= bit;
2680: }
2681: }
2682: else
2683: {
2684: bb_live_regs[offset] &= ~bit;
2685: bb_dead_regs[offset] |= bit;
2686: }
2687: }
2688: else
2689: prev = link;
2690: }
2691: }
2692: }
2693:
2694: if (reload_completed == 0)
2695: {
2696: /* Keep track of register lives. */
2697: old_live_regs = (regset) alloca (regset_bytes);
2698: regs_sometimes_live
2699: = (struct sometimes *) alloca (max_regno * sizeof (struct sometimes));
2700: sometimes_max = 0;
2701:
2702: /* Start with registers live at end. */
2703: for (j = 0; j < regset_size; j++)
2704: {
2705: int live = bb_live_regs[j];
2706: old_live_regs[j] = live;
2707: if (live)
2708: {
2709: register int bit;
2710: for (bit = 0; bit < REGSET_ELT_BITS; bit++)
2711: if (live & (1 << bit))
2712: sometimes_max = new_sometimes_live (regs_sometimes_live, j,
2713: bit, sometimes_max);
2714: }
2715: }
2716: }
2717:
2718: SCHED_SORT (ready, n_ready, 1);
2719:
2720: if (file)
2721: {
2722: fprintf (file, ";; ready list initially:\n;; ");
2723: for (i = 0; i < n_ready; i++)
2724: fprintf (file, "%d ", INSN_UID (ready[i]));
2725: fprintf (file, "\n\n");
2726:
2727: for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
2728: if (INSN_PRIORITY (insn) > 0)
2729: fprintf (file, ";; insn[%4d]: priority = %4d, ref_count = %4d\n",
2730: INSN_UID (insn), INSN_PRIORITY (insn),
2731: INSN_REF_COUNT (insn));
2732: }
2733:
2734: /* Now HEAD and TAIL are going to become disconnected
2735: entirely from the insn chain. */
2736: tail = ready[0];
2737:
2738: /* Q_SIZE will always be zero here. */
2739: q_ptr = 0;
2740: bzero (insn_queue, sizeof (insn_queue));
2741:
2742: /* Now, perform list scheduling. */
2743:
2744: /* Where we start inserting insns is after TAIL. */
2745: last = next_tail;
2746:
2747: new_needs = (NEXT_INSN (prev_head) == basic_block_head[b]
2748: ? NEED_HEAD : NEED_NOTHING);
2749: if (PREV_INSN (next_tail) == basic_block_end[b])
2750: new_needs |= NEED_TAIL;
2751:
2752: new_ready = n_ready;
2753: while (sched_n_insns < n_insns)
2754: {
2755: q_ptr = NEXT_Q (q_ptr);
2756:
2757: /* Add all pending insns that can be scheduled without stalls to the
2758: ready list. */
2759: for (insn = insn_queue[q_ptr]; insn; insn = NEXT_INSN (insn))
2760: {
2761: if (file)
2762: fprintf (file, ";; launching %d before %d with no stalls\n",
2763: INSN_UID (insn), INSN_UID (last));
2764: ready[new_ready++] = insn;
2765: q_size -= 1;
2766: }
2767: insn_queue[q_ptr] = 0;
2768:
2769: /* If there are no ready insns, stall until one is ready and add all
2770: of the pending insns at that point to the ready list. */
2771: if (new_ready == 0)
2772: {
2773: register int stalls;
2774:
2775: for (stalls = 1; stalls < Q_SIZE; stalls++)
2776: if (insn = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)])
2777: {
2778: for (; insn; insn = NEXT_INSN (insn))
2779: {
2780: if (file)
2781: fprintf (file, ";; issue insn %d before %d with %d stalls\n",
2782: INSN_UID (insn), INSN_UID (last), stalls);
2783: ready[new_ready++] = insn;
2784: q_size -= 1;
2785: }
2786: insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = 0;
2787: break;
2788: }
2789:
2790: #if 0
2791: /* This looks logically correct, but on the SPEC benchmark set on
2792: the SPARC, I get better code without it. */
2793: q_ptr = NEXT_Q_AFTER (q_ptr, stalls);
2794: #endif
2795: }
2796:
2797: /* There should be some instructions waiting to fire. */
2798: if (new_ready == 0)
2799: abort ();
2800:
2801: /* Sort the ready list and choose the best insn to schedule.
2802: N_READY holds the number of items that were scheduled the last time,
2803: minus the one instruction scheduled on the last loop iteration; it
2804: is not modified for any other reason in this loop. */
2805: SCHED_SORT (ready, new_ready, n_ready);
2806: n_ready = new_ready;
2807: last_scheduled_insn = insn = ready[0];
2808:
2809: if (DONE_PRIORITY_P (insn))
2810: abort ();
2811:
2812: if (reload_completed == 0)
2813: {
2814: /* Process this insn, and each insn linked to this one which must
2815: be immediately output after this insn. */
2816: do
2817: {
2818: /* First we kill registers set by this insn, and then we
2819: make registers used by this insn live. This is the opposite
2820: order used above because we are traversing the instructions
2821: backwards. */
2822:
2823: /* Strictly speaking, we should scan REG_UNUSED notes and make
2824: every register mentioned there live, however, we will just
2825: kill them again immediately below, so there doesn't seem to
2826: be any reason why we bother to do this. */
2827:
2828: /* See if this is the last notice we must take of a register. */
2829: if (GET_CODE (PATTERN (insn)) == SET
2830: || GET_CODE (PATTERN (insn)) == CLOBBER)
2831: sched_note_set (b, PATTERN (insn), 1);
2832: else if (GET_CODE (PATTERN (insn)) == PARALLEL)
2833: {
2834: int j;
2835: for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
2836: if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
2837: || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
2838: sched_note_set (b, XVECEXP (PATTERN (insn), 0, j), 1);
2839: }
2840:
2841: /* This code keeps life analysis information up to date. */
2842: if (GET_CODE (insn) == CALL_INSN)
2843: {
2844: register struct sometimes *p;
2845:
2846: /* A call kills all call used and global registers, except
2847: for those mentioned in the call pattern which will be
2848: made live again later. */
2849: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2850: if (call_used_regs[i] || global_regs[i])
2851: {
2852: register int offset = i / REGSET_ELT_BITS;
2853: register int bit = 1 << (i % REGSET_ELT_BITS);
2854:
2855: bb_live_regs[offset] &= ~bit;
2856: bb_dead_regs[offset] |= bit;
2857: }
2858:
2859: /* Regs live at the time of a call instruction must not
2860: go in a register clobbered by calls. Record this for
2861: all regs now live. Note that insns which are born or
2862: die in a call do not cross a call, so this must be done
2863: after the killings (above) and before the births
2864: (below). */
2865: p = regs_sometimes_live;
2866: for (i = 0; i < sometimes_max; i++, p++)
2867: if (bb_live_regs[p->offset] & (1 << p->bit))
2868: p->calls_crossed += 1;
2869: }
2870:
2871: /* Make every register used live, and add REG_DEAD notes for
2872: registers which were not live before we started. */
2873: attach_deaths_insn (insn);
2874:
2875: /* Find registers now made live by that instruction. */
2876: for (i = 0; i < regset_size; i++)
2877: {
2878: int diff = bb_live_regs[i] & ~old_live_regs[i];
2879: if (diff)
2880: {
2881: register int bit;
2882: old_live_regs[i] |= diff;
2883: for (bit = 0; bit < REGSET_ELT_BITS; bit++)
2884: if (diff & (1 << bit))
2885: sometimes_max
2886: = new_sometimes_live (regs_sometimes_live, i, bit,
2887: sometimes_max);
2888: }
2889: }
2890:
2891: /* Count lengths of all regs we are worrying about now,
2892: and handle registers no longer live. */
2893:
2894: for (i = 0; i < sometimes_max; i++)
2895: {
2896: register struct sometimes *p = ®s_sometimes_live[i];
2897: int regno = p->offset*REGSET_ELT_BITS + p->bit;
2898:
2899: p->live_length += 1;
2900:
2901: if ((bb_live_regs[p->offset] & (1 << p->bit)) == 0)
2902: {
2903: /* This is the end of one of this register's lifetime
2904: segments. Save the lifetime info collected so far,
2905: and clear its bit in the old_live_regs entry. */
2906: sched_reg_live_length[regno] += p->live_length;
2907: sched_reg_n_calls_crossed[regno] += p->calls_crossed;
2908: old_live_regs[p->offset] &= ~(1 << p->bit);
2909:
2910: /* Delete the reg_sometimes_live entry for this reg by
2911: copying the last entry over top of it. */
2912: *p = regs_sometimes_live[--sometimes_max];
2913: /* ...and decrement i so that this newly copied entry
2914: will be processed. */
2915: i--;
2916: }
2917: }
2918:
2919: link = insn;
2920: insn = PREV_INSN (insn);
2921: }
2922: while (SCHED_GROUP_P (link));
2923:
2924: /* Set INSN back to the insn we are scheduling now. */
2925: insn = ready[0];
2926: }
2927:
2928: /* Schedule INSN. Remove it from the ready list. */
2929: ready += 1;
2930: n_ready -= 1;
2931:
2932: sched_n_insns += 1;
2933: NEXT_INSN (insn) = last;
2934: PREV_INSN (last) = insn;
2935: last = insn;
2936:
2937: /* Everything that precedes INSN now either becomes "ready", if
2938: it can execute immediately before INSN, or "pending", if
2939: there must be a delay. Give INSN high enough priority that
2940: at least one (maybe more) reg-killing insns can be launched
2941: ahead of all others. Mark INSN as scheduled by changing its
2942: priority to -1. */
2943: INSN_PRIORITY (insn) = LAUNCH_PRIORITY;
2944: new_ready = launch_links (insn, ready, n_ready);
2945: INSN_PRIORITY (insn) = DONE_PRIORITY;
2946:
2947: /* Schedule all prior insns that must not be moved. */
2948: if (SCHED_GROUP_P (insn))
2949: {
2950: /* Disable these insns from being launched. */
2951: link = insn;
2952: while (SCHED_GROUP_P (link))
2953: {
2954: /* Disable these insns from being launched by anybody. */
2955: link = PREV_INSN (link);
2956: INSN_REF_COUNT (link) = 0;
2957: }
2958:
2959: /* None of these insns can move forward into delay slots. */
2960: while (SCHED_GROUP_P (insn))
2961: {
2962: insn = PREV_INSN (insn);
2963: new_ready = launch_links (insn, ready, new_ready);
2964: INSN_PRIORITY (insn) = DONE_PRIORITY;
2965:
2966: sched_n_insns += 1;
2967: NEXT_INSN (insn) = last;
2968: PREV_INSN (last) = insn;
2969: last = insn;
2970: }
2971: }
2972: }
2973: if (q_size != 0)
2974: abort ();
2975:
2976: if (reload_completed == 0)
2977: finish_sometimes_live (regs_sometimes_live, sometimes_max);
2978:
2979: /* HEAD is now the first insn in the chain of insns that
2980: been scheduled by the loop above.
2981: TAIL is the last of those insns. */
2982: head = insn;
2983:
2984: /* NOTE_LIST is the end of a chain of notes previously found
2985: among the insns. Insert them at the beginning of the insns. */
2986: if (note_list != 0)
2987: {
2988: rtx note_head = note_list;
2989: while (PREV_INSN (note_head))
2990: note_head = PREV_INSN (note_head);
2991:
2992: PREV_INSN (head) = note_list;
2993: NEXT_INSN (note_list) = head;
2994: head = note_head;
2995: }
2996:
2997: /* In theory, there should be no REG_DEAD notes leftover at the end.
2998: In practice, this can occur as the result of bugs in flow, combine.c,
2999: and/or sched.c. The values of the REG_DEAD notes remaining are
3000: meaningless, because dead_notes is just used as a free list. */
3001: #if 1
3002: if (dead_notes != 0)
3003: abort ();
3004: #endif
3005:
3006: if (new_needs & NEED_HEAD)
3007: basic_block_head[b] = head;
3008: PREV_INSN (head) = prev_head;
3009: NEXT_INSN (prev_head) = head;
3010:
3011: if (new_needs & NEED_TAIL)
3012: basic_block_end[b] = tail;
3013: NEXT_INSN (tail) = next_tail;
3014: PREV_INSN (next_tail) = tail;
3015:
3016: /* Restore the line-number notes of each insn. */
3017: if (write_symbols != NO_DEBUG)
3018: {
3019: rtx line, note, prev, new;
3020: int notes = 0;
3021:
3022: head = basic_block_head[b];
3023: next_tail = NEXT_INSN (basic_block_end[b]);
3024:
3025: /* Determine the current line-number. We want to know the current
3026: line number of the first insn of the block here, in case it is
3027: different from the true line number that was saved earlier. If
3028: different, then we need a line number note before the first insn
3029: of this block. If it happens to be the same, then we don't want to
3030: emit another line number note here. */
3031: for (line = head; line; line = PREV_INSN (line))
3032: if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
3033: break;
3034:
3035: /* Walk the insns keeping track of the current line-number and inserting
3036: the line-number notes as needed. */
3037: for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
3038: if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
3039: line = insn;
3040: else if (! (GET_CODE (insn) == NOTE
3041: && NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED)
3042: && (note = LINE_NOTE (insn)) != 0
3043: && note != line
3044: && (line == 0
3045: || NOTE_LINE_NUMBER (note) != NOTE_LINE_NUMBER (line)
3046: || NOTE_SOURCE_FILE (note) != NOTE_SOURCE_FILE (line)))
3047: {
3048: line = note;
3049: prev = PREV_INSN (insn);
3050: if (LINE_NOTE (note))
3051: {
3052: /* Re-use the orignal line-number note. */
3053: LINE_NOTE (note) = 0;
3054: PREV_INSN (note) = prev;
3055: NEXT_INSN (prev) = note;
3056: PREV_INSN (insn) = note;
3057: NEXT_INSN (note) = insn;
3058: }
3059: else
3060: {
3061: notes++;
3062: new = emit_note_after (NOTE_LINE_NUMBER (note), prev);
3063: NOTE_SOURCE_FILE (new) = NOTE_SOURCE_FILE (note);
3064: }
3065: }
3066: if (file && notes)
3067: fprintf (file, ";; added %d line-number notes\n", notes);
3068: }
3069:
3070: if (file)
3071: {
3072: fprintf (file, ";; new basic block head = %d\n;; new basic block end = %d\n\n",
3073: INSN_UID (basic_block_head[b]), INSN_UID (basic_block_end[b]));
3074: }
3075:
3076: /* Yow! We're done! */
3077: free_pending_lists ();
3078:
3079: return;
3080: }
3081:
3082: /* Subroutine of split_hard_reg_notes. Searches X for any reference to
3083: REGNO, returning the rtx of the reference found if any. Otherwise,
3084: returns 0. */
3085:
3086: rtx
3087: regno_use_in (regno, x)
3088: int regno;
3089: rtx x;
3090: {
3091: register char *fmt;
3092: int i, j;
3093: rtx tem;
3094:
3095: if (GET_CODE (x) == REG && REGNO (x) == regno)
3096: return x;
3097:
3098: fmt = GET_RTX_FORMAT (GET_CODE (x));
3099: for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
3100: {
3101: if (fmt[i] == 'e')
3102: {
3103: if (tem = regno_use_in (regno, XEXP (x, i)))
3104: return tem;
3105: }
3106: else if (fmt[i] == 'E')
3107: for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3108: if (tem = regno_use_in (regno , XVECEXP (x, i, j)))
3109: return tem;
3110: }
3111:
3112: return 0;
3113: }
3114:
3115: /* Subroutine of update_flow_info. Determines whether any new REG_NOTEs are
3116: needed for the hard register mentioned in the note. This can happen
3117: if the reference to the hard register in the original insn was split into
3118: several smaller hard register references in the split insns. */
3119:
3120: static void
3121: split_hard_reg_notes (note, first, last, orig_insn)
3122: rtx note, first, last, orig_insn;
3123: {
3124: rtx reg, temp, link;
3125: int n_regs, i, new_reg;
3126: rtx insn;
3127:
3128: /* Assume that this is a REG_DEAD note. */
3129: if (REG_NOTE_KIND (note) != REG_DEAD)
3130: abort ();
3131:
3132: reg = XEXP (note, 0);
3133:
3134: n_regs = HARD_REGNO_NREGS (REGNO (reg), GET_MODE (reg));
3135:
3136: /* ??? Could add check here to see whether, the hard register is referenced
3137: in the same mode as in the original insn. If so, then it has not been
3138: split, and the rest of the code below is unnecessary. */
3139:
3140: for (i = 1; i < n_regs; i++)
3141: {
3142: new_reg = REGNO (reg) + i;
3143:
3144: /* Check for references to new_reg in the split insns. */
3145: for (insn = last; ; insn = PREV_INSN (insn))
3146: {
3147: if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
3148: && (temp = regno_use_in (new_reg, PATTERN (insn))))
3149: {
3150: /* Create a new reg dead note here. */
3151: link = rtx_alloc (EXPR_LIST);
3152: PUT_REG_NOTE_KIND (link, REG_DEAD);
3153: XEXP (link, 0) = temp;
3154: XEXP (link, 1) = REG_NOTES (insn);
3155: REG_NOTES (insn) = link;
3156: break;
3157: }
3158: /* It isn't mentioned anywhere, so no new reg note is needed for
3159: this register. */
3160: if (insn == first)
3161: break;
3162: }
3163: }
3164: }
3165:
3166: /* Subroutine of update_flow_info. Determines whether a SET or CLOBBER in an
3167: insn created by splitting needs a REG_DEAD or REG_UNUSED note added. */
3168:
3169: static void
3170: new_insn_dead_notes (pat, insn, last, orig_insn)
3171: rtx pat, insn, last, orig_insn;
3172: {
3173: rtx dest, tem, set;
3174:
3175: /* PAT is either a CLOBBER or a SET here. */
3176: dest = XEXP (pat, 0);
3177:
3178: while (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SUBREG
3179: || GET_CODE (dest) == STRICT_LOW_PART
3180: || GET_CODE (dest) == SIGN_EXTRACT)
3181: dest = XEXP (dest, 0);
3182:
3183: if (GET_CODE (dest) == REG)
3184: {
3185: for (tem = last; tem != insn; tem = PREV_INSN (tem))
3186: {
3187: if (GET_RTX_CLASS (GET_CODE (tem)) == 'i'
3188: && reg_overlap_mentioned_p (dest, PATTERN (tem))
3189: && (set = single_set (tem)))
3190: {
3191: rtx tem_dest = SET_DEST (set);
3192:
3193: while (GET_CODE (tem_dest) == ZERO_EXTRACT
3194: || GET_CODE (tem_dest) == SUBREG
3195: || GET_CODE (tem_dest) == STRICT_LOW_PART
3196: || GET_CODE (tem_dest) == SIGN_EXTRACT)
3197: tem_dest = XEXP (tem_dest, 0);
3198:
3199: if (tem_dest != dest)
3200: {
3201: /* Use the same scheme as combine.c, don't put both REG_DEAD
3202: and REG_UNUSED notes on the same insn. */
3203: if (! find_regno_note (tem, REG_UNUSED, REGNO (dest))
3204: && ! find_regno_note (tem, REG_DEAD, REGNO (dest)))
3205: {
3206: rtx note = rtx_alloc (EXPR_LIST);
3207: PUT_REG_NOTE_KIND (note, REG_DEAD);
3208: XEXP (note, 0) = dest;
3209: XEXP (note, 1) = REG_NOTES (tem);
3210: REG_NOTES (tem) = note;
3211: }
3212: /* The reg only dies in one insn, the last one that uses
3213: it. */
3214: break;
3215: }
3216: else if (reg_overlap_mentioned_p (dest, SET_SRC (set)))
3217: /* We found an instruction that both uses the register,
3218: and sets it, so no new REG_NOTE is needed for this set. */
3219: break;
3220: }
3221: }
3222: /* If this is a set, it must die somewhere, unless it is the dest of
3223: the original insn, and hence is live after the original insn. Abort
3224: if it isn't supposed to be live after the original insn.
3225:
3226: If this is a clobber, then just add a REG_UNUSED note. */
3227: if (tem == insn)
3228: {
3229: int live_after_orig_insn = 0;
3230: rtx pattern = PATTERN (orig_insn);
3231: int i;
3232:
3233: if (GET_CODE (pat) == CLOBBER)
3234: {
3235: rtx note = rtx_alloc (EXPR_LIST);
3236: PUT_REG_NOTE_KIND (note, REG_UNUSED);
3237: XEXP (note, 0) = dest;
3238: XEXP (note, 1) = REG_NOTES (insn);
3239: REG_NOTES (insn) = note;
3240: return;
3241: }
3242:
3243: /* The original insn could have multiple sets, so search the
3244: insn for all sets. */
3245: if (GET_CODE (pattern) == SET)
3246: {
3247: if (reg_overlap_mentioned_p (dest, SET_DEST (pattern)))
3248: live_after_orig_insn = 1;
3249: }
3250: else if (GET_CODE (pattern) == PARALLEL)
3251: {
3252: for (i = 0; i < XVECLEN (pattern, 0); i++)
3253: if (GET_CODE (XVECEXP (pattern, 0, i)) == SET
3254: && reg_overlap_mentioned_p (dest,
3255: SET_DEST (XVECEXP (pattern,
3256: 0, i))))
3257: live_after_orig_insn = 1;
3258: }
3259:
3260: if (! live_after_orig_insn)
3261: abort ();
3262: }
3263: }
3264: }
3265:
3266: /* Subroutine of update_flow_info. Update the value of reg_n_sets for all
3267: registers modified by X. INC is -1 if the containing insn is being deleted,
3268: and is 1 if the containing insn is a newly generated insn. */
3269:
3270: static void
3271: update_n_sets (x, inc)
3272: rtx x;
3273: int inc;
3274: {
3275: rtx dest = SET_DEST (x);
3276:
3277: while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
3278: || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
3279: dest = SUBREG_REG (dest);
3280:
3281: if (GET_CODE (dest) == REG)
3282: {
3283: int regno = REGNO (dest);
3284:
3285: if (regno < FIRST_PSEUDO_REGISTER)
3286: {
3287: register int i;
3288: int endregno = regno + HARD_REGNO_NREGS (regno, GET_MODE (dest));
3289:
3290: for (i = regno; i < endregno; i++)
3291: reg_n_sets[i] += inc;
3292: }
3293: else
3294: reg_n_sets[regno] += inc;
3295: }
3296: }
3297:
3298: /* Updates all flow-analysis related quantities (including REG_NOTES) for
3299: the insns from FIRST to LAST inclusive that were created by splitting
3300: ORIG_INSN. NOTES are the original REG_NOTES. */
3301:
3302: static void
3303: update_flow_info (notes, first, last, orig_insn)
3304: rtx notes;
3305: rtx first, last;
3306: rtx orig_insn;
3307: {
3308: rtx insn, note;
3309: rtx next;
3310: rtx orig_dest, temp;
3311: rtx set;
3312:
3313: /* Get and save the destination set by the original insn. */
3314:
3315: orig_dest = single_set (orig_insn);
3316: if (orig_dest)
3317: orig_dest = SET_DEST (orig_dest);
3318:
3319: /* Move REG_NOTES from the original insn to where they now belong. */
3320:
3321: for (note = notes; note; note = next)
3322: {
3323: next = XEXP (note, 1);
3324: switch (REG_NOTE_KIND (note))
3325: {
3326: case REG_DEAD:
3327: case REG_UNUSED:
3328: /* Move these notes from the original insn to the last new insn where
3329: the register is now set. */
3330:
3331: for (insn = last; ; insn = PREV_INSN (insn))
3332: {
3333: if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
3334: && reg_mentioned_p (XEXP (note, 0), PATTERN (insn)))
3335: {
3336: XEXP (note, 1) = REG_NOTES (insn);
3337: REG_NOTES (insn) = note;
3338:
3339: /* Sometimes need to convert REG_UNUSED notes to REG_DEAD
3340: notes. */
3341: /* ??? This won't handle mutiple word registers correctly,
3342: but should be good enough for now. */
3343: if (REG_NOTE_KIND (note) == REG_UNUSED
3344: && ! dead_or_set_p (insn, XEXP (note, 0)))
3345: PUT_REG_NOTE_KIND (note, REG_DEAD);
3346:
3347: /* The reg only dies in one insn, the last one that uses
3348: it. */
3349: break;
3350: }
3351: /* It must die somewhere, fail it we couldn't find where it died.
3352:
3353: If this is a REG_UNUSED note, then it must be a temporary
3354: register that was not needed by this instantiation of the
3355: pattern, so we can safely ignore it. */
3356: if (insn == first)
3357: {
3358: if (REG_NOTE_KIND (note) != REG_UNUSED)
3359: abort ();
3360:
3361: break;
3362: }
3363: }
3364:
3365: /* If this note refers to a multiple word hard register, it may
3366: have been split into several smaller hard register references.
3367: Check to see if there are any new register references that
3368: need REG_NOTES added for them. */
3369: temp = XEXP (note, 0);
3370: if (REG_NOTE_KIND (note) == REG_DEAD
3371: && GET_CODE (temp) == REG
3372: && REGNO (temp) < FIRST_PSEUDO_REGISTER
3373: && HARD_REGNO_NREGS (REGNO (temp), GET_MODE (temp)))
3374: split_hard_reg_notes (note, first, last, orig_insn);
3375: break;
3376:
3377: case REG_WAS_0:
3378: /* This note applies to the dest of the original insn. Find the
3379: first new insn that now has the same dest, and move the note
3380: there. */
3381:
3382: if (! orig_dest)
3383: abort ();
3384:
3385: for (insn = first; ; insn = NEXT_INSN (insn))
3386: {
3387: if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
3388: && (temp = single_set (insn))
3389: && rtx_equal_p (SET_DEST (temp), orig_dest))
3390: {
3391: XEXP (note, 1) = REG_NOTES (insn);
3392: REG_NOTES (insn) = note;
3393: /* The reg is only zero before one insn, the first that
3394: uses it. */
3395: break;
3396: }
3397: /* It must be set somewhere, fail if we couldn't find where it
3398: was set. */
3399: if (insn == last)
3400: abort ();
3401: }
3402: break;
3403:
3404: case REG_EQUAL:
3405: case REG_EQUIV:
3406: /* A REG_EQUIV or REG_EQUAL note on an insn with more than one
3407: set is meaningless. Just drop the note. */
3408: if (! orig_dest)
3409: break;
3410:
3411: case REG_NO_CONFLICT:
3412: /* These notes apply to the dest of the original insn. Find the last
3413: new insn that now has the same dest, and move the note there. */
3414:
3415: if (! orig_dest)
3416: abort ();
3417:
3418: for (insn = last; ; insn = PREV_INSN (insn))
3419: {
3420: if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
3421: && (temp = single_set (insn))
3422: && rtx_equal_p (SET_DEST (temp), orig_dest))
3423: {
3424: XEXP (note, 1) = REG_NOTES (insn);
3425: REG_NOTES (insn) = note;
3426: /* Only put this note on one of the new insns. */
3427: break;
3428: }
3429:
3430: /* The original dest must still be set someplace. Abort if we
3431: couldn't find it. */
3432: if (insn == first)
3433: abort ();
3434: }
3435: break;
3436:
3437: case REG_LIBCALL:
3438: /* Move a REG_LIBCALL note to the first insn created, and update
3439: the corresponding REG_RETVAL note. */
3440: XEXP (note, 1) = REG_NOTES (first);
3441: REG_NOTES (first) = note;
3442:
3443: insn = XEXP (note, 0);
3444: note = find_reg_note (insn, REG_RETVAL, 0);
3445: if (note)
3446: XEXP (note, 0) = first;
3447: break;
3448:
3449: case REG_RETVAL:
3450: /* Move a REG_RETVAL note to the last insn created, and update
3451: the corresponding REG_LIBCALL note. */
3452: XEXP (note, 1) = REG_NOTES (last);
3453: REG_NOTES (last) = note;
3454:
3455: insn = XEXP (note, 0);
3456: note = find_reg_note (insn, REG_LIBCALL, 0);
3457: if (note)
3458: XEXP (note, 0) = last;
3459: break;
3460:
3461: case REG_NONNEG:
3462: /* This should be moved to whichever instruction is a JUMP_INSN. */
3463:
3464: for (insn = last; ; insn = PREV_INSN (insn))
3465: {
3466: if (GET_CODE (insn) == JUMP_INSN)
3467: {
3468: XEXP (note, 1) = REG_NOTES (insn);
3469: REG_NOTES (insn) = note;
3470: /* Only put this note on one of the new insns. */
3471: break;
3472: }
3473: /* Fail if we couldn't find a JUMP_INSN. */
3474: if (insn == first)
3475: abort ();
3476: }
3477: break;
3478:
3479: case REG_INC:
3480: /* This should be moved to whichever instruction now has the
3481: increment operation. */
3482: abort ();
3483:
3484: case REG_LABEL:
3485: /* Should be moved to the new insn(s) which use the label. */
3486: abort ();
3487:
3488: case REG_CC_SETTER:
3489: case REG_CC_USER:
3490: /* These two notes will never appear until after reorg, so we don't
3491: have to handle them here. */
3492: default:
3493: abort ();
3494: }
3495: }
3496:
3497: /* Each new insn created, except the last, has a new set. If the destination
3498: is a register, then this reg is now live across several insns, whereas
3499: previously the dest reg was born and died within the same insn. To
3500: reflect this, we now need a REG_DEAD note on the insn where this
3501: dest reg dies.
3502:
3503: Similarly, the new insns may have clobbers that need REG_UNUSED notes. */
3504:
3505: for (insn = first; insn != last; insn = NEXT_INSN (insn))
3506: {
3507: rtx pat;
3508: int i;
3509:
3510: pat = PATTERN (insn);
3511: if (GET_CODE (pat) == SET || GET_CODE (pat) == CLOBBER)
3512: new_insn_dead_notes (pat, insn, last, orig_insn);
3513: else if (GET_CODE (pat) == PARALLEL)
3514: {
3515: for (i = 0; i < XVECLEN (pat, 0); i++)
3516: if (GET_CODE (XVECEXP (pat, 0, i)) == SET
3517: || GET_CODE (XVECEXP (pat, 0, i)) == CLOBBER)
3518: new_insn_dead_notes (XVECEXP (pat, 0, i), insn, last, orig_insn);
3519: }
3520: }
3521:
3522: /* If any insn, except the last, uses the register set by the last insn,
3523: then we need a new REG_DEAD note on that insn. In this case, there
3524: would not have been a REG_DEAD note for this register in the original
3525: insn because it was used and set within one insn.
3526:
3527: There is no new REG_DEAD note needed if the last insn uses the register
3528: that it is setting. */
3529:
3530: set = single_set (last);
3531: if (set)
3532: {
3533: rtx dest = SET_DEST (set);
3534:
3535: while (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SUBREG
3536: || GET_CODE (dest) == STRICT_LOW_PART
3537: || GET_CODE (dest) == SIGN_EXTRACT)
3538: dest = XEXP (dest, 0);
3539:
3540: if (GET_CODE (dest) == REG
3541: && ! reg_overlap_mentioned_p (dest, SET_SRC (set)))
3542: {
3543: for (insn = PREV_INSN (last); ; insn = PREV_INSN (insn))
3544: {
3545: if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
3546: && reg_mentioned_p (dest, PATTERN (insn))
3547: && (set = single_set (insn)))
3548: {
3549: rtx insn_dest = SET_DEST (set);
3550:
3551: while (GET_CODE (insn_dest) == ZERO_EXTRACT
3552: || GET_CODE (insn_dest) == SUBREG
3553: || GET_CODE (insn_dest) == STRICT_LOW_PART
3554: || GET_CODE (insn_dest) == SIGN_EXTRACT)
3555: insn_dest = XEXP (insn_dest, 0);
3556:
3557: if (insn_dest != dest)
3558: {
3559: note = rtx_alloc (EXPR_LIST);
3560: PUT_REG_NOTE_KIND (note, REG_DEAD);
3561: XEXP (note, 0) = dest;
3562: XEXP (note, 1) = REG_NOTES (insn);
3563: REG_NOTES (insn) = note;
3564: /* The reg only dies in one insn, the last one
3565: that uses it. */
3566: break;
3567: }
3568: }
3569: if (insn == first)
3570: break;
3571: }
3572: }
3573: }
3574:
3575: /* If the original dest is modifying a multiple register target, and the
3576: original instruction was split such that the original dest is now set
3577: by two or more SUBREG sets, then the split insns no longer kill the
3578: destination of the original insn.
3579:
3580: In this case, if there exists an instruction in the same basic block,
3581: before the split insn, which uses the original dest, and this use is
3582: killed by the original insn, then we must remove the REG_DEAD note on
3583: this insn, because it is now superfluous.
3584:
3585: This does not apply when a hard register gets split, because the code
3586: knows how to handle overlapping hard registers properly. */
3587: if (orig_dest && GET_CODE (orig_dest) == REG)
3588: {
3589: int found_orig_dest = 0;
3590: int found_split_dest = 0;
3591:
3592: for (insn = first; ; insn = NEXT_INSN (insn))
3593: {
3594: set = single_set (insn);
3595: if (set)
3596: {
3597: if (GET_CODE (SET_DEST (set)) == REG
3598: && REGNO (SET_DEST (set)) == REGNO (orig_dest))
3599: {
3600: found_orig_dest = 1;
3601: break;
3602: }
3603: else if (GET_CODE (SET_DEST (set)) == SUBREG
3604: && SUBREG_REG (SET_DEST (set)) == orig_dest)
3605: {
3606: found_split_dest = 1;
3607: break;
3608: }
3609: }
3610:
3611: if (insn == last)
3612: break;
3613: }
3614:
3615: if (found_split_dest)
3616: {
3617: /* Search backwards from FIRST, looking for the first insn that uses
3618: the original dest. Stop if we pass a CODE_LABEL or a JUMP_INSN.
3619: If we find an insn, and it has a REG_DEAD note, then delete the
3620: note. */
3621:
3622: for (insn = first; insn; insn = PREV_INSN (insn))
3623: {
3624: if (GET_CODE (insn) == CODE_LABEL
3625: || GET_CODE (insn) == JUMP_INSN)
3626: break;
3627: else if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
3628: && reg_mentioned_p (orig_dest, insn))
3629: {
3630: note = find_regno_note (insn, REG_DEAD, REGNO (orig_dest));
3631: if (note)
3632: remove_note (insn, note);
3633: }
3634: }
3635: }
3636: else if (! found_orig_dest)
3637: {
3638: /* This should never happen. */
3639: abort ();
3640: }
3641: }
3642:
3643: /* Update reg_n_sets. This is necessary to prevent local alloc from
3644: converting REG_EQUAL notes to REG_EQUIV when splitting has modified
3645: a reg from set once to set multiple times. */
3646:
3647: {
3648: rtx x = PATTERN (orig_insn);
3649: RTX_CODE code = GET_CODE (x);
3650:
3651: if (code == SET || code == CLOBBER)
3652: update_n_sets (x, -1);
3653: else if (code == PARALLEL)
3654: {
3655: int i;
3656: for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
3657: {
3658: code = GET_CODE (XVECEXP (x, 0, i));
3659: if (code == SET || code == CLOBBER)
3660: update_n_sets (XVECEXP (x, 0, i), -1);
3661: }
3662: }
3663:
3664: for (insn = first; ; insn = NEXT_INSN (insn))
3665: {
3666: x = PATTERN (insn);
3667: code = GET_CODE (x);
3668:
3669: if (code == SET || code == CLOBBER)
3670: update_n_sets (x, 1);
3671: else if (code == PARALLEL)
3672: {
3673: int i;
3674: for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
3675: {
3676: code = GET_CODE (XVECEXP (x, 0, i));
3677: if (code == SET || code == CLOBBER)
3678: update_n_sets (XVECEXP (x, 0, i), 1);
3679: }
3680: }
3681:
3682: if (insn == last)
3683: break;
3684: }
3685: }
3686: }
3687:
3688: /* The one entry point in this file. DUMP_FILE is the dump file for
3689: this pass. */
3690:
3691: void
3692: schedule_insns (dump_file)
3693: FILE *dump_file;
3694: {
3695: int max_uid = MAX_INSNS_PER_SPLIT * (get_max_uid () + 1);
3696: int i, b;
3697: rtx insn;
3698:
3699: /* Taking care of this degenerate case makes the rest of
3700: this code simpler. */
3701: if (n_basic_blocks == 0)
3702: return;
3703:
3704: /* Create an insn here so that we can hang dependencies off of it later. */
3705: sched_before_next_call = gen_rtx (INSN, VOIDmode, 0, 0, 0, 0, 0, 0, 0);
3706:
3707: /* Initialize the unused_*_lists. We can't use the ones left over from
3708: the previous function, because gcc has freed that memory. We can use
3709: the ones left over from the first sched pass in the second pass however,
3710: so only clear them on the first sched pass. The first pass is before
3711: reload if flag_schedule_insns is set, otherwise it is afterwards. */
3712:
3713: if (reload_completed == 0 || ! flag_schedule_insns)
3714: {
3715: unused_insn_list = 0;
3716: unused_expr_list = 0;
3717: }
3718:
3719: /* We create no insns here, only reorder them, so we
3720: remember how far we can cut back the stack on exit. */
3721:
3722: /* Allocate data for this pass. See comments, above,
3723: for what these vectors do. */
3724: /* ??? Instruction splitting below may create new instructions, so these
3725: arrays must be bigger than just max_uid. */
3726: insn_luid = (int *) alloca (max_uid * sizeof (int));
3727: insn_priority = (int *) alloca (max_uid * sizeof (int));
3728: insn_ref_count = (int *) alloca (max_uid * sizeof (int));
3729:
3730: if (reload_completed == 0)
3731: {
3732: sched_reg_n_deaths = (short *) alloca (max_regno * sizeof (short));
3733: sched_reg_n_calls_crossed = (int *) alloca (max_regno * sizeof (int));
3734: sched_reg_live_length = (int *) alloca (max_regno * sizeof (int));
3735: bb_dead_regs = (regset) alloca (regset_bytes);
3736: bb_live_regs = (regset) alloca (regset_bytes);
3737: bzero (sched_reg_n_calls_crossed, max_regno * sizeof (int));
3738: bzero (sched_reg_live_length, max_regno * sizeof (int));
3739: bcopy (reg_n_deaths, sched_reg_n_deaths, max_regno * sizeof (short));
3740: init_alias_analysis ();
3741: }
3742: else
3743: {
3744: sched_reg_n_deaths = 0;
3745: sched_reg_n_calls_crossed = 0;
3746: sched_reg_live_length = 0;
3747: bb_dead_regs = 0;
3748: bb_live_regs = 0;
3749: if (! flag_schedule_insns)
3750: init_alias_analysis ();
3751: }
3752:
3753: if (write_symbols != NO_DEBUG)
3754: {
3755: rtx line;
3756:
3757: line_note = (rtx *) alloca (max_uid * sizeof (rtx));
3758: bzero (line_note, max_uid * sizeof (rtx));
3759: line_note_head = (rtx *) alloca (n_basic_blocks * sizeof (rtx));
3760: bzero (line_note_head, n_basic_blocks * sizeof (rtx));
3761:
3762: /* Determine the line-number at the start of each basic block.
3763: This must be computed and saved now, because after a basic block's
3764: predecessor has been scheduled, it is impossible to accurately
3765: determine the correct line number for the first insn of the block. */
3766:
3767: for (b = 0; b < n_basic_blocks; b++)
3768: for (line = basic_block_head[b]; line; line = PREV_INSN (line))
3769: if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
3770: {
3771: line_note_head[b] = line;
3772: break;
3773: }
3774: }
3775:
3776: bzero (insn_luid, max_uid * sizeof (int));
3777: bzero (insn_priority, max_uid * sizeof (int));
3778: bzero (insn_ref_count, max_uid * sizeof (int));
3779:
3780: /* Schedule each basic block, block by block. */
3781:
3782: if (NEXT_INSN (basic_block_end[n_basic_blocks-1]) == 0
3783: || (GET_CODE (basic_block_end[n_basic_blocks-1]) != NOTE
3784: && GET_CODE (basic_block_end[n_basic_blocks-1]) != CODE_LABEL))
3785: emit_note_after (NOTE_INSN_DELETED, basic_block_end[n_basic_blocks-1]);
3786:
3787: for (b = 0; b < n_basic_blocks; b++)
3788: {
3789: rtx insn, next;
3790: rtx insns;
3791:
3792: note_list = 0;
3793:
3794: for (insn = basic_block_head[b]; ; insn = next)
3795: {
3796: rtx prev;
3797: rtx set;
3798:
3799: /* Can't use `next_real_insn' because that
3800: might go across CODE_LABELS and short-out basic blocks. */
3801: next = NEXT_INSN (insn);
3802: if (GET_CODE (insn) != INSN)
3803: {
3804: if (insn == basic_block_end[b])
3805: break;
3806:
3807: continue;
3808: }
3809:
3810: /* Don't split no-op move insns. These should silently disappear
3811: later in final. Splitting such insns would break the code
3812: that handles REG_NO_CONFLICT blocks. */
3813: set = single_set (insn);
3814: if (set && rtx_equal_p (SET_SRC (set), SET_DEST (set)))
3815: {
3816: if (insn == basic_block_end[b])
3817: break;
3818:
3819: /* Nops get in the way while scheduling, so delete them now if
3820: register allocation has already been done. It is too risky
3821: to try to do this before register allocation, and there are
3822: unlikely to be very many nops then anyways. */
3823: if (reload_completed)
3824: {
3825: PUT_CODE (insn, NOTE);
3826: NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
3827: NOTE_SOURCE_FILE (insn) = 0;
3828: }
3829:
3830: continue;
3831: }
3832:
3833: /* Split insns here to get max fine-grain parallelism. */
3834: prev = PREV_INSN (insn);
3835: if (reload_completed == 0)
3836: {
3837: rtx last, first = PREV_INSN (insn);
3838: rtx notes = REG_NOTES (insn);
3839:
3840: last = try_split (PATTERN (insn), insn, 1);
3841: if (last != insn)
3842: {
3843: /* try_split returns the NOTE that INSN became. */
3844: first = NEXT_INSN (first);
3845: update_flow_info (notes, first, last, insn);
3846:
3847: PUT_CODE (insn, NOTE);
3848: NOTE_SOURCE_FILE (insn) = 0;
3849: NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
3850: if (insn == basic_block_head[b])
3851: basic_block_head[b] = first;
3852: if (insn == basic_block_end[b])
3853: {
3854: basic_block_end[b] = last;
3855: break;
3856: }
3857: }
3858: }
3859:
3860: if (insn == basic_block_end[b])
3861: break;
3862: }
3863:
3864: schedule_block (b, dump_file);
3865:
3866: #ifdef USE_C_ALLOCA
3867: alloca (0);
3868: #endif
3869: }
3870:
3871: if (write_symbols != NO_DEBUG)
3872: {
3873: rtx line = 0;
3874: rtx insn = get_insns ();
3875: int active_insn = 0;
3876: int notes = 0;
3877:
3878: /* Walk the insns deleting redundant line-number notes. Many of these
3879: are already present. The remainder tend to occur at basic
3880: block boundaries. */
3881: for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
3882: if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
3883: {
3884: /* If there are no active insns following, INSN is redundant. */
3885: if (active_insn == 0)
3886: {
3887: notes++;
3888: NOTE_SOURCE_FILE (insn) = 0;
3889: NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
3890: }
3891: /* If the line number is unchanged, LINE is redundant. */
3892: else if (line
3893: && NOTE_LINE_NUMBER (line) == NOTE_LINE_NUMBER (insn)
3894: && NOTE_SOURCE_FILE (line) == NOTE_SOURCE_FILE (insn))
3895: {
3896: notes++;
3897: NOTE_SOURCE_FILE (line) = 0;
3898: NOTE_LINE_NUMBER (line) = NOTE_INSN_DELETED;
3899: line = insn;
3900: }
3901: else
3902: line = insn;
3903: active_insn = 0;
3904: }
3905: else if (! ((GET_CODE (insn) == NOTE
3906: && NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED)
3907: || (GET_CODE (insn) == INSN
3908: && (GET_CODE (PATTERN (insn)) == USE
3909: || GET_CODE (PATTERN (insn)) == CLOBBER))))
3910: active_insn++;
3911:
3912: if (dump_file && notes)
3913: fprintf (dump_file, ";; deleted %d line-number notes\n", notes);
3914: }
3915:
3916: if (reload_completed == 0)
3917: {
3918: int regno;
3919: for (regno = 0; regno < max_regno; regno++)
3920: if (sched_reg_live_length[regno])
3921: {
3922: if (dump_file)
3923: {
3924: if (reg_live_length[regno] > sched_reg_live_length[regno])
3925: fprintf (dump_file,
3926: ";; register %d life shortened from %d to %d\n",
3927: regno, reg_live_length[regno],
3928: sched_reg_live_length[regno]);
3929: /* Negative values are special; don't overwrite the current
3930: reg_live_length value if it is negative. */
3931: else if (reg_live_length[regno] < sched_reg_live_length[regno]
3932: && reg_live_length[regno] >= 0)
3933: fprintf (dump_file,
3934: ";; register %d life extended from %d to %d\n",
3935: regno, reg_live_length[regno],
3936: sched_reg_live_length[regno]);
3937:
3938: if (reg_n_calls_crossed[regno]
3939: && ! sched_reg_n_calls_crossed[regno])
3940: fprintf (dump_file,
3941: ";; register %d no longer crosses calls\n", regno);
3942: else if (! reg_n_calls_crossed[regno]
3943: && sched_reg_n_calls_crossed[regno])
3944: fprintf (dump_file,
3945: ";; register %d now crosses calls\n", regno);
3946: }
3947: reg_live_length[regno] = sched_reg_live_length[regno];
3948: reg_n_calls_crossed[regno] = sched_reg_n_calls_crossed[regno];
3949: }
3950: }
3951: }
3952: #endif /* INSN_SCHEDULING */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.