gcc/sched.c

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