gcc/sched.c

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