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