gcc/sched.c

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