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