gcc/sched.c

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