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