gcc/sched.c

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