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