From bd58420c07007371fa217a85dc03727e3018eac9 Mon Sep 17 00:00:00 2001 From: Richard Kenner Date: Sun, 2 Feb 1992 17:23:08 -0500 Subject: [PATCH] Initial revision From-SVN: r271 --- gcc/sched.c | 3951 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 3951 insertions(+) create mode 100644 gcc/sched.c diff --git a/gcc/sched.c b/gcc/sched.c new file mode 100644 index 000000000000..020df0e94918 --- /dev/null +++ b/gcc/sched.c @@ -0,0 +1,3951 @@ +/* Instruction scheduling pass. + Copyright (C) 1992 Free Software Foundation, Inc. + Contributed by Michael Tiemann (tiemann@cygnus.com) + Enhanced by, and currently maintained by, Jim Wilson (wilson@cygnus.com) + +This file is part of GNU CC. + +GNU CC is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 2, or (at your option) +any later version. + +GNU CC is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GNU CC; see the file COPYING. If not, write to +the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */ + +/* Instruction scheduling pass. + + This pass implements list scheduling within basic blocks. It is + run after flow analysis, but before register allocation. The + scheduler works as follows: + + We compute insn priorities based on data dependencies. Flow + analysis only creates a fraction of the data-dependencies we must + observe: namely, only those dependencies which the combiner can be + expected to use. For this pass, we must therefore create the + remaining dependencies we need to observe: register dependencies, + memory dependencies, dependencies to keep function calls in order, + and the dependence between a conditional branch and the setting of + condition codes are all dealt with here. + + The scheduler first traverses the data flow graph, starting with + the last instruction, and proceeding to the first, assigning + values to insn_priority as it goes. This sorts the instructions + topologically by data dependence. + + Once priorities have been established, we order the insns using + list scheduling. This works as follows: starting with a list of + all the ready insns, and sorted according to priority number, we + schedule the insn from the end of the list by placing its + predecessors in the list according to their priority order. We + consider this insn scheduled by setting the pointer to the "end" of + the list to point to the previous insn. When an insn has no + predecessors, we also add it to the ready list. When all insns down + to the lowest priority have been scheduled, the critical path of the + basic block has been made as short as possible. The remaining insns + are then scheduled in remaining slots. + + The following list shows the order in which we want to break ties: + + 1. choose insn with lowest conflict cost, ties broken by + 2. choose insn with the longest path to end of bb, ties broken by + 3. choose insn that kills the most registers, ties broken by + 4. choose insn that conflicts with the most ready insns, or finally + 5. choose insn with lowest UID. + + Memory references complicate matters. Only if we can be certain + that memory references are not part of the data dependency graph + (via true, anti, or output dependence), can we move operations past + memory references. To first approximation, reads can be done + independently, while writes introduce dependencies. Better + approximations will yield fewer dependencies. + + Dependencies set up by memory references are treated in exactly the + same way as other dependencies, by using LOG_LINKS. + + Having optimized the critical path, we may have also unduly + extended the lifetimes of some registers. If an operation requires + that constants be loaded into registers, it is certainly desirable + to load those constants as early as necessary, but no earlier. + I.e., it will not do to load up a bunch of registers at the + beginning of a basic block only to use them at the end, if they + could be loaded later, since this may result in excessive register + utilization. + + Note that since branches are never in basic blocks, but only end + basic blocks, this pass will not do any branch scheduling. But + that is ok, since we can use GNU's delayed branch scheduling + pass to take care of this case. + + Also note that no further optimizations based on algebraic identities + are performed, so this pass would be a good one to perform instruction + splitting, such as breaking up a multiply instruction into shifts + and adds where that is profitable. + + Given the memory aliasing analysis that this pass should perform, + it should be possible to remove redundant stores to memory, and to + load values from registers instead of hitting memory. + + This pass must update information that subsequent passes expect to be + correct. Namely: reg_n_refs, reg_n_sets, reg_n_deaths, + reg_n_calls_crossed, and reg_live_length. Also, basic_block_head, + basic_block_end. + + The information in the line number notes is carefully retained by this + pass. All other NOTE insns are grouped in their same relative order at + the beginning of basic blocks that have been scheduled. */ + +#include +#include "config.h" +#include "rtl.h" +#include "basic-block.h" +#include "regs.h" +#include "hard-reg-set.h" +#include "flags.h" +#include "insn-config.h" +#include "insn-attr.h" + +/* Arrays set up by scheduling for the same respective purposes as + similar-named arrays set up by flow analysis. We work with these + arrays during the scheduling pass so we can compare values against + unscheduled code. + + Values of these arrays are copied at the end of this pass into the + arrays set up by flow analysis. */ +static short *sched_reg_n_deaths; +static int *sched_reg_n_calls_crossed; +static int *sched_reg_live_length; + +/* Element N is the next insn that sets (hard or pseudo) register + N within the current basic block; or zero, if there is no + such insn. Needed for new registers which may be introduced + by splitting insns. */ +static rtx *reg_last_uses; +static rtx *reg_last_sets; + +/* Vector indexed by INSN_UID giving the original ordering of the insns. */ +static int *insn_luid; +#define INSN_LUID(INSN) (insn_luid[INSN_UID (INSN)]) + +/* Vector indexed by INSN_UID giving each instruction a priority. */ +static int *insn_priority; +#define INSN_PRIORITY(INSN) (insn_priority[INSN_UID (INSN)]) + +#define DONE_PRIORITY -1 +#define MAX_PRIORITY 0x7fffffff +#define TAIL_PRIORITY 0x7ffffffe +#define LAUNCH_PRIORITY 0x7f000001 +#define DONE_PRIORITY_P(INSN) (INSN_PRIORITY (INSN) < 0) +#define LOW_PRIORITY_P(INSN) ((INSN_PRIORITY (INSN) & 0x7f000000) == 0) + +/* Vector indexed by INSN_UID giving number of insns refering to this insn. */ +static int *insn_ref_count; +#define INSN_REF_COUNT(INSN) (insn_ref_count[INSN_UID (INSN)]) + +/* Vector indexed by INSN_UID giving line-number note in effect for each + insn. For line-number notes, this indicates whether the note may be + reused. */ +static rtx *line_note; +#define LINE_NOTE(INSN) (line_note[INSN_UID (INSN)]) + +/* Vector indexed by basic block number giving the starting line-number + for each basic block. */ +static rtx *line_note_head; + +/* List of important notes we must keep around. This is a pointer to the + last element in the list. */ +static rtx note_list; + +/* Regsets telling whether a given register is live or dead before the last + scheduled insn. Must scan the instructions once before scheduling to + determine what registers are live or dead at the end of the block. */ +static regset bb_dead_regs; +static regset bb_live_regs; + +/* Regset telling whether a given register is live after the insn currently + being scheduled. Before processing an insn, this is equal to bb_live_regs + above. This is used so that we can find regsiters that are newly born/dead + after processing an insn. */ +static regset old_live_regs; + +/* The chain of REG_DEAD notes. REG_DEAD notes are removed from all insns + during the initial scan and reused later. If there are not exactly as + many REG_DEAD notes in the post scheduled code as there were in the + prescheduled code then we trigger an abort because this indicates a bug. */ +static rtx dead_notes; + +/* Queues, etc. */ + +/* An instruction is ready to be scheduled when all insns following it + have already been scheduled. It is important to ensure that all + insns which use its result will not be executed until its result + has been computed. We maintain three lists (conceptually): + + (1) a "Ready" list of unscheduled, uncommitted insns + (2) a "Scheduled" list of scheduled insns + (3) a "Pending" list of insns which can be scheduled, but + for stalls. + + Insns move from the "Ready" list to the "Pending" list when + all insns following them have been scheduled. + + Insns move from the "Pending" list to the "Scheduled" list + when there is sufficient space in the pipeline to prevent + stalls between the insn and scheduled insns which use it. + + The "Pending" list acts as a buffer to prevent insns + from avalanching. + + The "Ready" list is implemented by the variable `ready'. + The "Pending" list are the insns in the LOG_LINKS of ready insns. + The "Scheduled" list is the new insn chain built by this pass. */ + +/* Implement a circular buffer from which instructions are issued. */ +#define Q_SIZE 128 +static rtx insn_queue[Q_SIZE]; +static int q_ptr = 0; +static int q_size = 0; +#define NEXT_Q(X) (((X)+1) & (Q_SIZE-1)) +#define NEXT_Q_AFTER(X,C) (((X)+C) & (Q_SIZE-1)) + +/* Forward declarations. */ +static void sched_analyze_2 (); +static void schedule_block (); + +/* Main entry point of this file. */ +void schedule_insns (); + +#define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X))) + +/* Vector indexed by N giving the initial (unchanging) value known + for pseudo-register N. */ +static rtx *reg_known_value; + +/* Indicates number of valid entries in reg_known_value. */ +static int reg_known_value_size; + +static rtx +canon_rtx (x) + rtx x; +{ + if (GET_CODE (x) == REG && REGNO (x) >= FIRST_PSEUDO_REGISTER + && REGNO (x) <= reg_known_value_size) + return reg_known_value[REGNO (x)]; + else if (GET_CODE (x) == PLUS) + { + rtx x0 = canon_rtx (XEXP (x, 0)); + rtx x1 = canon_rtx (XEXP (x, 1)); + + if (x0 != XEXP (x, 0) || x1 != XEXP (x, 1)) + { + /* We can tolerate LO_SUMs being offset here; these + rtl are used for nothing other than comparisons. */ + if (GET_CODE (x0) == CONST_INT) + return plus_constant_for_output (x1, INTVAL (x0)); + else if (GET_CODE (x1) == CONST_INT) + return plus_constant_for_output (x0, INTVAL (x1)); + return gen_rtx (PLUS, GET_MODE (x), x0, x1); + } + } + return x; +} + +/* Set up all info needed to perform alias analysis on memory references. */ + +void +init_alias_analysis () +{ + int maxreg = max_reg_num (); + rtx insn; + rtx note; + rtx set; + + reg_known_value_size = maxreg; + + reg_known_value + = (rtx *) oballoc ((maxreg-FIRST_PSEUDO_REGISTER) * sizeof (rtx)) + - FIRST_PSEUDO_REGISTER; + bzero (reg_known_value+FIRST_PSEUDO_REGISTER, + (maxreg-FIRST_PSEUDO_REGISTER) * sizeof (rtx)); + + /* Fill in the entries with known constant values. */ + for (insn = get_insns (); insn; insn = NEXT_INSN (insn)) + if ((set = single_set (insn)) != 0 + && GET_CODE (SET_DEST (set)) == REG + && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER + && (((note = find_reg_note (insn, REG_EQUAL, 0)) != 0 + && reg_n_sets[REGNO (SET_DEST (set))] == 1) + || (note = find_reg_note (insn, REG_EQUIV, 0)) != 0) + && GET_CODE (XEXP (note, 0)) != EXPR_LIST) + reg_known_value[REGNO (SET_DEST (set))] = XEXP (note, 0); + + /* Fill in the remaining entries. */ + while (--maxreg >= FIRST_PSEUDO_REGISTER) + if (reg_known_value[maxreg] == 0) + reg_known_value[maxreg] = regno_reg_rtx[maxreg]; +} + +/* Return 1 if X and Y are identical-looking rtx's. + + We use the data in reg_known_value above to see if two registers with + different numbers are, in fact, equivalent. */ + +static int +rtx_equal_for_memref_p (x, y) + rtx x, y; +{ + register int i; + register int j; + register enum rtx_code code; + register char *fmt; + + if (x == 0 && y == 0) + return 1; + if (x == 0 || y == 0) + return 0; + x = canon_rtx (x); + y = canon_rtx (y); + + if (x == y) + return 1; + + code = GET_CODE (x); + /* Rtx's of different codes cannot be equal. */ + if (code != GET_CODE (y)) + return 0; + + /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent. + (REG:SI x) and (REG:HI x) are NOT equivalent. */ + + if (GET_MODE (x) != GET_MODE (y)) + return 0; + + /* REG, LABEL_REF, and SYMBOL_REF can be compared nonrecursively. */ + + if (code == REG) + return REGNO (x) == REGNO (y); + if (code == LABEL_REF) + return XEXP (x, 0) == XEXP (y, 0); + if (code == SYMBOL_REF) + return XSTR (x, 0) == XSTR (y, 0); + + /* Compare the elements. If any pair of corresponding elements + fail to match, return 0 for the whole things. */ + + fmt = GET_RTX_FORMAT (code); + for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) + { + switch (fmt[i]) + { + case 'n': + case 'i': + if (XINT (x, i) != XINT (y, i)) + return 0; + break; + + case 'V': + case 'E': + /* Two vectors must have the same length. */ + if (XVECLEN (x, i) != XVECLEN (y, i)) + return 0; + + /* And the corresponding elements must match. */ + for (j = 0; j < XVECLEN (x, i); j++) + if (rtx_equal_for_memref_p (XVECEXP (x, i, j), XVECEXP (y, i, j)) == 0) + return 0; + break; + + case 'e': + if (rtx_equal_for_memref_p (XEXP (x, i), XEXP (y, i)) == 0) + return 0; + break; + + case 'S': + case 's': + if (strcmp (XSTR (x, i), XSTR (y, i))) + return 0; + break; + + case 'u': + /* These are just backpointers, so they don't matter. */ + break; + + case '0': + break; + + /* It is believed that rtx's at this level will never + contain anything but integers and other rtx's, + except for within LABEL_REFs and SYMBOL_REFs. */ + default: + abort (); + } + } + return 1; +} + +/* Given an rtx X, find a SYMBOL_REF or LABEL_REF within + X and return it, or return 0 if none found. */ + +static rtx +find_symbolic_term (x) + rtx x; +{ + register int i; + register enum rtx_code code; + register char *fmt; + + code = GET_CODE (x); + if (code == SYMBOL_REF || code == LABEL_REF) + return x; + if (GET_RTX_CLASS (code) == 'o') + return 0; + + fmt = GET_RTX_FORMAT (code); + for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) + { + rtx t; + + if (fmt[i] == 'e') + { + t = find_symbolic_term (XEXP (x, i)); + if (t != 0) + return t; + } + else if (fmt[i] == 'E') + break; + } + return 0; +} + +/* Return nonzero if X and Y (memory addresses) could reference the + same location in memory. C is an offset accumulator. When + C is nonzero, we are testing aliases between X and Y + C. + XSIZE is the size in bytes of the X reference, + similarly YSIZE is the size in bytes for Y. + + If XSIZE or YSIZE is zero, we do not know the amount of memory being + referenced (the reference was BLKmode), so make the most pessimistic + assumptions. + + We recognize the following cases of non-conflicting memory: + + (1) addresses involving the frame pointer cannot conflict + with addresses involving static variables. + (2) static variables with different addresses cannot conflict. + + Nice to notice that varying addresses cannot confict with fp if no + local variables had their addresses taken, but that's too hard now. */ + +static int +memrefs_conflict_p (xsize, x, ysize, y, c) + rtx x, y; + int xsize, ysize; + int c; +{ + if (GET_CODE (x) == HIGH) + x = XEXP (x, 0); + else if (GET_CODE (x) == LO_SUM) + x = XEXP (x, 1); + else + x = canon_rtx (x); + if (GET_CODE (y) == HIGH) + y = XEXP (y, 0); + else if (GET_CODE (y) == LO_SUM) + y = XEXP (y, 1); + else + y = canon_rtx (y); + + if (rtx_equal_for_memref_p (x, y)) + return (xsize == 0 || ysize == 0 || + (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0)); + + if (y == frame_pointer_rtx || y == stack_pointer_rtx) + { + rtx t = y; + int tsize = ysize; + y = x; ysize = xsize; + x = t; xsize = tsize; + } + + if (x == frame_pointer_rtx || x == stack_pointer_rtx) + { + rtx y1; + + if (CONSTANT_P (y)) + return 0; + + if (GET_CODE (y) == PLUS + && canon_rtx (XEXP (y, 0)) == x + && (y1 = canon_rtx (XEXP (y, 1))) + && GET_CODE (y1) == CONST_INT) + { + c += INTVAL (y1); + return (xsize == 0 || ysize == 0 + || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0)); + } + + if (GET_CODE (y) == PLUS + && (y1 = canon_rtx (XEXP (y, 0))) + && CONSTANT_P (y1)) + return 0; + + return 1; + } + + if (GET_CODE (x) == PLUS) + { + /* The fact that X is canonnicallized means that this + PLUS rtx is canonnicallized. */ + rtx x0 = XEXP (x, 0); + rtx x1 = XEXP (x, 1); + + if (GET_CODE (y) == PLUS) + { + /* The fact that Y is canonnicallized means that this + PLUS rtx is canonnicallized. */ + rtx y0 = XEXP (y, 0); + rtx y1 = XEXP (y, 1); + + if (rtx_equal_for_memref_p (x1, y1)) + return memrefs_conflict_p (xsize, x0, ysize, y0, c); + if (rtx_equal_for_memref_p (x0, y0)) + return memrefs_conflict_p (xsize, x1, ysize, y1, c); + if (GET_CODE (x1) == CONST_INT) + if (GET_CODE (y1) == CONST_INT) + return memrefs_conflict_p (xsize, x0, ysize, y0, + c - INTVAL (x1) + INTVAL (y1)); + else + return memrefs_conflict_p (xsize, x0, ysize, y, c - INTVAL (x1)); + else if (GET_CODE (y1) == CONST_INT) + return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1)); + + /* Handle case where we cannot understand iteration operators, + but we notice that the base addresses are distinct objects. */ + x = find_symbolic_term (x); + if (x == 0) + return 1; + y = find_symbolic_term (y); + if (y == 0) + return 1; + return rtx_equal_for_memref_p (x, y); + } + else if (GET_CODE (x1) == CONST_INT) + return memrefs_conflict_p (xsize, x0, ysize, y, c - INTVAL (x1)); + } + else if (GET_CODE (y) == PLUS) + { + /* The fact that Y is canonnicallized means that this + PLUS rtx is canonnicallized. */ + rtx y0 = XEXP (y, 0); + rtx y1 = XEXP (y, 1); + + if (GET_CODE (y1) == CONST_INT) + return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1)); + else + return 1; + } + + if (GET_CODE (x) == GET_CODE (y)) + switch (GET_CODE (x)) + { + case MULT: + { + /* Handle cases where we expect the second operands to be the + same, and check only whether the first operand would conflict + or not. */ + rtx x0, y0; + rtx x1 = canon_rtx (XEXP (x, 1)); + rtx y1 = canon_rtx (XEXP (y, 1)); + if (! rtx_equal_for_memref_p (x1, y1)) + return 1; + x0 = canon_rtx (XEXP (x, 0)); + y0 = canon_rtx (XEXP (y, 0)); + if (rtx_equal_for_memref_p (x0, y0)) + return (xsize == 0 || ysize == 0 + || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0)); + + /* Can't properly adjust our sizes. */ + if (GET_CODE (x1) != CONST_INT) + return 1; + xsize /= INTVAL (x1); + ysize /= INTVAL (x1); + c /= INTVAL (x1); + return memrefs_conflict_p (xsize, x0, ysize, y0, c); + } + } + + if (CONSTANT_P (x)) + { + if (GET_CODE (x) == CONST_INT && GET_CODE (y) == CONST_INT) + { + c += (INTVAL (y) - INTVAL (x)); + return (xsize == 0 || ysize == 0 + || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0)); + } + + if (GET_CODE (x) == CONST) + { + if (GET_CODE (y) == CONST) + return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)), + ysize, canon_rtx (XEXP (y, 0)), c); + else + return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)), + ysize, y, c); + } + if (GET_CODE (y) == CONST) + return memrefs_conflict_p (xsize, x, ysize, + canon_rtx (XEXP (y, 0)), c); + + if (CONSTANT_P (y)) + return (rtx_equal_for_memref_p (x, y) + && (xsize == 0 || ysize == 0 + || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0))); + + return 1; + } + return 1; +} + +/* Functions to compute memory dependencies. + + Since we process the insns in execution order, we can build tables + to keep track of what registers are fixed (and not aliased), what registers + are varying in known ways, and what registers are varying in unknown + ways. + + If both memory references are volatile, then there must always be a + dependence between the two references, since their order can not be + changed. A volatile and non-volatile reference can be interchanged + though. + + A MEM_IN_STRUCT reference at a varying address can never conflict with a + non-MEM_IN_STRUCT reference at a fixed address. */ + +/* Read dependence: X is read after read in MEM takes place. There can + only be a dependence here if both reads are volatile. */ + +int +read_dependence (mem, x) + rtx mem; + rtx x; +{ + return MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem); +} + +/* True dependence: X is read after store in MEM takes place. */ + +int +true_dependence (mem, x) + rtx mem; + rtx x; +{ + if (RTX_UNCHANGING_P (x)) + return 0; + + return ((MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem)) + || (memrefs_conflict_p (SIZE_FOR_MODE (mem), XEXP (mem, 0), + SIZE_FOR_MODE (x), XEXP (x, 0), 0) + && ! (MEM_IN_STRUCT_P (mem) && rtx_addr_varies_p (mem) + && ! MEM_IN_STRUCT_P (x) && ! rtx_addr_varies_p (x)) + && ! (MEM_IN_STRUCT_P (x) && rtx_addr_varies_p (x) + && ! MEM_IN_STRUCT_P (mem) && ! rtx_addr_varies_p (mem)))); +} + +/* Anti dependence: X is written after read in MEM takes place. */ + +int +anti_dependence (mem, x) + rtx mem; + rtx x; +{ + if (RTX_UNCHANGING_P (mem)) + return 0; + + return ((MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem)) + || (memrefs_conflict_p (SIZE_FOR_MODE (mem), XEXP (mem, 0), + SIZE_FOR_MODE (x), XEXP (x, 0), 0) + && ! (MEM_IN_STRUCT_P (mem) && rtx_addr_varies_p (mem) + && ! MEM_IN_STRUCT_P (x) && ! rtx_addr_varies_p (x)) + && ! (MEM_IN_STRUCT_P (x) && rtx_addr_varies_p (x) + && ! MEM_IN_STRUCT_P (mem) && ! rtx_addr_varies_p (mem)))); +} + +/* Output dependence: X is written after store in MEM takes place. */ + +int +output_dependence (mem, x) + rtx mem; + rtx x; +{ + return ((MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem)) + || (memrefs_conflict_p (SIZE_FOR_MODE (mem), XEXP (mem, 0), + SIZE_FOR_MODE (x), XEXP (x, 0), 0) + && ! (MEM_IN_STRUCT_P (mem) && rtx_addr_varies_p (mem) + && ! MEM_IN_STRUCT_P (x) && ! rtx_addr_varies_p (x)) + && ! (MEM_IN_STRUCT_P (x) && rtx_addr_varies_p (x) + && ! MEM_IN_STRUCT_P (mem) && ! rtx_addr_varies_p (mem)))); +} + +#ifndef INSN_SCHEDULING +void schedule_insns () {} +#else +#ifndef __GNUC__ +#define __inline +#endif + +/* Computation of memory dependencies. */ + +/* The *_insns and *_mems are paired lists. Each pending memory operation + will have a pointer to the MEM rtx on one list and a pointer to the + containing insn on the other list in the same place in the list. */ + +/* We can't use add_dependence like the old code did, because a single insn + may have multiple memory accesses, and hence needs to be on the list + once for each memory access. Add_dependence won't let you add an insn + to a list more than once. */ + +/* An INSN_LIST containing all insns with pending read operations. */ +static rtx pending_read_insns; + +/* An EXPR_LIST containing all MEM rtx's which are pending reads. */ +static rtx pending_read_mems; + +/* An INSN_LIST containing all insns with pending write operations. */ +static rtx pending_write_insns; + +/* An EXPR_LIST containing all MEM rtx's which are pending writes. */ +static rtx pending_write_mems; + +/* Indicates the combined length of the two pending lists. We must prevent + these lists from ever growing too large since the number of dependencies + produced is at least O(N*N), and execution time is at least O(4*N*N), as + a function of the length of these pending lists. */ + +static int pending_lists_length; + +/* An INSN_LIST containing all INSN_LISTs allocated but currently unused. */ + +static rtx unused_insn_list; + +/* An EXPR_LIST containing all EXPR_LISTs allocated but currently unused. */ + +static rtx unused_expr_list; + +/* The last insn upon which all memory references must depend. + This is an insn which flushed the pending lists, creating a dependency + between it and all previously pending memory references. This creates + a barrier (or a checkpoint) which no memory reference is allowed to cross. + + This includes all non constant CALL_INSNs. When we do interprocedural + alias analysis, this restriction can be relaxed. + This may also be an INSN that writes memory if the pending lists grow + too large. */ + +static rtx last_pending_memory_flush; + +/* The last function call we have seen. All hard regs, and, of course, + the last function call, must depend on this. */ + +static rtx last_function_call; + +/* The LOG_LINKS field of this is a list of insns which use a pseudo register + that does not already cross a call. We create dependencies between each + of those insn and the next call insn, to ensure that they won't cross a call + after scheduling is done. */ + +static rtx sched_before_next_call; + +/* Pointer to the last instruction scheduled. Used by rank_for_schedule, + so that insns independent of the last scheduled insn will be preferred + over dependent instructions. */ + +static rtx last_scheduled_insn; + +/* Process an insn's memory dependencies. There are four kinds of + dependencies: + + (0) read dependence: read follows read + (1) true dependence: read follows write + (2) anti dependence: write follows read + (3) output dependence: write follows write + + We are careful to build only dependencies which actually exist, and + use transitivity to avoid building too many links. */ + +/* Return the INSN_LIST containing INSN in LIST, or NULL + if LIST does not contain INSN. */ + +__inline static rtx +find_insn_list (insn, list) + rtx insn; + rtx list; +{ + while (list) + { + if (XEXP (list, 0) == insn) + return list; + list = XEXP (list, 1); + } + return 0; +} + +/* Compute cost of executing INSN. This is the number of virtual + cycles taken between instruction issue and instruction results. */ + +__inline static int +insn_cost (insn) + rtx insn; +{ + register int cost; + + recog_memoized (insn); + + /* A USE insn, or something else we don't need to understand. + We can't pass these directly to result_ready_cost because it will trigger + a fatal error for unrecognizable insns. */ + if (INSN_CODE (insn) < 0) + return 1; + else + { + cost = result_ready_cost (insn); + + if (cost < 1) + cost = 1; + + return cost; + } +} + +/* Compute the priority number for INSN. */ + +static int +priority (insn) + rtx insn; +{ + if (insn && GET_RTX_CLASS (GET_CODE (insn)) == 'i') + { + int prev_priority; + int max_priority; + int this_priority = INSN_PRIORITY (insn); + rtx prev; + + if (this_priority > 0) + return this_priority; + + max_priority = 1; + + /* Nonzero if these insns must be scheduled together. */ + if (SCHED_GROUP_P (insn)) + { + prev = insn; + while (SCHED_GROUP_P (prev)) + { + prev = PREV_INSN (prev); + INSN_REF_COUNT (prev) += 1; + } + } + + for (prev = LOG_LINKS (insn); prev; prev = XEXP (prev, 1)) + { + rtx x = XEXP (prev, 0); + + /* A dependence pointing to a note is always obsolete, because + sched_analyze_insn will have created any necessary new dependences + which replace it. Notes can be created when instructions are + deleted by insn splitting, or by register allocation. */ + if (GET_CODE (x) == NOTE) + { + remove_dependence (insn, x); + continue; + } + + /* This priority calculation was chosen because it results in the + least instruction movement, and does not hurt the performance + of the resulting code compared to the old algorithm. + This makes the sched algorithm more stable, which results + in better code, because there is less register pressure, + cross jumping is more likely to work, and debugging is easier. + + When all instructions have a latency of 1, there is no need to + move any instructions. Subtracting one here ensures that in such + cases all instructions will end up with a priority of one, and + hence no scheduling will be done. + + The original code did not subtract the one, and added the + insn_cost of the current instruction to its priority (e.g. + move the insn_cost call down to the end). */ + + if (REG_NOTE_KIND (prev) == 0) + /* Data dependence. */ + prev_priority = priority (x) + insn_cost (x) - 1; + else + /* Anti or output dependence. Don't add the latency of this + insn's result, because it isn't being used. */ + prev_priority = priority (x); + + if (prev_priority > max_priority) + max_priority = prev_priority; + INSN_REF_COUNT (x) += 1; + } + + INSN_PRIORITY (insn) = max_priority; + return INSN_PRIORITY (insn); + } + return 0; +} + +/* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add + them to the unused_*_list variables, so that they can be reused. */ + +static void +free_pending_lists () +{ + register rtx link, prev_link; + + if (pending_read_insns) + { + prev_link = pending_read_insns; + link = XEXP (prev_link, 1); + + while (link) + { + prev_link = link; + link = XEXP (link, 1); + } + + XEXP (prev_link, 1) = unused_insn_list; + unused_insn_list = pending_read_insns; + pending_read_insns = 0; + } + + if (pending_write_insns) + { + prev_link = pending_write_insns; + link = XEXP (prev_link, 1); + + while (link) + { + prev_link = link; + link = XEXP (link, 1); + } + + XEXP (prev_link, 1) = unused_insn_list; + unused_insn_list = pending_write_insns; + pending_write_insns = 0; + } + + if (pending_read_mems) + { + prev_link = pending_read_mems; + link = XEXP (prev_link, 1); + + while (link) + { + prev_link = link; + link = XEXP (link, 1); + } + + XEXP (prev_link, 1) = unused_expr_list; + unused_expr_list = pending_read_mems; + pending_read_mems = 0; + } + + if (pending_write_mems) + { + prev_link = pending_write_mems; + link = XEXP (prev_link, 1); + + while (link) + { + prev_link = link; + link = XEXP (link, 1); + } + + XEXP (prev_link, 1) = unused_expr_list; + unused_expr_list = pending_write_mems; + pending_write_mems = 0; + } +} + +/* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST. + The MEM is a memory reference contained within INSN, which we are saving + so that we can do memory aliasing on it. */ + +static void +add_insn_mem_dependence (insn_list, mem_list, insn, mem) + rtx *insn_list, *mem_list, insn, mem; +{ + register rtx link; + + if (unused_insn_list) + { + link = unused_insn_list; + unused_insn_list = XEXP (link, 1); + } + else + link = rtx_alloc (INSN_LIST); + XEXP (link, 0) = insn; + XEXP (link, 1) = *insn_list; + *insn_list = link; + + if (unused_expr_list) + { + link = unused_expr_list; + unused_expr_list = XEXP (link, 1); + } + else + link = rtx_alloc (EXPR_LIST); + XEXP (link, 0) = mem; + XEXP (link, 1) = *mem_list; + *mem_list = link; + + pending_lists_length++; +} + +/* Make a dependency between every memory reference on the pending lists + and INSN, thus flushing the pending lists. */ + +static void +flush_pending_lists (insn) + rtx insn; +{ + rtx link; + + while (pending_read_insns) + { + add_dependence (insn, XEXP (pending_read_insns, 0), REG_DEP_ANTI); + + link = pending_read_insns; + pending_read_insns = XEXP (pending_read_insns, 1); + XEXP (link, 1) = unused_insn_list; + unused_insn_list = link; + + link = pending_read_mems; + pending_read_mems = XEXP (pending_read_mems, 1); + XEXP (link, 1) = unused_expr_list; + unused_expr_list = link; + } + while (pending_write_insns) + { + add_dependence (insn, XEXP (pending_write_insns, 0), REG_DEP_ANTI); + + link = pending_write_insns; + pending_write_insns = XEXP (pending_write_insns, 1); + XEXP (link, 1) = unused_insn_list; + unused_insn_list = link; + + link = pending_write_mems; + pending_write_mems = XEXP (pending_write_mems, 1); + XEXP (link, 1) = unused_expr_list; + unused_expr_list = link; + } + pending_lists_length = 0; + + if (last_pending_memory_flush) + add_dependence (insn, last_pending_memory_flush, REG_DEP_ANTI); + + last_pending_memory_flush = insn; +} + +/* Analyze a single SET or CLOBBER rtx, X, creating all dependencies generated + by the write to the destination of X, and reads of everything mentioned. */ + +static void +sched_analyze_1 (x, insn) + rtx x; + rtx insn; +{ + register int regno; + register rtx dest = SET_DEST (x); + + if (dest == 0) + return; + + while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG + || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT) + { + if (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT) + { + /* The second and third arguments are values read by this insn. */ + sched_analyze_2 (XEXP (dest, 1), insn); + sched_analyze_2 (XEXP (dest, 2), insn); + } + dest = SUBREG_REG (dest); + } + + if (GET_CODE (dest) == REG) + { + register int offset, bit, i; + + regno = REGNO (dest); + + /* A hard reg in a wide mode may really be multiple registers. + If so, mark all of them just like the first. */ + if (regno < FIRST_PSEUDO_REGISTER) + { + i = HARD_REGNO_NREGS (regno, GET_MODE (dest)); + while (--i >= 0) + { + rtx u; + + for (u = reg_last_uses[regno+i]; u; u = XEXP (u, 1)) + add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI); + reg_last_uses[regno + i] = 0; + if (reg_last_sets[regno + i]) + add_dependence (insn, reg_last_sets[regno + i], + REG_DEP_OUTPUT); + reg_last_sets[regno + i] = insn; + if ((call_used_regs[i] || global_regs[i]) + && last_function_call) + /* Function calls clobber all call_used regs. */ + add_dependence (insn, last_function_call, REG_DEP_ANTI); + } + } + else + { + rtx u; + + for (u = reg_last_uses[regno]; u; u = XEXP (u, 1)) + add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI); + reg_last_uses[regno] = 0; + if (reg_last_sets[regno]) + add_dependence (insn, reg_last_sets[regno], REG_DEP_OUTPUT); + reg_last_sets[regno] = insn; + + /* Don't let it cross a call after scheduling if it doesn't + already cross one. */ + if (reg_n_calls_crossed[regno] == 0 && last_function_call) + add_dependence (insn, last_function_call, REG_DEP_ANTI); + } + } + else if (GET_CODE (dest) == MEM) + { + /* Writing memory. */ + + if (pending_lists_length > 32) + { + /* Flush all pending reads and writes to prevent the pending lists + from getting any larger. Insn scheduling runs too slowly when + these lists get long. The number 32 was chosen because it + seems like a resonable number. When compiling GCC with itself, + this flush occurs 8 times for sparc, and 10 times for m88k using + the number 32. */ + flush_pending_lists (insn); + } + else + { + rtx pending, pending_mem; + + pending = pending_read_insns; + pending_mem = pending_read_mems; + while (pending) + { + /* If a dependency already exists, don't create a new one. */ + if (! find_insn_list (XEXP (pending, 0), LOG_LINKS (insn))) + if (anti_dependence (XEXP (pending_mem, 0), dest, insn)) + add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI); + + pending = XEXP (pending, 1); + pending_mem = XEXP (pending_mem, 1); + } + + pending = pending_write_insns; + pending_mem = pending_write_mems; + while (pending) + { + /* If a dependency already exists, don't create a new one. */ + if (! find_insn_list (XEXP (pending, 0), LOG_LINKS (insn))) + if (output_dependence (XEXP (pending_mem, 0), dest)) + add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT); + + pending = XEXP (pending, 1); + pending_mem = XEXP (pending_mem, 1); + } + + if (last_pending_memory_flush) + add_dependence (insn, last_pending_memory_flush, REG_DEP_ANTI); + + add_insn_mem_dependence (&pending_write_insns, &pending_write_mems, + insn, dest); + } + sched_analyze_2 (XEXP (dest, 0), insn); + } + + /* Analyze reads. */ + if (GET_CODE (x) == SET) + sched_analyze_2 (SET_SRC (x), insn); + else if (GET_CODE (x) != CLOBBER) + sched_analyze_2 (dest, insn); +} + +/* Analyze the uses of memory and registers in rtx X in INSN. */ + +static void +sched_analyze_2 (x, insn) + rtx x; + rtx insn; +{ + register int i; + register int j; + register enum rtx_code code; + register char *fmt; + + if (x == 0) + return; + + code = GET_CODE (x); + + /* Get rid of the easy cases first. */ + + /* Ignore constants. Note that we must handle CONST_DOUBLE here + because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but + this does not mean that this insn is using cc0. */ + if (code == CONST_INT || code == CONST_DOUBLE || code == SYMBOL_REF + || code == CONST || code == LABEL_REF) + return; + +#ifdef HAVE_cc0 + else if (code == CC0) + { + rtx link; + + /* User of CC0 depends on immediately preceding insn. + All notes are removed from the list of insns to schedule before we + reach here, so the previous insn must be the setter of cc0. */ + if (GET_CODE (PREV_INSN (insn)) != INSN) + abort (); + SCHED_GROUP_P (insn) = 1; + + /* Make a copy of all dependencies on PREV_INSN, and add to this insn. + This is so that all the dependencies will apply to the group. */ + + for (link = LOG_LINKS (PREV_INSN (insn)); link; link = XEXP (link, 1)) + add_dependence (insn, XEXP (link, 0), GET_MODE (link)); + + return; + } +#endif + + else if (code == REG) + { + int regno = REGNO (x); + if (regno < FIRST_PSEUDO_REGISTER) + { + int i; + + i = HARD_REGNO_NREGS (regno, GET_MODE (x)); + while (--i >= 0) + { + reg_last_uses[regno + i] + = gen_rtx (INSN_LIST, VOIDmode, + insn, reg_last_uses[regno + i]); + if (reg_last_sets[regno + i]) + add_dependence (insn, reg_last_sets[regno + i], 0); + if ((call_used_regs[regno + i] || global_regs[regno + i]) + && last_function_call) + /* Function calls clobber all call_used regs. */ + add_dependence (insn, last_function_call, REG_DEP_ANTI); + } + } + else + { + reg_last_uses[regno] + = gen_rtx (INSN_LIST, VOIDmode, insn, reg_last_uses[regno]); + if (reg_last_sets[regno]) + add_dependence (insn, reg_last_sets[regno], 0); + + /* If the register does not already cross any calls, then add this + insn to the sched_before_next_call list so that it will still + not cross calls after scheduling. */ + if (reg_n_calls_crossed[regno] == 0) + add_dependence (sched_before_next_call, insn, REG_DEP_ANTI); + } + return; + } + + /* The interesting case. */ + else if (code == MEM) + { + /* Reading memory. */ + + /* Don't create a dependence for memory references which are known to + be unchanging, such as constant pool accesses. These will never + conflict with any other memory access. */ + if (RTX_UNCHANGING_P (x) == 0) + { + rtx pending, pending_mem; + + pending = pending_read_insns; + pending_mem = pending_read_mems; + while (pending) + { + /* If a dependency already exists, don't create a new one. */ + if (! find_insn_list (XEXP (pending, 0), LOG_LINKS (insn))) + if (read_dependence (XEXP (pending_mem, 0), x)) + add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI); + + pending = XEXP (pending, 1); + pending_mem = XEXP (pending_mem, 1); + } + + pending = pending_write_insns; + pending_mem = pending_write_mems; + while (pending) + { + /* If a dependency already exists, don't create a new one. */ + if (! find_insn_list (XEXP (pending, 0), LOG_LINKS (insn))) + if (true_dependence (XEXP (pending_mem, 0), x)) + add_dependence (insn, XEXP (pending, 0), 0); + + pending = XEXP (pending, 1); + pending_mem = XEXP (pending_mem, 1); + } + if (last_pending_memory_flush) + add_dependence (insn, last_pending_memory_flush, REG_DEP_ANTI); + + /* Always add these dependencies to pending_reads, since + this insn may be followed by a write. */ + add_insn_mem_dependence (&pending_read_insns, &pending_read_mems, + insn, x); + } + /* Take advantage of tail recursion here. */ + sched_analyze_2 (XEXP (x, 0), insn); + return; + } + + else if (code == ASM_OPERANDS || code == ASM_INPUT + || code == UNSPEC_VOLATILE) + { + rtx u; + + /* Traditional and volatile asm instructions must be considered to use + and clobber all hard registers and all of memory. So must + UNSPEC_VOLATILE operations. */ + if ((code == ASM_OPERANDS && MEM_VOLATILE_P (x)) || code == ASM_INPUT + || code == UNSPEC_VOLATILE) + { + for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) + { + for (u = reg_last_uses[i]; u; u = XEXP (u, 1)) + if (GET_CODE (PATTERN (XEXP (u, 0))) != USE) + add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI); + reg_last_uses[i] = 0; + if (reg_last_sets[i] + && GET_CODE (PATTERN (reg_last_sets[i])) != USE) + add_dependence (insn, reg_last_sets[i], 0); + reg_last_sets[i] = insn; + } + + flush_pending_lists (insn); + } + + /* For all ASM_OPERANDS, we must traverse the vector of input operands. + We can not just fall through here since then we would be confused + by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate + traditional asms unlike their normal usage. */ + + if (code == ASM_OPERANDS) + { + for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++) + sched_analyze_2 (ASM_OPERANDS_INPUT (x, j), insn); + return; + } + } + + /* Other cases: walk the insn. */ + fmt = GET_RTX_FORMAT (code); + for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) + { + if (fmt[i] == 'e') + sched_analyze_2 (XEXP (x, i), insn); + else if (fmt[i] == 'E') + for (j = 0; j < XVECLEN (x, i); j++) + sched_analyze_2 (XVECEXP (x, i, j), insn); + } +} + +/* Analyze an INSN with pattern X to find all dependencies. */ + +static void +sched_analyze_insn (x, insn) + rtx x, insn; +{ + register RTX_CODE code = GET_CODE (x); + rtx link; + + if (code == SET || code == CLOBBER) + sched_analyze_1 (x, insn); + else if (code == PARALLEL) + { + register int i; + for (i = XVECLEN (x, 0) - 1; i >= 0; i--) + { + code = GET_CODE (XVECEXP (x, 0, i)); + if (code == SET || code == CLOBBER) + sched_analyze_1 (XVECEXP (x, 0, i), insn); + else + sched_analyze_2 (XVECEXP (x, 0, i), insn); + } + } + else + sched_analyze_2 (x, insn); + + for (link = REG_NOTES (insn); link; link = XEXP (link, 1)) + { + /* Any REG_INC note is a SET of the register indicated. */ + if (REG_NOTE_KIND (link) == REG_INC) + { + rtx dest = XEXP (link, 0); + int regno = REGNO (dest); + int i; + + /* A hard reg in a wide mode may really be multiple registers. + If so, mark all of them just like the first. */ + if (regno < FIRST_PSEUDO_REGISTER) + { + i = HARD_REGNO_NREGS (regno, GET_MODE (dest)); + while (--i >= 0) + { + rtx u; + + for (u = reg_last_uses[regno+i]; u; u = XEXP (u, 1)) + add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI); + reg_last_uses[regno + i] = 0; + if (reg_last_sets[regno + i]) + add_dependence (insn, reg_last_sets[regno + i], + REG_DEP_OUTPUT); + reg_last_sets[regno + i] = insn; + if ((call_used_regs[i] || global_regs[i]) + && last_function_call) + /* Function calls clobber all call_used regs. */ + add_dependence (insn, last_function_call, REG_DEP_ANTI); + } + } + else + { + rtx u; + + for (u = reg_last_uses[regno]; u; u = XEXP (u, 1)) + add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI); + reg_last_uses[regno] = 0; + if (reg_last_sets[regno]) + add_dependence (insn, reg_last_sets[regno], REG_DEP_OUTPUT); + reg_last_sets[regno] = insn; + + /* Don't let it cross a call after scheduling if it doesn't + already cross one. */ + if (reg_n_calls_crossed[regno] == 0 && last_function_call) + add_dependence (insn, last_function_call, 0); + } + } + } + + /* Handle function calls. */ + if (GET_CODE (insn) == CALL_INSN) + { + rtx dep_insn; + rtx prev_dep_insn; + + /* When scheduling instructions, we make sure calls don't lose their + accompanying USE insns by depending them one on another in order. */ + + prev_dep_insn = insn; + dep_insn = PREV_INSN (insn); + while (GET_CODE (dep_insn) == INSN + && GET_CODE (PATTERN (dep_insn)) == USE) + { + SCHED_GROUP_P (prev_dep_insn) = 1; + + /* Make a copy of all dependencies on dep_insn, and add to insn. + This is so that all of the dependencies will apply to the + group. */ + + for (link = LOG_LINKS (dep_insn); link; link = XEXP (link, 1)) + add_dependence (insn, XEXP (link, 0), GET_MODE (link)); + + prev_dep_insn = dep_insn; + dep_insn = PREV_INSN (dep_insn); + } + } +} + +/* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS + for every dependency. */ + +static int +sched_analyze (head, tail) + rtx head, tail; +{ + register rtx insn; + register int n_insns = 0; + register rtx u; + register int luid = 0; + + for (insn = head; ; insn = NEXT_INSN (insn)) + { + INSN_LUID (insn) = luid++; + + if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN) + { + sched_analyze_insn (PATTERN (insn), insn); + n_insns += 1; + } + else if (GET_CODE (insn) == CALL_INSN) + { + rtx dest = 0; + rtx x; + register int i; + + /* Any instruction using a hard register which may get clobbered + by a call needs to be marked as dependent on this call. + This prevents a use of a hard return reg from being moved + past a void call (i.e. it does not explicitly set the hard + return reg). */ + + for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) + if (call_used_regs[i] || global_regs[i]) + { + for (u = reg_last_uses[i]; u; u = XEXP (u, 1)) + if (GET_CODE (PATTERN (XEXP (u, 0))) != USE) + add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI); + reg_last_uses[i] = 0; + if (reg_last_sets[i] + && GET_CODE (PATTERN (reg_last_sets[i])) != USE) + add_dependence (insn, reg_last_sets[i], REG_DEP_ANTI); + reg_last_sets[i] = insn; + /* Insn, being a CALL_INSN, magically depends on + `last_function_call' already. */ + } + + /* For each insn which shouldn't cross a call, add a dependence + between that insn and this call insn. */ + x = LOG_LINKS (sched_before_next_call); + while (x) + { + add_dependence (insn, XEXP (x, 0), REG_DEP_ANTI); + x = XEXP (x, 1); + } + LOG_LINKS (sched_before_next_call) = 0; + + sched_analyze_insn (PATTERN (insn), insn); + + /* We don't need to flush memory for a function call which does + not involve memory. */ + if (! CONST_CALL_P (insn)) + { + /* In the absence of interprocedural alias analysis, + we must flush all pending reads and writes, and + start new dependencies starting from here. */ + flush_pending_lists (insn); + } + + /* Depend this function call (actually, the user of this + function call) on all hard register clobberage. */ + last_function_call = insn; + n_insns += 1; + } + + if (insn == tail) + return n_insns; + } +} + +/* Called when we see a set of a register. If death is true, then we are + scanning backwards. Mark that register as unborn. If nobody says + otherwise, that is how things will remain. If death is false, then we + are scanning forwards. Mark that register as being born. */ + +static void +sched_note_set (b, x, death) + int b; + rtx x; + int death; +{ + register int regno, j; + register rtx reg = SET_DEST (x); + int subreg_p = 0; + + if (reg == 0) + return; + + while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == STRICT_LOW_PART + || GET_CODE (reg) == SIGN_EXTRACT || GET_CODE (reg) == ZERO_EXTRACT) + { + /* Must treat modification of just one hardware register of a multi-reg + value or just a byte field of a register exactly the same way that + mark_set_1 in flow.c does. */ + if (GET_CODE (reg) == ZERO_EXTRACT + || GET_CODE (reg) == SIGN_EXTRACT + || (GET_CODE (reg) == SUBREG + && REG_SIZE (SUBREG_REG (reg)) > REG_SIZE (reg))) + subreg_p = 1; + + reg = SUBREG_REG (reg); + } + + if (GET_CODE (reg) != REG) + return; + + /* Global registers are always live, so the code below does not apply + to them. */ + + regno = REGNO (reg); + if (regno >= FIRST_PSEUDO_REGISTER || ! global_regs[regno]) + { + register int offset = regno / REGSET_ELT_BITS; + register int bit = 1 << (regno % REGSET_ELT_BITS); + + if (death) + { + /* If we only set part of the register, then this set does not + kill it. */ + if (subreg_p) + return; + + /* Try killing this register. */ + if (regno < FIRST_PSEUDO_REGISTER) + { + int j = HARD_REGNO_NREGS (regno, GET_MODE (reg)); + while (--j >= 0) + { + offset = (regno + j) / REGSET_ELT_BITS; + bit = 1 << ((regno + j) % REGSET_ELT_BITS); + + bb_live_regs[offset] &= ~bit; + bb_dead_regs[offset] |= bit; + } + } + else + { + bb_live_regs[offset] &= ~bit; + bb_dead_regs[offset] |= bit; + } + } + else + { + /* Make the register live again. */ + if (regno < FIRST_PSEUDO_REGISTER) + { + int j = HARD_REGNO_NREGS (regno, GET_MODE (reg)); + while (--j >= 0) + { + offset = (regno + j) / REGSET_ELT_BITS; + bit = 1 << ((regno + j) % REGSET_ELT_BITS); + + bb_live_regs[offset] |= bit; + bb_dead_regs[offset] &= ~bit; + } + } + else + { + bb_live_regs[offset] |= bit; + bb_dead_regs[offset] &= ~bit; + } + } + } +} + +/* Macros and functions for keeping the priority queue sorted, and + dealing with queueing and unqueueing of instructions. */ + +#define SCHED_SORT(READY, NEW_READY, OLD_READY) \ + do { if ((NEW_READY) - (OLD_READY) == 1) \ + swap_sort (READY, NEW_READY); \ + else if ((NEW_READY) - (OLD_READY) > 1) \ + qsort (READY, NEW_READY, sizeof (rtx), rank_for_schedule); } \ + while (0) + +/* Returns a positive value if y is preferred; returns a negative value if + x is preferred. Should never return 0, since that will make the sort + unstable. */ + +static int +rank_for_schedule (x, y) + rtx *x, *y; +{ + rtx tmp = *y; + rtx tmp2 = *x; + rtx tmp_dep, tmp2_dep; + int tmp_class, tmp2_class; + int value; + + /* Choose the instruction with the highest priority, if different. */ + if (value = INSN_PRIORITY (tmp) - INSN_PRIORITY (tmp2)) + return value; + + if (last_scheduled_insn) + { + /* Classify the instructions into three classes: + 1) Data dependent on last schedule insn. + 2) Anti/Output dependent on last scheduled insn. + 3) Independent of last scheduled insn, or has latency of one. + Choose the insn from the highest numbered class if different. */ + tmp_dep = find_insn_list (tmp, LOG_LINKS (last_scheduled_insn)); + if (tmp_dep == 0 || insn_cost (tmp) == 1) + tmp_class = 3; + else if (REG_NOTE_KIND (tmp_dep) == 0) + tmp_class = 1; + else + tmp_class = 2; + + tmp2_dep = find_insn_list (tmp2, LOG_LINKS (last_scheduled_insn)); + if (tmp2_dep == 0 || insn_cost (tmp2) == 1) + tmp2_class = 3; + else if (REG_NOTE_KIND (tmp2_dep) == 0) + tmp2_class = 1; + else + tmp2_class = 2; + + if (value = tmp_class - tmp2_class) + return value; + } + + /* If insns are equally good, sort by INSN_LUID (original insn order), + so that we make the sort stable. This minimizes instruction movement, + thus minimizing sched's effect on debugging and cross-jumping. */ + return INSN_LUID (tmp) - INSN_LUID (tmp2); +} + +/* Resort the array A in which only element at index N may be out of order. */ + +__inline static void +swap_sort (a, n) + rtx *a; + int n; +{ + rtx insn = a[n-1]; + int i = n-2; + + while (i >= 0 && rank_for_schedule (a+i, &insn) >= 0) + { + a[i+1] = a[i]; + i -= 1; + } + a[i+1] = insn; +} + +static int max_priority; + +/* Add INSN to the insn queue so that it fires at least N_CYCLES + before the currently executing insn. */ + +__inline static void +queue_insn (insn, n_cycles) + rtx insn; + int n_cycles; +{ + int next_q = NEXT_Q_AFTER (q_ptr, n_cycles); + NEXT_INSN (insn) = insn_queue[next_q]; + insn_queue[next_q] = insn; + q_size += 1; +} + +/* Return nonzero if PAT is the pattern of an insn which makes a + register live. */ + +__inline static int +birthing_insn_p (pat) + rtx pat; +{ + int j; + + if (reload_completed == 1) + return 0; + + if (GET_CODE (pat) == SET + && GET_CODE (SET_DEST (pat)) == REG) + { + rtx dest = SET_DEST (pat); + int i = REGNO (dest); + int offset = i / REGSET_ELT_BITS; + int bit = 1 << (i % REGSET_ELT_BITS); + + /* It would be more accurate to use refers_to_regno_p or + reg_mentioned_p to determine when the dest is not live before this + insn. */ + + if (bb_live_regs[offset] & bit) + return (reg_n_sets[i] == 1); + + return 0; + } + if (GET_CODE (pat) == PARALLEL) + { + for (j = 0; j < XVECLEN (pat, 0); j++) + if (birthing_insn_p (XVECEXP (pat, 0, j))) + return 1; + } + return 0; +} + +/* If PREV is an insn which is immediately ready to execute, return 1, + otherwise return 0. We may adjust its priority if that will help shorten + register lifetimes. */ + +static int +launch_link (prev) + rtx prev; +{ + rtx pat = PATTERN (prev); + rtx note; + /* MAX of (a) number of cycles needed by prev + (b) number of cycles before needed resources are free. */ + int n_cycles = insn_cost (prev); + int n_deaths = 0; + + /* Trying to shorten register lives after reload has completed + is useless and wrong. It gives inaccurate schedules. */ + if (reload_completed == 0) + { + for (note = REG_NOTES (prev); note; note = XEXP (note, 1)) + if (REG_NOTE_KIND (note) == REG_DEAD) + n_deaths += 1; + + /* Defer scheduling insns which kill registers, since that + shortens register lives. Prefer scheduling insns which + make registers live for the same reason. */ + switch (n_deaths) + { + default: + INSN_PRIORITY (prev) >>= 3; + break; + case 3: + INSN_PRIORITY (prev) >>= 2; + break; + case 2: + case 1: + INSN_PRIORITY (prev) >>= 1; + break; + case 0: + if (birthing_insn_p (pat)) + { + int max = max_priority; + + if (max > INSN_PRIORITY (prev)) + INSN_PRIORITY (prev) = max; + } + break; + } + } + + if (n_cycles <= 1) + return 1; + queue_insn (prev, n_cycles); + return 0; +} + +/* INSN is the "currently executing insn". Launch each insn which was + waiting on INSN (in the backwards dataflow sense). READY is a + vector of insns which are ready to fire. N_READY is the number of + elements in READY. */ + +static int +launch_links (insn, ready, n_ready) + rtx insn; + rtx *ready; + int n_ready; +{ + rtx link; + int new_ready = n_ready; + + if (LOG_LINKS (insn) == 0) + return n_ready; + + /* This is used by the function launch_link above. */ + if (n_ready > 0) + max_priority = MAX (INSN_PRIORITY (ready[0]), INSN_PRIORITY (insn)); + else + max_priority = INSN_PRIORITY (insn); + + for (link = LOG_LINKS (insn); link != 0; link = XEXP (link, 1)) + { + rtx prev = XEXP (link, 0); + + if ((INSN_REF_COUNT (prev) -= 1) == 0 && launch_link (prev)) + ready[new_ready++] = prev; + } + + return new_ready; +} + +/* Add a REG_DEAD note for REG to INSN, reusing a REG_DEAD note from the + dead_notes list. */ + +static void +create_reg_dead_note (reg, insn) + rtx reg, insn; +{ + rtx link = dead_notes; + + if (link == 0) + /* In theory, we should not end up with more REG_DEAD reg notes than we + started with. In practice, this can occur as the result of bugs in + flow, combine and/or sched. */ + { +#if 1 + abort (); +#else + link = rtx_alloc (EXPR_LIST); + PUT_REG_NOTE_KIND (link, REG_DEAD); +#endif + } + else + dead_notes = XEXP (dead_notes, 1); + + XEXP (link, 0) = reg; + XEXP (link, 1) = REG_NOTES (insn); + REG_NOTES (insn) = link; +} + +/* Subroutine on attach_deaths_insn--handles the recursive search + through INSN. If SET_P is true, then x is being modified by the insn. */ + +static void +attach_deaths (x, insn, set_p) + rtx x; + rtx insn; + int set_p; +{ + register int i; + register int j; + register enum rtx_code code; + register char *fmt; + + if (x == 0) + return; + + code = GET_CODE (x); + + switch (code) + { + case CONST_INT: + case CONST_DOUBLE: + case LABEL_REF: + case SYMBOL_REF: + case CONST: + case CODE_LABEL: + case PC: + case CC0: + /* Get rid of the easy cases first. */ + return; + + case REG: + { + /* If the register dies in this insn, queue that note, and mark + this register as needing to die. */ + /* This code is very similar to mark_used_1 (if set_p is false) + and mark_set_1 (if set_p is true) in flow.c. */ + + register int regno = REGNO (x); + register int offset = regno / REGSET_ELT_BITS; + register int bit = 1 << (regno % REGSET_ELT_BITS); + int all_needed = (old_live_regs[offset] & bit); + int some_needed = (old_live_regs[offset] & bit); + + if (set_p) + return; + + if (regno < FIRST_PSEUDO_REGISTER) + { + int n; + + n = HARD_REGNO_NREGS (regno, GET_MODE (x)); + while (--n > 0) + { + some_needed |= (old_live_regs[(regno + n) / REGSET_ELT_BITS] + & 1 << ((regno + n) % REGSET_ELT_BITS)); + all_needed &= (old_live_regs[(regno + n) / REGSET_ELT_BITS] + & 1 << ((regno + n) % REGSET_ELT_BITS)); + } + } + + /* If it wasn't live before we started, then add a REG_DEAD note. + We must check the previous lifetime info not the current info, + because we may have to execute this code several times, e.g. + once for a clobber (which doesn't add a note) and later + for a use (which does add a note). + + Always make the register live. We must do this even if it was + live before, because this may be an insn which sets and uses + the same register, in which case the register has already been + killed, so we must make it live again. + + Global registers are always live, and should never have a REG_DEAD + note added for them, so none of the code below applies to them. */ + + if (regno >= FIRST_PSEUDO_REGISTER || ! global_regs[regno]) + { + /* Never add REG_DEAD notes for the FRAME_POINTER_REGNUM or the + STACK_POINTER_REGNUM, since these are always considered to be + live. Similarly for ARG_POINTER_REGNUM if it is fixed. */ + if (regno != FRAME_POINTER_REGNUM +#if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM + && ! (regno == ARG_POINTER_REGNUM && fixed_regs[regno]) +#endif +#ifdef PIC_OFFSET_TABLE_REGNUM + && ! (regno == PIC_OFFSET_TABLE_REGNUM && flag_pic) +#endif + && regno != STACK_POINTER_REGNUM) + { + if (! all_needed && ! dead_or_set_p (insn, x)) + { + /* If none of the words in X is needed, make a REG_DEAD + note. Otherwise, we must make partial REG_DEAD + notes. */ + if (! some_needed) + create_reg_dead_note (x, insn); + else + { + int i; + + /* Don't make a REG_DEAD note for a part of a + register that is set in the insn. */ + for (i = HARD_REGNO_NREGS (regno, GET_MODE (x)) - 1; + i >= 0; i--) + if ((old_live_regs[(regno + i) / REGSET_ELT_BITS] + & 1 << ((regno +i) % REGSET_ELT_BITS)) == 0 + && ! dead_or_set_regno_p (insn, regno + i)) + create_reg_dead_note (gen_rtx (REG, word_mode, + regno + i), + insn); + } + } + } + + if (regno < FIRST_PSEUDO_REGISTER) + { + int j = HARD_REGNO_NREGS (regno, GET_MODE (x)); + while (--j >= 0) + { + offset = (regno + j) / REGSET_ELT_BITS; + bit = 1 << ((regno + j) % REGSET_ELT_BITS); + + bb_dead_regs[offset] &= ~bit; + bb_live_regs[offset] |= bit; + } + } + else + { + bb_dead_regs[offset] &= ~bit; + bb_live_regs[offset] |= bit; + } + } + return; + } + + case MEM: + /* Handle tail-recursive case. */ + attach_deaths (XEXP (x, 0), insn, 0); + return; + + case SUBREG: + case STRICT_LOW_PART: + /* These two cases preserve the value of SET_P, so handle them + separately. */ + attach_deaths (XEXP (x, 0), insn, set_p); + return; + + case ZERO_EXTRACT: + case SIGN_EXTRACT: + /* This case preserves the value of SET_P for the first operand, but + clears it for the other two. */ + attach_deaths (XEXP (x, 0), insn, set_p); + attach_deaths (XEXP (x, 1), insn, 0); + attach_deaths (XEXP (x, 2), insn, 0); + return; + + default: + /* Other cases: walk the insn. */ + fmt = GET_RTX_FORMAT (code); + for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) + { + if (fmt[i] == 'e') + attach_deaths (XEXP (x, i), insn, 0); + else if (fmt[i] == 'E') + for (j = 0; j < XVECLEN (x, i); j++) + attach_deaths (XVECEXP (x, i, j), insn, 0); + } + } +} + +/* After INSN has executed, add register death notes for each register + that is dead after INSN. */ + +static void +attach_deaths_insn (insn) + rtx insn; +{ + rtx x = PATTERN (insn); + register RTX_CODE code = GET_CODE (x); + + if (code == SET) + { + attach_deaths (SET_SRC (x), insn, 0); + + /* A register might die here even if it is the destination, e.g. + it is the target of a volatile read and is otherwise unused. + Hence we must always call attach_deaths for the SET_DEST. */ + attach_deaths (SET_DEST (x), insn, 1); + } + else if (code == PARALLEL) + { + register int i; + for (i = XVECLEN (x, 0) - 1; i >= 0; i--) + { + code = GET_CODE (XVECEXP (x, 0, i)); + if (code == SET) + { + attach_deaths (SET_SRC (XVECEXP (x, 0, i)), insn, 0); + + attach_deaths (SET_DEST (XVECEXP (x, 0, i)), insn, 1); + } + else if (code == CLOBBER) + attach_deaths (XEXP (XVECEXP (x, 0, i), 0), insn, 1); + else + attach_deaths (XVECEXP (x, 0, i), insn, 0); + } + } + else if (code == CLOBBER) + attach_deaths (XEXP (x, 0), insn, 1); + else + attach_deaths (x, insn, 0); +} + +/* Delete notes beginning with INSN and maybe put them in the chain + of notes ended by NOTE_LIST. + Returns the insn following the notes. */ + +static rtx +unlink_notes (insn, tail) + rtx insn, tail; +{ + rtx prev = PREV_INSN (insn); + + while (insn != tail && GET_CODE (insn) == NOTE) + { + rtx next = NEXT_INSN (insn); + /* Delete the note from its current position. */ + if (prev) + NEXT_INSN (prev) = next; + if (next) + PREV_INSN (next) = prev; + + if (write_symbols != NO_DEBUG && NOTE_LINE_NUMBER (insn) > 0) + /* Record line-number notes so they can be reused. */ + LINE_NOTE (insn) = insn; + else + { + /* Insert the note at the end of the notes list. */ + PREV_INSN (insn) = note_list; + if (note_list) + NEXT_INSN (note_list) = insn; + note_list = insn; + } + + insn = next; + } + return insn; +} + +/* Data structure for keeping track of register information + during that register's life. */ + +struct sometimes +{ + short offset; short bit; + short live_length; short calls_crossed; +}; + +/* Constructor for `sometimes' data structure. */ + +static int +new_sometimes_live (regs_sometimes_live, offset, bit, sometimes_max) + struct sometimes *regs_sometimes_live; + int offset, bit; + int sometimes_max; +{ + register struct sometimes *p; + register int regno = offset * REGSET_ELT_BITS + bit; + int i; + + /* There should never be a register greater than max_regno here. If there + is, it means that a define_split has created a new pseudo reg. This + is not allowed, since there will not be flow info available for any + new register, so catch the error here. */ + if (regno >= max_regno) + abort (); + + p = ®s_sometimes_live[sometimes_max]; + p->offset = offset; + p->bit = bit; + p->live_length = 0; + p->calls_crossed = 0; + sometimes_max++; + return sometimes_max; +} + +/* Count lengths of all regs we are currently tracking, + and find new registers no longer live. */ + +static void +finish_sometimes_live (regs_sometimes_live, sometimes_max) + struct sometimes *regs_sometimes_live; + int sometimes_max; +{ + int i; + + for (i = 0; i < sometimes_max; i++) + { + register struct sometimes *p = ®s_sometimes_live[i]; + int regno; + + regno = p->offset * REGSET_ELT_BITS + p->bit; + + sched_reg_live_length[regno] += p->live_length; + sched_reg_n_calls_crossed[regno] += p->calls_crossed; + } +} + +/* Use modified list scheduling to rearrange insns in basic block + B. FILE, if nonzero, is where we dump interesting output about + this pass. */ + +static void +schedule_block (b, file) + int b; + FILE *file; +{ + rtx insn, last; + rtx last_note = 0; + rtx *ready, link; + int i, j, n_ready = 0, new_ready, n_insns = 0; + int sched_n_insns = 0; +#define NEED_NOTHING 0 +#define NEED_HEAD 1 +#define NEED_TAIL 2 + int new_needs; + + /* HEAD and TAIL delimit the region being scheduled. */ + rtx head = basic_block_head[b]; + rtx tail = basic_block_end[b]; + /* PREV_HEAD and NEXT_TAIL are the boundaries of the insns + being scheduled. When the insns have been ordered, + these insns delimit where the new insns are to be + spliced back into the insn chain. */ + rtx next_tail; + rtx prev_head; + + /* Keep life information accurate. */ + register struct sometimes *regs_sometimes_live; + int sometimes_max; + + if (file) + fprintf (file, ";;\t -- basic block number %d from %d to %d --\n", + b, INSN_UID (basic_block_head[b]), INSN_UID (basic_block_end[b])); + + i = max_reg_num (); + reg_last_uses = (rtx *) alloca (i * sizeof (rtx)); + bzero (reg_last_uses, i * sizeof (rtx)); + reg_last_sets = (rtx *) alloca (i * sizeof (rtx)); + bzero (reg_last_sets, i * sizeof (rtx)); + + /* Remove certain insns at the beginning from scheduling, + by advancing HEAD. */ + + /* At the start of a function, before reload has run, don't delay getting + parameters from hard registers into pseudo registers. */ + if (reload_completed == 0 && b == 0) + { + while (head != tail + && GET_CODE (head) == NOTE + && NOTE_LINE_NUMBER (head) != NOTE_INSN_FUNCTION_BEG) + head = NEXT_INSN (head); + while (head != tail + && GET_CODE (head) == INSN + && GET_CODE (PATTERN (head)) == SET) + { + rtx src = SET_SRC (PATTERN (head)); + while (GET_CODE (src) == SUBREG + || GET_CODE (src) == SIGN_EXTEND + || GET_CODE (src) == ZERO_EXTEND + || GET_CODE (src) == SIGN_EXTRACT + || GET_CODE (src) == ZERO_EXTRACT) + src = XEXP (src, 0); + if (GET_CODE (src) != REG + || REGNO (src) >= FIRST_PSEUDO_REGISTER) + break; + /* Keep this insn from ever being scheduled. */ + INSN_REF_COUNT (head) = 1; + head = NEXT_INSN (head); + } + } + + /* Don't include any notes or labels at the beginning of the + basic block, or notes at the ends of basic blocks. */ + while (head != tail) + { + if (GET_CODE (head) == NOTE) + head = NEXT_INSN (head); + else if (GET_CODE (tail) == NOTE) + tail = PREV_INSN (tail); + else if (GET_CODE (head) == CODE_LABEL) + head = NEXT_INSN (head); + else break; + } + /* If the only insn left is a NOTE or a CODE_LABEL, then there is no need + to schedule this block. */ + if (head == tail + && (GET_CODE (head) == NOTE || GET_CODE (head) == CODE_LABEL)) + return; + +#if 0 + /* This short-cut doesn't work. It does not count call insns crossed by + registers in reg_sometimes_live. It does not mark these registers as + dead if they die in this block. It does not mark these registers live + (or create new reg_sometimes_live entries if necessary) if they are born + in this block. + + The easy solution is to just always schedule a block. This block only + has one insn, so this won't slow down this pass by much. */ + + if (head == tail) + return; +#endif + + /* Exclude certain insns at the end of the basic block by advancing TAIL. */ + /* This isn't correct. Instead of advancing TAIL, should assign very + high priorities to these insns to guarantee that they get scheduled last. + If these insns are ignored, as is currently done, the register life info + may be incorrectly computed. */ + if (GET_CODE (tail) == INSN + && GET_CODE (PATTERN (tail)) == USE + && next_nonnote_insn (tail) == 0) + { + /* If this was the only insn in the block, then there are no insns to + schedule. */ + if (head == tail) + return; + + /* We don't try to reorder the USE at the end of a function. */ + tail = prev_nonnote_insn (tail); + +#if 0 + /* This short-cut does not work. See comment above. */ + if (head == tail) + return; +#endif + } + else if (GET_CODE (tail) == JUMP_INSN + && SCHED_GROUP_P (tail) == 0 + && GET_CODE (PREV_INSN (tail)) == INSN + && GET_CODE (PATTERN (PREV_INSN (tail))) == USE + && REG_FUNCTION_VALUE_P (XEXP (PATTERN (PREV_INSN (tail)), 0))) + { + /* Don't let the setting of the function's return value register + move from this jump. For the same reason we want to get the + parameters into pseudo registers as quickly as possible, we + want to set the function's return value register as late as + possible. */ + + /* If this is the only insn in the block, then there is no need to + schedule the block. */ + if (head == tail) + return; + + tail = PREV_INSN (tail); + if (head == tail) + return; + + tail = prev_nonnote_insn (tail); + +#if 0 + /* This shortcut does not work. See comment above. */ + if (head == tail) + return; +#endif + } + +#ifdef HAVE_cc0 + /* This is probably wrong. Instead of doing this, should give this insn + a very high priority to guarantee that it gets scheduled last. */ + /* Can not separate an insn that sets the condition code from one that + uses it. So we must leave an insn that sets cc0 where it is. */ + if (sets_cc0_p (PATTERN (tail))) + tail = PREV_INSN (tail); +#endif + + /* Now HEAD through TAIL are the insns actually to be rearranged; + Let PREV_HEAD and NEXT_TAIL enclose them. */ + prev_head = PREV_INSN (head); + next_tail = NEXT_INSN (tail); + + /* Initialize basic block data structures. */ + dead_notes = 0; + pending_read_insns = 0; + pending_read_mems = 0; + pending_write_insns = 0; + pending_write_mems = 0; + pending_lists_length = 0; + last_pending_memory_flush = 0; + last_function_call = 0; + last_scheduled_insn = 0; + + LOG_LINKS (sched_before_next_call) = 0; + + n_insns += sched_analyze (head, tail); + if (n_insns == 0) + { + free_pending_lists (); + return; + } + + /* Allocate vector to hold insns to be rearranged (except those + insns which are controlled by an insn with SCHED_GROUP_P set). + All these insns are included between ORIG_HEAD and ORIG_TAIL, + as those variables ultimately are set up. */ + ready = (rtx *) alloca ((n_insns+1) * sizeof (rtx)); + + /* TAIL is now the last of the insns to be rearranged. + Put those insns into the READY vector. */ + insn = tail; + + /* If the last insn is a branch, force it to be the last insn after + scheduling. Also, don't try to reorder calls at the ends the basic + block -- this will only lead to worse register allocation. */ + if (GET_CODE (tail) == CALL_INSN || GET_CODE (tail) == JUMP_INSN) + { + priority (tail); + ready[n_ready++] = tail; + INSN_PRIORITY (tail) = TAIL_PRIORITY; + INSN_REF_COUNT (tail) = 0; + insn = PREV_INSN (tail); + } + + /* Assign priorities to instructions. Also check whether they + are in priority order already. If so then I will be nonnegative. + We use this shortcut only before reloading. */ +#if 0 + i = reload_completed ? DONE_PRIORITY : MAX_PRIORITY; +#endif + + for (; insn != prev_head; insn = PREV_INSN (insn)) + { + if (GET_RTX_CLASS (GET_CODE (insn)) == 'i') + { + priority (insn); + if (INSN_REF_COUNT (insn) == 0) + ready[n_ready++] = insn; + if (SCHED_GROUP_P (insn)) + { + while (SCHED_GROUP_P (insn)) + { + insn = PREV_INSN (insn); + while (GET_CODE (insn) == NOTE) + insn = PREV_INSN (insn); + priority (insn); + } + continue; + } +#if 0 + if (i < 0) + continue; + if (INSN_PRIORITY (insn) < i) + i = INSN_PRIORITY (insn); + else if (INSN_PRIORITY (insn) > i) + i = DONE_PRIORITY; +#endif + } + } + +#if 0 + /* This short-cut doesn't work. It does not count call insns crossed by + registers in reg_sometimes_live. It does not mark these registers as + dead if they die in this block. It does not mark these registers live + (or create new reg_sometimes_live entries if necessary) if they are born + in this block. + + The easy solution is to just always schedule a block. These blocks tend + to be very short, so this doesn't slow down this pass by much. */ + + /* If existing order is good, don't bother to reorder. */ + if (i != DONE_PRIORITY) + { + if (file) + fprintf (file, ";; already scheduled\n"); + + if (reload_completed == 0) + { + for (i = 0; i < sometimes_max; i++) + regs_sometimes_live[i].live_length += n_insns; + + finish_sometimes_live (regs_sometimes_live, sometimes_max); + } + free_pending_lists (); + return; + } +#endif + + /* Scan all the insns to be scheduled, removing NOTE insns + and register death notes. + Line number NOTE insns end up in NOTE_LIST. + Register death notes end up in DEAD_NOTES. + + Recreate the register life information for the end of this basic + block. */ + + if (reload_completed == 0) + { + bcopy (basic_block_live_at_start[b], bb_live_regs, regset_bytes); + bzero (bb_dead_regs, regset_bytes); + + if (b == 0) + { + /* This is the first block in the function. There may be insns + before head that we can't schedule. We still need to examine + them though for accurate register lifetime analysis. */ + + /* We don't want to remove any REG_DEAD notes as the code below + does. */ + + for (insn = basic_block_head[b]; insn != head; + insn = NEXT_INSN (insn)) + if (GET_RTX_CLASS (GET_CODE (insn)) == 'i') + { + /* See if the register gets born here. */ + /* We must check for registers being born before we check for + registers dying. It is possible for a register to be born + and die in the same insn, e.g. reading from a volatile + memory location into an otherwise unused register. Such + a register must be marked as dead after this insn. */ + if (GET_CODE (PATTERN (insn)) == SET + || GET_CODE (PATTERN (insn)) == CLOBBER) + sched_note_set (b, PATTERN (insn), 0); + else if (GET_CODE (PATTERN (insn)) == PARALLEL) + { + int j; + for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--) + if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET + || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER) + sched_note_set (b, XVECEXP (PATTERN (insn), 0, j), 0); + + for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--) + if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == USE) + sched_note_set (b, XVECEXP (PATTERN (insn), 0, j), 0); + } + + for (link = REG_NOTES (insn); link; link = XEXP (link, 1)) + { + if ((REG_NOTE_KIND (link) == REG_DEAD + || REG_NOTE_KIND (link) == REG_UNUSED) + /* Verify that the REG_NOTE has a legal value. */ + && GET_CODE (XEXP (link, 0)) == REG) + { + register int regno = REGNO (XEXP (link, 0)); + register int offset = regno / REGSET_ELT_BITS; + register int bit = 1 << (regno % REGSET_ELT_BITS); + + if (regno < FIRST_PSEUDO_REGISTER) + { + int j = HARD_REGNO_NREGS (regno, + GET_MODE (XEXP (link, 0))); + while (--j >= 0) + { + offset = (regno + j) / REGSET_ELT_BITS; + bit = 1 << ((regno + j) % REGSET_ELT_BITS); + + bb_live_regs[offset] &= ~bit; + bb_dead_regs[offset] |= bit; + } + } + else + { + bb_live_regs[offset] &= ~bit; + bb_dead_regs[offset] |= bit; + } + } + } + } + } + } + + /* If debugging information is being produced, keep track of the line + number notes for each insn. */ + if (write_symbols != NO_DEBUG) + { + /* We must use the true line number for the first insn in the block + that was computed and saved at the start of this pass. We can't + use the current line number, because scheduling of the previous + block may have changed the current line number. */ + rtx line = line_note_head[b]; + + for (insn = basic_block_head[b]; + insn != next_tail; + insn = NEXT_INSN (insn)) + if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0) + line = insn; + else + LINE_NOTE (insn) = line; + } + + for (insn = head; insn != next_tail; insn = NEXT_INSN (insn)) + { + rtx prev, next, link; + + /* Farm out notes. This is needed to keep the debugger from + getting completely deranged. */ + if (GET_CODE (insn) == NOTE) + { + prev = insn; + insn = unlink_notes (insn, next_tail); + if (prev == tail) + abort (); + if (prev == head) + abort (); + if (insn == next_tail) + abort (); + } + + if (reload_completed == 0 + && GET_RTX_CLASS (GET_CODE (insn)) == 'i') + { + /* See if the register gets born here. */ + /* We must check for registers being born before we check for + registers dying. It is possible for a register to be born and + die in the same insn, e.g. reading from a volatile memory + location into an otherwise unused register. Such a register + must be marked as dead after this insn. */ + if (GET_CODE (PATTERN (insn)) == SET + || GET_CODE (PATTERN (insn)) == CLOBBER) + sched_note_set (b, PATTERN (insn), 0); + else if (GET_CODE (PATTERN (insn)) == PARALLEL) + { + int j; + for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--) + if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET + || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER) + sched_note_set (b, XVECEXP (PATTERN (insn), 0, j), 0); + + for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--) + if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == USE) + sched_note_set (b, XVECEXP (PATTERN (insn), 0, j), 0); + } + + /* Need to know what registers this insn kills. */ + for (prev = 0, link = REG_NOTES (insn); link; link = next) + { + int regno; + + next = XEXP (link, 1); + if ((REG_NOTE_KIND (link) == REG_DEAD + || REG_NOTE_KIND (link) == REG_UNUSED) + /* Verify that the REG_NOTE has a legal value. */ + && GET_CODE (XEXP (link, 0)) == REG) + { + register int regno = REGNO (XEXP (link, 0)); + register int offset = regno / REGSET_ELT_BITS; + register int bit = 1 << (regno % REGSET_ELT_BITS); + + /* Only unlink REG_DEAD notes; leave REG_UNUSED notes + alone. */ + if (REG_NOTE_KIND (link) == REG_DEAD) + { + if (prev) + XEXP (prev, 1) = next; + else + REG_NOTES (insn) = next; + XEXP (link, 1) = dead_notes; + dead_notes = link; + } + else + prev = link; + + if (regno < FIRST_PSEUDO_REGISTER) + { + int j = HARD_REGNO_NREGS (regno, + GET_MODE (XEXP (link, 0))); + while (--j >= 0) + { + offset = (regno + j) / REGSET_ELT_BITS; + bit = 1 << ((regno + j) % REGSET_ELT_BITS); + + bb_live_regs[offset] &= ~bit; + bb_dead_regs[offset] |= bit; + } + } + else + { + bb_live_regs[offset] &= ~bit; + bb_dead_regs[offset] |= bit; + } + } + else + prev = link; + } + } + } + + if (reload_completed == 0) + { + /* Keep track of register lives. */ + old_live_regs = (regset) alloca (regset_bytes); + regs_sometimes_live + = (struct sometimes *) alloca (max_regno * sizeof (struct sometimes)); + sometimes_max = 0; + + /* Start with registers live at end. */ + for (j = 0; j < regset_size; j++) + { + int live = bb_live_regs[j]; + old_live_regs[j] = live; + if (live) + { + register int bit; + for (bit = 0; bit < REGSET_ELT_BITS; bit++) + if (live & (1 << bit)) + sometimes_max = new_sometimes_live (regs_sometimes_live, j, + bit, sometimes_max); + } + } + } + + SCHED_SORT (ready, n_ready, 1); + + if (file) + { + fprintf (file, ";; ready list initially:\n;; "); + for (i = 0; i < n_ready; i++) + fprintf (file, "%d ", INSN_UID (ready[i])); + fprintf (file, "\n\n"); + + for (insn = head; insn != next_tail; insn = NEXT_INSN (insn)) + if (INSN_PRIORITY (insn) > 0) + fprintf (file, ";; insn[%4d]: priority = %4d, ref_count = %4d\n", + INSN_UID (insn), INSN_PRIORITY (insn), + INSN_REF_COUNT (insn)); + } + + /* Now HEAD and TAIL are going to become disconnected + entirely from the insn chain. */ + tail = ready[0]; + + /* Q_SIZE will always be zero here. */ + q_ptr = 0; + bzero (insn_queue, sizeof (insn_queue)); + + /* Now, perform list scheduling. */ + + /* Where we start inserting insns is after TAIL. */ + last = next_tail; + + new_needs = (NEXT_INSN (prev_head) == basic_block_head[b] + ? NEED_HEAD : NEED_NOTHING); + if (PREV_INSN (next_tail) == basic_block_end[b]) + new_needs |= NEED_TAIL; + + new_ready = n_ready; + while (sched_n_insns < n_insns) + { + q_ptr = NEXT_Q (q_ptr); + + /* Add all pending insns that can be scheduled without stalls to the + ready list. */ + for (insn = insn_queue[q_ptr]; insn; insn = NEXT_INSN (insn)) + { + if (file) + fprintf (file, ";; launching %d before %d with no stalls\n", + INSN_UID (insn), INSN_UID (last)); + ready[new_ready++] = insn; + q_size -= 1; + } + insn_queue[q_ptr] = 0; + + /* If there are no ready insns, stall until one is ready and add all + of the pending insns at that point to the ready list. */ + if (new_ready == 0) + { + register int stalls; + + for (stalls = 1; stalls < Q_SIZE; stalls++) + if (insn = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]) + { + for (; insn; insn = NEXT_INSN (insn)) + { + if (file) + fprintf (file, ";; issue insn %d before %d with %d stalls\n", + INSN_UID (insn), INSN_UID (last), stalls); + ready[new_ready++] = insn; + q_size -= 1; + } + insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = 0; + break; + } + +#if 0 + /* This looks logically correct, but on the SPEC benchmark set on + the SPARC, I get better code without it. */ + q_ptr = NEXT_Q_AFTER (q_ptr, stalls); +#endif + } + + /* There should be some instructions waiting to fire. */ + if (new_ready == 0) + abort (); + + /* Sort the ready list and choose the best insn to schedule. + N_READY holds the number of items that were scheduled the last time, + minus the one instruction scheduled on the last loop iteration; it + is not modified for any other reason in this loop. */ + SCHED_SORT (ready, new_ready, n_ready); + n_ready = new_ready; + last_scheduled_insn = insn = ready[0]; + + if (DONE_PRIORITY_P (insn)) + abort (); + + if (reload_completed == 0) + { + /* Process this insn, and each insn linked to this one which must + be immediately output after this insn. */ + do + { + /* First we kill registers set by this insn, and then we + make registers used by this insn live. This is the opposite + order used above because we are traversing the instructions + backwards. */ + + /* Strictly speaking, we should scan REG_UNUSED notes and make + every register mentioned there live, however, we will just + kill them again immediately below, so there doesn't seem to + be any reason why we bother to do this. */ + + /* See if this is the last notice we must take of a register. */ + if (GET_CODE (PATTERN (insn)) == SET + || GET_CODE (PATTERN (insn)) == CLOBBER) + sched_note_set (b, PATTERN (insn), 1); + else if (GET_CODE (PATTERN (insn)) == PARALLEL) + { + int j; + for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--) + if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET + || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER) + sched_note_set (b, XVECEXP (PATTERN (insn), 0, j), 1); + } + + /* This code keeps life analysis information up to date. */ + if (GET_CODE (insn) == CALL_INSN) + { + register struct sometimes *p; + + /* A call kills all call used and global registers, except + for those mentioned in the call pattern which will be + made live again later. */ + for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) + if (call_used_regs[i] || global_regs[i]) + { + register int offset = i / REGSET_ELT_BITS; + register int bit = 1 << (i % REGSET_ELT_BITS); + + bb_live_regs[offset] &= ~bit; + bb_dead_regs[offset] |= bit; + } + + /* Regs live at the time of a call instruction must not + go in a register clobbered by calls. Record this for + all regs now live. Note that insns which are born or + die in a call do not cross a call, so this must be done + after the killings (above) and before the births + (below). */ + p = regs_sometimes_live; + for (i = 0; i < sometimes_max; i++, p++) + if (bb_live_regs[p->offset] & (1 << p->bit)) + p->calls_crossed += 1; + } + + /* Make every register used live, and add REG_DEAD notes for + registers which were not live before we started. */ + attach_deaths_insn (insn); + + /* Find registers now made live by that instruction. */ + for (i = 0; i < regset_size; i++) + { + int diff = bb_live_regs[i] & ~old_live_regs[i]; + if (diff) + { + register int bit; + old_live_regs[i] |= diff; + for (bit = 0; bit < REGSET_ELT_BITS; bit++) + if (diff & (1 << bit)) + sometimes_max + = new_sometimes_live (regs_sometimes_live, i, bit, + sometimes_max); + } + } + + /* Count lengths of all regs we are worrying about now, + and handle registers no longer live. */ + + for (i = 0; i < sometimes_max; i++) + { + register struct sometimes *p = ®s_sometimes_live[i]; + int regno = p->offset*REGSET_ELT_BITS + p->bit; + + p->live_length += 1; + + if ((bb_live_regs[p->offset] & (1 << p->bit)) == 0) + { + /* This is the end of one of this register's lifetime + segments. Save the lifetime info collected so far, + and clear its bit in the old_live_regs entry. */ + sched_reg_live_length[regno] += p->live_length; + sched_reg_n_calls_crossed[regno] += p->calls_crossed; + old_live_regs[p->offset] &= ~(1 << p->bit); + + /* Delete the reg_sometimes_live entry for this reg by + copying the last entry over top of it. */ + *p = regs_sometimes_live[--sometimes_max]; + /* ...and decrement i so that this newly copied entry + will be processed. */ + i--; + } + } + + link = insn; + insn = PREV_INSN (insn); + } + while (SCHED_GROUP_P (link)); + + /* Set INSN back to the insn we are scheduling now. */ + insn = ready[0]; + } + + /* Schedule INSN. Remove it from the ready list. */ + ready += 1; + n_ready -= 1; + + sched_n_insns += 1; + NEXT_INSN (insn) = last; + PREV_INSN (last) = insn; + last = insn; + + /* Everything that precedes INSN now either becomes "ready", if + it can execute immediately before INSN, or "pending", if + there must be a delay. Give INSN high enough priority that + at least one (maybe more) reg-killing insns can be launched + ahead of all others. Mark INSN as scheduled by changing its + priority to -1. */ + INSN_PRIORITY (insn) = LAUNCH_PRIORITY; + new_ready = launch_links (insn, ready, n_ready); + INSN_PRIORITY (insn) = DONE_PRIORITY; + + /* Schedule all prior insns that must not be moved. */ + if (SCHED_GROUP_P (insn)) + { + /* Disable these insns from being launched. */ + link = insn; + while (SCHED_GROUP_P (link)) + { + /* Disable these insns from being launched by anybody. */ + link = PREV_INSN (link); + INSN_REF_COUNT (link) = 0; + } + + /* None of these insns can move forward into delay slots. */ + while (SCHED_GROUP_P (insn)) + { + insn = PREV_INSN (insn); + new_ready = launch_links (insn, ready, new_ready); + INSN_PRIORITY (insn) = DONE_PRIORITY; + + sched_n_insns += 1; + NEXT_INSN (insn) = last; + PREV_INSN (last) = insn; + last = insn; + } + } + } + if (q_size != 0) + abort (); + + if (reload_completed == 0) + finish_sometimes_live (regs_sometimes_live, sometimes_max); + + /* HEAD is now the first insn in the chain of insns that + been scheduled by the loop above. + TAIL is the last of those insns. */ + head = insn; + + /* NOTE_LIST is the end of a chain of notes previously found + among the insns. Insert them at the beginning of the insns. */ + if (note_list != 0) + { + rtx note_head = note_list; + while (PREV_INSN (note_head)) + note_head = PREV_INSN (note_head); + + PREV_INSN (head) = note_list; + NEXT_INSN (note_list) = head; + head = note_head; + } + + /* In theory, there should be no REG_DEAD notes leftover at the end. + In practice, this can occur as the result of bugs in flow, combine.c, + and/or sched.c. The values of the REG_DEAD notes remaining are + meaningless, because dead_notes is just used as a free list. */ +#if 1 + if (dead_notes != 0) + abort (); +#endif + + if (new_needs & NEED_HEAD) + basic_block_head[b] = head; + PREV_INSN (head) = prev_head; + NEXT_INSN (prev_head) = head; + + if (new_needs & NEED_TAIL) + basic_block_end[b] = tail; + NEXT_INSN (tail) = next_tail; + PREV_INSN (next_tail) = tail; + + /* Restore the line-number notes of each insn. */ + if (write_symbols != NO_DEBUG) + { + rtx line, note, prev, new; + int notes = 0; + + head = basic_block_head[b]; + next_tail = NEXT_INSN (basic_block_end[b]); + + /* Determine the current line-number. We want to know the current + line number of the first insn of the block here, in case it is + different from the true line number that was saved earlier. If + different, then we need a line number note before the first insn + of this block. If it happens to be the same, then we don't want to + emit another line number note here. */ + for (line = head; line; line = PREV_INSN (line)) + if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0) + break; + + /* Walk the insns keeping track of the current line-number and inserting + the line-number notes as needed. */ + for (insn = head; insn != next_tail; insn = NEXT_INSN (insn)) + if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0) + line = insn; + else if (! (GET_CODE (insn) == NOTE + && NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED) + && (note = LINE_NOTE (insn)) != 0 + && note != line + && (line == 0 + || NOTE_LINE_NUMBER (note) != NOTE_LINE_NUMBER (line) + || NOTE_SOURCE_FILE (note) != NOTE_SOURCE_FILE (line))) + { + line = note; + prev = PREV_INSN (insn); + if (LINE_NOTE (note)) + { + /* Re-use the orignal line-number note. */ + LINE_NOTE (note) = 0; + PREV_INSN (note) = prev; + NEXT_INSN (prev) = note; + PREV_INSN (insn) = note; + NEXT_INSN (note) = insn; + } + else + { + notes++; + new = emit_note_after (NOTE_LINE_NUMBER (note), prev); + NOTE_SOURCE_FILE (new) = NOTE_SOURCE_FILE (note); + } + } + if (file && notes) + fprintf (file, ";; added %d line-number notes\n", notes); + } + + if (file) + { + fprintf (file, ";; new basic block head = %d\n;; new basic block end = %d\n\n", + INSN_UID (basic_block_head[b]), INSN_UID (basic_block_end[b])); + } + + /* Yow! We're done! */ + free_pending_lists (); + + return; +} + +/* Subroutine of split_hard_reg_notes. Searches X for any reference to + REGNO, returning the rtx of the reference found if any. Otherwise, + returns 0. */ + +rtx +regno_use_in (regno, x) + int regno; + rtx x; +{ + register char *fmt; + int i, j; + rtx tem; + + if (GET_CODE (x) == REG && REGNO (x) == regno) + return x; + + fmt = GET_RTX_FORMAT (GET_CODE (x)); + for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--) + { + if (fmt[i] == 'e') + { + if (tem = regno_use_in (regno, XEXP (x, i))) + return tem; + } + else if (fmt[i] == 'E') + for (j = XVECLEN (x, i) - 1; j >= 0; j--) + if (tem = regno_use_in (regno , XVECEXP (x, i, j))) + return tem; + } + + return 0; +} + +/* Subroutine of update_flow_info. Determines whether any new REG_NOTEs are + needed for the hard register mentioned in the note. This can happen + if the reference to the hard register in the original insn was split into + several smaller hard register references in the split insns. */ + +static void +split_hard_reg_notes (note, first, last, orig_insn) + rtx note, first, last, orig_insn; +{ + rtx reg, temp, link; + int n_regs, i, new_reg; + rtx insn; + + /* Assume that this is a REG_DEAD note. */ + if (REG_NOTE_KIND (note) != REG_DEAD) + abort (); + + reg = XEXP (note, 0); + + n_regs = HARD_REGNO_NREGS (REGNO (reg), GET_MODE (reg)); + + /* ??? Could add check here to see whether, the hard register is referenced + in the same mode as in the original insn. If so, then it has not been + split, and the rest of the code below is unnecessary. */ + + for (i = 1; i < n_regs; i++) + { + new_reg = REGNO (reg) + i; + + /* Check for references to new_reg in the split insns. */ + for (insn = last; ; insn = PREV_INSN (insn)) + { + if (GET_RTX_CLASS (GET_CODE (insn)) == 'i' + && (temp = regno_use_in (new_reg, PATTERN (insn)))) + { + /* Create a new reg dead note here. */ + link = rtx_alloc (EXPR_LIST); + PUT_REG_NOTE_KIND (link, REG_DEAD); + XEXP (link, 0) = temp; + XEXP (link, 1) = REG_NOTES (insn); + REG_NOTES (insn) = link; + break; + } + /* It isn't mentioned anywhere, so no new reg note is needed for + this register. */ + if (insn == first) + break; + } + } +} + +/* Subroutine of update_flow_info. Determines whether a SET or CLOBBER in an + insn created by splitting needs a REG_DEAD or REG_UNUSED note added. */ + +static void +new_insn_dead_notes (pat, insn, last, orig_insn) + rtx pat, insn, last, orig_insn; +{ + rtx dest, tem, set; + + /* PAT is either a CLOBBER or a SET here. */ + dest = XEXP (pat, 0); + + while (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SUBREG + || GET_CODE (dest) == STRICT_LOW_PART + || GET_CODE (dest) == SIGN_EXTRACT) + dest = XEXP (dest, 0); + + if (GET_CODE (dest) == REG) + { + for (tem = last; tem != insn; tem = PREV_INSN (tem)) + { + if (GET_RTX_CLASS (GET_CODE (tem)) == 'i' + && reg_overlap_mentioned_p (dest, PATTERN (tem)) + && (set = single_set (tem))) + { + rtx tem_dest = SET_DEST (set); + + while (GET_CODE (tem_dest) == ZERO_EXTRACT + || GET_CODE (tem_dest) == SUBREG + || GET_CODE (tem_dest) == STRICT_LOW_PART + || GET_CODE (tem_dest) == SIGN_EXTRACT) + tem_dest = XEXP (tem_dest, 0); + + if (tem_dest != dest) + { + /* Use the same scheme as combine.c, don't put both REG_DEAD + and REG_UNUSED notes on the same insn. */ + if (! find_regno_note (tem, REG_UNUSED, REGNO (dest)) + && ! find_regno_note (tem, REG_DEAD, REGNO (dest))) + { + rtx note = rtx_alloc (EXPR_LIST); + PUT_REG_NOTE_KIND (note, REG_DEAD); + XEXP (note, 0) = dest; + XEXP (note, 1) = REG_NOTES (tem); + REG_NOTES (tem) = note; + } + /* The reg only dies in one insn, the last one that uses + it. */ + break; + } + else if (reg_overlap_mentioned_p (dest, SET_SRC (set))) + /* We found an instruction that both uses the register, + and sets it, so no new REG_NOTE is needed for this set. */ + break; + } + } + /* If this is a set, it must die somewhere, unless it is the dest of + the original insn, and hence is live after the original insn. Abort + if it isn't supposed to be live after the original insn. + + If this is a clobber, then just add a REG_UNUSED note. */ + if (tem == insn) + { + int live_after_orig_insn = 0; + rtx pattern = PATTERN (orig_insn); + int i; + + if (GET_CODE (pat) == CLOBBER) + { + rtx note = rtx_alloc (EXPR_LIST); + PUT_REG_NOTE_KIND (note, REG_UNUSED); + XEXP (note, 0) = dest; + XEXP (note, 1) = REG_NOTES (insn); + REG_NOTES (insn) = note; + return; + } + + /* The original insn could have multiple sets, so search the + insn for all sets. */ + if (GET_CODE (pattern) == SET) + { + if (reg_overlap_mentioned_p (dest, SET_DEST (pattern))) + live_after_orig_insn = 1; + } + else if (GET_CODE (pattern) == PARALLEL) + { + for (i = 0; i < XVECLEN (pattern, 0); i++) + if (GET_CODE (XVECEXP (pattern, 0, i)) == SET + && reg_overlap_mentioned_p (dest, + SET_DEST (XVECEXP (pattern, + 0, i)))) + live_after_orig_insn = 1; + } + + if (! live_after_orig_insn) + abort (); + } + } +} + +/* Subroutine of update_flow_info. Update the value of reg_n_sets for all + registers modified by X. INC is -1 if the containing insn is being deleted, + and is 1 if the containing insn is a newly generated insn. */ + +static void +update_n_sets (x, inc) + rtx x; + int inc; +{ + rtx dest = SET_DEST (x); + + while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG + || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT) + dest = SUBREG_REG (dest); + + if (GET_CODE (dest) == REG) + { + int regno = REGNO (dest); + + if (regno < FIRST_PSEUDO_REGISTER) + { + register int i; + int endregno = regno + HARD_REGNO_NREGS (regno, GET_MODE (dest)); + + for (i = regno; i < endregno; i++) + reg_n_sets[i] += inc; + } + else + reg_n_sets[regno] += inc; + } +} + +/* Updates all flow-analysis related quantities (including REG_NOTES) for + the insns from FIRST to LAST inclusive that were created by splitting + ORIG_INSN. NOTES are the original REG_NOTES. */ + +static void +update_flow_info (notes, first, last, orig_insn) + rtx notes; + rtx first, last; + rtx orig_insn; +{ + rtx insn, note; + rtx next; + rtx orig_dest, temp; + rtx set; + + /* Get and save the destination set by the original insn. */ + + orig_dest = single_set (orig_insn); + if (orig_dest) + orig_dest = SET_DEST (orig_dest); + + /* Move REG_NOTES from the original insn to where they now belong. */ + + for (note = notes; note; note = next) + { + next = XEXP (note, 1); + switch (REG_NOTE_KIND (note)) + { + case REG_DEAD: + case REG_UNUSED: + /* Move these notes from the original insn to the last new insn where + the register is now set. */ + + for (insn = last; ; insn = PREV_INSN (insn)) + { + if (GET_RTX_CLASS (GET_CODE (insn)) == 'i' + && reg_mentioned_p (XEXP (note, 0), PATTERN (insn))) + { + XEXP (note, 1) = REG_NOTES (insn); + REG_NOTES (insn) = note; + + /* Sometimes need to convert REG_UNUSED notes to REG_DEAD + notes. */ + /* ??? This won't handle mutiple word registers correctly, + but should be good enough for now. */ + if (REG_NOTE_KIND (note) == REG_UNUSED + && ! dead_or_set_p (insn, XEXP (note, 0))) + PUT_REG_NOTE_KIND (note, REG_DEAD); + + /* The reg only dies in one insn, the last one that uses + it. */ + break; + } + /* It must die somewhere, fail it we couldn't find where it died. + + If this is a REG_UNUSED note, then it must be a temporary + register that was not needed by this instantiation of the + pattern, so we can safely ignore it. */ + if (insn == first) + { + if (REG_NOTE_KIND (note) != REG_UNUSED) + abort (); + + break; + } + } + + /* If this note refers to a multiple word hard register, it may + have been split into several smaller hard register references. + Check to see if there are any new register references that + need REG_NOTES added for them. */ + temp = XEXP (note, 0); + if (REG_NOTE_KIND (note) == REG_DEAD + && GET_CODE (temp) == REG + && REGNO (temp) < FIRST_PSEUDO_REGISTER + && HARD_REGNO_NREGS (REGNO (temp), GET_MODE (temp))) + split_hard_reg_notes (note, first, last, orig_insn); + break; + + case REG_WAS_0: + /* This note applies to the dest of the original insn. Find the + first new insn that now has the same dest, and move the note + there. */ + + if (! orig_dest) + abort (); + + for (insn = first; ; insn = NEXT_INSN (insn)) + { + if (GET_RTX_CLASS (GET_CODE (insn)) == 'i' + && (temp = single_set (insn)) + && rtx_equal_p (SET_DEST (temp), orig_dest)) + { + XEXP (note, 1) = REG_NOTES (insn); + REG_NOTES (insn) = note; + /* The reg is only zero before one insn, the first that + uses it. */ + break; + } + /* It must be set somewhere, fail if we couldn't find where it + was set. */ + if (insn == last) + abort (); + } + break; + + case REG_EQUAL: + case REG_EQUIV: + /* A REG_EQUIV or REG_EQUAL note on an insn with more than one + set is meaningless. Just drop the note. */ + if (! orig_dest) + break; + + case REG_NO_CONFLICT: + /* These notes apply to the dest of the original insn. Find the last + new insn that now has the same dest, and move the note there. */ + + if (! orig_dest) + abort (); + + for (insn = last; ; insn = PREV_INSN (insn)) + { + if (GET_RTX_CLASS (GET_CODE (insn)) == 'i' + && (temp = single_set (insn)) + && rtx_equal_p (SET_DEST (temp), orig_dest)) + { + XEXP (note, 1) = REG_NOTES (insn); + REG_NOTES (insn) = note; + /* Only put this note on one of the new insns. */ + break; + } + + /* The original dest must still be set someplace. Abort if we + couldn't find it. */ + if (insn == first) + abort (); + } + break; + + case REG_LIBCALL: + /* Move a REG_LIBCALL note to the first insn created, and update + the corresponding REG_RETVAL note. */ + XEXP (note, 1) = REG_NOTES (first); + REG_NOTES (first) = note; + + insn = XEXP (note, 0); + note = find_reg_note (insn, REG_RETVAL, 0); + if (note) + XEXP (note, 0) = first; + break; + + case REG_RETVAL: + /* Move a REG_RETVAL note to the last insn created, and update + the corresponding REG_LIBCALL note. */ + XEXP (note, 1) = REG_NOTES (last); + REG_NOTES (last) = note; + + insn = XEXP (note, 0); + note = find_reg_note (insn, REG_LIBCALL, 0); + if (note) + XEXP (note, 0) = last; + break; + + case REG_NONNEG: + /* This should be moved to whichever instruction is a JUMP_INSN. */ + + for (insn = last; ; insn = PREV_INSN (insn)) + { + if (GET_CODE (insn) == JUMP_INSN) + { + XEXP (note, 1) = REG_NOTES (insn); + REG_NOTES (insn) = note; + /* Only put this note on one of the new insns. */ + break; + } + /* Fail if we couldn't find a JUMP_INSN. */ + if (insn == first) + abort (); + } + break; + + case REG_INC: + /* This should be moved to whichever instruction now has the + increment operation. */ + abort (); + + case REG_LABEL: + /* Should be moved to the new insn(s) which use the label. */ + abort (); + + case REG_CC_SETTER: + case REG_CC_USER: + /* These two notes will never appear until after reorg, so we don't + have to handle them here. */ + default: + abort (); + } + } + + /* Each new insn created, except the last, has a new set. If the destination + is a register, then this reg is now live across several insns, whereas + previously the dest reg was born and died within the same insn. To + reflect this, we now need a REG_DEAD note on the insn where this + dest reg dies. + + Similarly, the new insns may have clobbers that need REG_UNUSED notes. */ + + for (insn = first; insn != last; insn = NEXT_INSN (insn)) + { + rtx pat; + int i; + + pat = PATTERN (insn); + if (GET_CODE (pat) == SET || GET_CODE (pat) == CLOBBER) + new_insn_dead_notes (pat, insn, last, orig_insn); + else if (GET_CODE (pat) == PARALLEL) + { + for (i = 0; i < XVECLEN (pat, 0); i++) + if (GET_CODE (XVECEXP (pat, 0, i)) == SET + || GET_CODE (XVECEXP (pat, 0, i)) == CLOBBER) + new_insn_dead_notes (XVECEXP (pat, 0, i), insn, last, orig_insn); + } + } + + /* If any insn, except the last, uses the register set by the last insn, + then we need a new REG_DEAD note on that insn. In this case, there + would not have been a REG_DEAD note for this register in the original + insn because it was used and set within one insn. + + There is no new REG_DEAD note needed if the last insn uses the register + that it is setting. */ + + set = single_set (last); + if (set) + { + rtx dest = SET_DEST (set); + + while (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SUBREG + || GET_CODE (dest) == STRICT_LOW_PART + || GET_CODE (dest) == SIGN_EXTRACT) + dest = XEXP (dest, 0); + + if (GET_CODE (dest) == REG + && ! reg_overlap_mentioned_p (dest, SET_SRC (set))) + { + for (insn = PREV_INSN (last); ; insn = PREV_INSN (insn)) + { + if (GET_RTX_CLASS (GET_CODE (insn)) == 'i' + && reg_mentioned_p (dest, PATTERN (insn)) + && (set = single_set (insn))) + { + rtx insn_dest = SET_DEST (set); + + while (GET_CODE (insn_dest) == ZERO_EXTRACT + || GET_CODE (insn_dest) == SUBREG + || GET_CODE (insn_dest) == STRICT_LOW_PART + || GET_CODE (insn_dest) == SIGN_EXTRACT) + insn_dest = XEXP (insn_dest, 0); + + if (insn_dest != dest) + { + note = rtx_alloc (EXPR_LIST); + PUT_REG_NOTE_KIND (note, REG_DEAD); + XEXP (note, 0) = dest; + XEXP (note, 1) = REG_NOTES (insn); + REG_NOTES (insn) = note; + /* The reg only dies in one insn, the last one + that uses it. */ + break; + } + } + if (insn == first) + break; + } + } + } + + /* If the original dest is modifying a multiple register target, and the + original instruction was split such that the original dest is now set + by two or more SUBREG sets, then the split insns no longer kill the + destination of the original insn. + + In this case, if there exists an instruction in the same basic block, + before the split insn, which uses the original dest, and this use is + killed by the original insn, then we must remove the REG_DEAD note on + this insn, because it is now superfluous. + + This does not apply when a hard register gets split, because the code + knows how to handle overlapping hard registers properly. */ + if (orig_dest && GET_CODE (orig_dest) == REG) + { + int found_orig_dest = 0; + int found_split_dest = 0; + + for (insn = first; ; insn = NEXT_INSN (insn)) + { + set = single_set (insn); + if (set) + { + if (GET_CODE (SET_DEST (set)) == REG + && REGNO (SET_DEST (set)) == REGNO (orig_dest)) + { + found_orig_dest = 1; + break; + } + else if (GET_CODE (SET_DEST (set)) == SUBREG + && SUBREG_REG (SET_DEST (set)) == orig_dest) + { + found_split_dest = 1; + break; + } + } + + if (insn == last) + break; + } + + if (found_split_dest) + { + /* Search backwards from FIRST, looking for the first insn that uses + the original dest. Stop if we pass a CODE_LABEL or a JUMP_INSN. + If we find an insn, and it has a REG_DEAD note, then delete the + note. */ + + for (insn = first; insn; insn = PREV_INSN (insn)) + { + if (GET_CODE (insn) == CODE_LABEL + || GET_CODE (insn) == JUMP_INSN) + break; + else if (GET_RTX_CLASS (GET_CODE (insn)) == 'i' + && reg_mentioned_p (orig_dest, insn)) + { + note = find_regno_note (insn, REG_DEAD, REGNO (orig_dest)); + if (note) + remove_note (insn, note); + } + } + } + else if (! found_orig_dest) + { + /* This should never happen. */ + abort (); + } + } + + /* Update reg_n_sets. This is necessary to prevent local alloc from + converting REG_EQUAL notes to REG_EQUIV when splitting has modified + a reg from set once to set multiple times. */ + + { + rtx x = PATTERN (orig_insn); + RTX_CODE code = GET_CODE (x); + + if (code == SET || code == CLOBBER) + update_n_sets (x, -1); + else if (code == PARALLEL) + { + int i; + for (i = XVECLEN (x, 0) - 1; i >= 0; i--) + { + code = GET_CODE (XVECEXP (x, 0, i)); + if (code == SET || code == CLOBBER) + update_n_sets (XVECEXP (x, 0, i), -1); + } + } + + for (insn = first; ; insn = NEXT_INSN (insn)) + { + x = PATTERN (insn); + code = GET_CODE (x); + + if (code == SET || code == CLOBBER) + update_n_sets (x, 1); + else if (code == PARALLEL) + { + int i; + for (i = XVECLEN (x, 0) - 1; i >= 0; i--) + { + code = GET_CODE (XVECEXP (x, 0, i)); + if (code == SET || code == CLOBBER) + update_n_sets (XVECEXP (x, 0, i), 1); + } + } + + if (insn == last) + break; + } + } +} + +/* The one entry point in this file. DUMP_FILE is the dump file for + this pass. */ + +void +schedule_insns (dump_file) + FILE *dump_file; +{ + int max_uid = MAX_INSNS_PER_SPLIT * (get_max_uid () + 1); + int i, b; + rtx insn; + + /* Taking care of this degenerate case makes the rest of + this code simpler. */ + if (n_basic_blocks == 0) + return; + + /* Create an insn here so that we can hang dependencies off of it later. */ + sched_before_next_call = gen_rtx (INSN, VOIDmode, 0, 0, 0, 0, 0, 0, 0); + + /* Initialize the unused_*_lists. We can't use the ones left over from + the previous function, because gcc has freed that memory. We can use + the ones left over from the first sched pass in the second pass however, + so only clear them on the first sched pass. The first pass is before + reload if flag_schedule_insns is set, otherwise it is afterwards. */ + + if (reload_completed == 0 || ! flag_schedule_insns) + { + unused_insn_list = 0; + unused_expr_list = 0; + } + + /* We create no insns here, only reorder them, so we + remember how far we can cut back the stack on exit. */ + + /* Allocate data for this pass. See comments, above, + for what these vectors do. */ + /* ??? Instruction splitting below may create new instructions, so these + arrays must be bigger than just max_uid. */ + insn_luid = (int *) alloca (max_uid * sizeof (int)); + insn_priority = (int *) alloca (max_uid * sizeof (int)); + insn_ref_count = (int *) alloca (max_uid * sizeof (int)); + + if (reload_completed == 0) + { + sched_reg_n_deaths = (short *) alloca (max_regno * sizeof (short)); + sched_reg_n_calls_crossed = (int *) alloca (max_regno * sizeof (int)); + sched_reg_live_length = (int *) alloca (max_regno * sizeof (int)); + bb_dead_regs = (regset) alloca (regset_bytes); + bb_live_regs = (regset) alloca (regset_bytes); + bzero (sched_reg_n_calls_crossed, max_regno * sizeof (int)); + bzero (sched_reg_live_length, max_regno * sizeof (int)); + bcopy (reg_n_deaths, sched_reg_n_deaths, max_regno * sizeof (short)); + init_alias_analysis (); + } + else + { + sched_reg_n_deaths = 0; + sched_reg_n_calls_crossed = 0; + sched_reg_live_length = 0; + bb_dead_regs = 0; + bb_live_regs = 0; + if (! flag_schedule_insns) + init_alias_analysis (); + } + + if (write_symbols != NO_DEBUG) + { + rtx line; + + line_note = (rtx *) alloca (max_uid * sizeof (rtx)); + bzero (line_note, max_uid * sizeof (rtx)); + line_note_head = (rtx *) alloca (n_basic_blocks * sizeof (rtx)); + bzero (line_note_head, n_basic_blocks * sizeof (rtx)); + + /* Determine the line-number at the start of each basic block. + This must be computed and saved now, because after a basic block's + predecessor has been scheduled, it is impossible to accurately + determine the correct line number for the first insn of the block. */ + + for (b = 0; b < n_basic_blocks; b++) + for (line = basic_block_head[b]; line; line = PREV_INSN (line)) + if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0) + { + line_note_head[b] = line; + break; + } + } + + bzero (insn_luid, max_uid * sizeof (int)); + bzero (insn_priority, max_uid * sizeof (int)); + bzero (insn_ref_count, max_uid * sizeof (int)); + + /* Schedule each basic block, block by block. */ + + if (NEXT_INSN (basic_block_end[n_basic_blocks-1]) == 0 + || (GET_CODE (basic_block_end[n_basic_blocks-1]) != NOTE + && GET_CODE (basic_block_end[n_basic_blocks-1]) != CODE_LABEL)) + emit_note_after (NOTE_INSN_DELETED, basic_block_end[n_basic_blocks-1]); + + for (b = 0; b < n_basic_blocks; b++) + { + rtx insn, next; + rtx insns; + + note_list = 0; + + for (insn = basic_block_head[b]; ; insn = next) + { + rtx prev; + rtx set; + + /* Can't use `next_real_insn' because that + might go across CODE_LABELS and short-out basic blocks. */ + next = NEXT_INSN (insn); + if (GET_CODE (insn) != INSN) + { + if (insn == basic_block_end[b]) + break; + + continue; + } + + /* Don't split no-op move insns. These should silently disappear + later in final. Splitting such insns would break the code + that handles REG_NO_CONFLICT blocks. */ + set = single_set (insn); + if (set && rtx_equal_p (SET_SRC (set), SET_DEST (set))) + { + if (insn == basic_block_end[b]) + break; + + /* Nops get in the way while scheduling, so delete them now if + register allocation has already been done. It is too risky + to try to do this before register allocation, and there are + unlikely to be very many nops then anyways. */ + if (reload_completed) + { + PUT_CODE (insn, NOTE); + NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED; + NOTE_SOURCE_FILE (insn) = 0; + } + + continue; + } + + /* Split insns here to get max fine-grain parallelism. */ + prev = PREV_INSN (insn); + if (reload_completed == 0) + { + rtx last, first = PREV_INSN (insn); + rtx notes = REG_NOTES (insn); + + last = try_split (PATTERN (insn), insn, 1); + if (last != insn) + { + /* try_split returns the NOTE that INSN became. */ + first = NEXT_INSN (first); + update_flow_info (notes, first, last, insn); + + PUT_CODE (insn, NOTE); + NOTE_SOURCE_FILE (insn) = 0; + NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED; + if (insn == basic_block_head[b]) + basic_block_head[b] = first; + if (insn == basic_block_end[b]) + { + basic_block_end[b] = last; + break; + } + } + } + + if (insn == basic_block_end[b]) + break; + } + + schedule_block (b, dump_file); + +#ifdef USE_C_ALLOCA + alloca (0); +#endif + } + + if (write_symbols != NO_DEBUG) + { + rtx line = 0; + rtx insn = get_insns (); + int active_insn = 0; + int notes = 0; + + /* Walk the insns deleting redundant line-number notes. Many of these + are already present. The remainder tend to occur at basic + block boundaries. */ + for (insn = get_last_insn (); insn; insn = PREV_INSN (insn)) + if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0) + { + /* If there are no active insns following, INSN is redundant. */ + if (active_insn == 0) + { + notes++; + NOTE_SOURCE_FILE (insn) = 0; + NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED; + } + /* If the line number is unchanged, LINE is redundant. */ + else if (line + && NOTE_LINE_NUMBER (line) == NOTE_LINE_NUMBER (insn) + && NOTE_SOURCE_FILE (line) == NOTE_SOURCE_FILE (insn)) + { + notes++; + NOTE_SOURCE_FILE (line) = 0; + NOTE_LINE_NUMBER (line) = NOTE_INSN_DELETED; + line = insn; + } + else + line = insn; + active_insn = 0; + } + else if (! ((GET_CODE (insn) == NOTE + && NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED) + || (GET_CODE (insn) == INSN + && (GET_CODE (PATTERN (insn)) == USE + || GET_CODE (PATTERN (insn)) == CLOBBER)))) + active_insn++; + + if (dump_file && notes) + fprintf (dump_file, ";; deleted %d line-number notes\n", notes); + } + + if (reload_completed == 0) + { + int regno; + for (regno = 0; regno < max_regno; regno++) + if (sched_reg_live_length[regno]) + { + if (dump_file) + { + if (reg_live_length[regno] > sched_reg_live_length[regno]) + fprintf (dump_file, + ";; register %d life shortened from %d to %d\n", + regno, reg_live_length[regno], + sched_reg_live_length[regno]); + /* Negative values are special; don't overwrite the current + reg_live_length value if it is negative. */ + else if (reg_live_length[regno] < sched_reg_live_length[regno] + && reg_live_length[regno] >= 0) + fprintf (dump_file, + ";; register %d life extended from %d to %d\n", + regno, reg_live_length[regno], + sched_reg_live_length[regno]); + + if (reg_n_calls_crossed[regno] + && ! sched_reg_n_calls_crossed[regno]) + fprintf (dump_file, + ";; register %d no longer crosses calls\n", regno); + else if (! reg_n_calls_crossed[regno] + && sched_reg_n_calls_crossed[regno]) + fprintf (dump_file, + ";; register %d now crosses calls\n", regno); + } + reg_live_length[regno] = sched_reg_live_length[regno]; + reg_n_calls_crossed[regno] = sched_reg_n_calls_crossed[regno]; + } + } +} +#endif /* INSN_SCHEDULING */ -- 2.43.5