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           prev_priority = priority (x) + insn_cost (x, prev, insn) - 1;
1478
1479           if (prev_priority > max_priority)
1480             max_priority = prev_priority;
1481           INSN_REF_COUNT (x) += 1;
1482         }
1483
1484       prepare_unit (insn_unit (insn));
1485       INSN_PRIORITY (insn) = max_priority;
1486       return INSN_PRIORITY (insn);
1487     }
1488   return 0;
1489 }
1490 \f
1491 /* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
1492    them to the unused_*_list variables, so that they can be reused.  */
1493
1494 static void
1495 free_pending_lists ()
1496 {
1497   register rtx link, prev_link;
1498
1499   if (pending_read_insns)
1500     {
1501       prev_link = pending_read_insns;
1502       link = XEXP (prev_link, 1);
1503
1504       while (link)
1505         {
1506           prev_link = link;
1507           link = XEXP (link, 1);
1508         }
1509
1510       XEXP (prev_link, 1) = unused_insn_list;
1511       unused_insn_list = pending_read_insns;
1512       pending_read_insns = 0;
1513     }
1514
1515   if (pending_write_insns)
1516     {
1517       prev_link = pending_write_insns;
1518       link = XEXP (prev_link, 1);
1519
1520       while (link)
1521         {
1522           prev_link = link;
1523           link = XEXP (link, 1);
1524         }
1525
1526       XEXP (prev_link, 1) = unused_insn_list;
1527       unused_insn_list = pending_write_insns;
1528       pending_write_insns = 0;
1529     }
1530
1531   if (pending_read_mems)
1532     {
1533       prev_link = pending_read_mems;
1534       link = XEXP (prev_link, 1);
1535
1536       while (link)
1537         {
1538           prev_link = link;
1539           link = XEXP (link, 1);
1540         }
1541
1542       XEXP (prev_link, 1) = unused_expr_list;
1543       unused_expr_list = pending_read_mems;
1544       pending_read_mems = 0;
1545     }
1546
1547   if (pending_write_mems)
1548     {
1549       prev_link = pending_write_mems;
1550       link = XEXP (prev_link, 1);
1551
1552       while (link)
1553         {
1554           prev_link = link;
1555           link = XEXP (link, 1);
1556         }
1557
1558       XEXP (prev_link, 1) = unused_expr_list;
1559       unused_expr_list = pending_write_mems;
1560       pending_write_mems = 0;
1561     }
1562 }
1563
1564 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
1565    The MEM is a memory reference contained within INSN, which we are saving
1566    so that we can do memory aliasing on it.  */
1567
1568 static void
1569 add_insn_mem_dependence (insn_list, mem_list, insn, mem)
1570      rtx *insn_list, *mem_list, insn, mem;
1571 {
1572   register rtx link;
1573
1574   if (unused_insn_list)
1575     {
1576       link = unused_insn_list;
1577       unused_insn_list = XEXP (link, 1);
1578     }
1579   else
1580     link = rtx_alloc (INSN_LIST);
1581   XEXP (link, 0) = insn;
1582   XEXP (link, 1) = *insn_list;
1583   *insn_list = link;
1584
1585   if (unused_expr_list)
1586     {
1587       link = unused_expr_list;
1588       unused_expr_list = XEXP (link, 1);
1589     }
1590   else
1591     link = rtx_alloc (EXPR_LIST);
1592   XEXP (link, 0) = mem;
1593   XEXP (link, 1) = *mem_list;
1594   *mem_list = link;
1595
1596   pending_lists_length++;
1597 }
1598 \f
1599 /* Make a dependency between every memory reference on the pending lists
1600    and INSN, thus flushing the pending lists.  */
1601
1602 static void
1603 flush_pending_lists (insn)
1604      rtx insn;
1605 {
1606   rtx link;
1607
1608   while (pending_read_insns)
1609     {
1610       add_dependence (insn, XEXP (pending_read_insns, 0), REG_DEP_ANTI);
1611
1612       link = pending_read_insns;
1613       pending_read_insns = XEXP (pending_read_insns, 1);
1614       XEXP (link, 1) = unused_insn_list;
1615       unused_insn_list = link;
1616
1617       link = pending_read_mems;
1618       pending_read_mems = XEXP (pending_read_mems, 1);
1619       XEXP (link, 1) = unused_expr_list;
1620       unused_expr_list = link;
1621     }
1622   while (pending_write_insns)
1623     {
1624       add_dependence (insn, XEXP (pending_write_insns, 0), REG_DEP_ANTI);
1625
1626       link = pending_write_insns;
1627       pending_write_insns = XEXP (pending_write_insns, 1);
1628       XEXP (link, 1) = unused_insn_list;
1629       unused_insn_list = link;
1630
1631       link = pending_write_mems;
1632       pending_write_mems = XEXP (pending_write_mems, 1);
1633       XEXP (link, 1) = unused_expr_list;
1634       unused_expr_list = link;
1635     }
1636   pending_lists_length = 0;
1637
1638   if (last_pending_memory_flush)
1639     add_dependence (insn, last_pending_memory_flush, REG_DEP_ANTI);
1640
1641   last_pending_memory_flush = insn;
1642 }
1643
1644 /* Analyze a single SET or CLOBBER rtx, X, creating all dependencies generated
1645    by the write to the destination of X, and reads of everything mentioned.  */
1646
1647 static void
1648 sched_analyze_1 (x, insn)
1649      rtx x;
1650      rtx insn;
1651 {
1652   register int regno;
1653   register rtx dest = SET_DEST (x);
1654
1655   if (dest == 0)
1656     return;
1657
1658   while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
1659          || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
1660     {
1661       if (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
1662         {
1663           /* The second and third arguments are values read by this insn.  */
1664           sched_analyze_2 (XEXP (dest, 1), insn);
1665           sched_analyze_2 (XEXP (dest, 2), insn);
1666         }
1667       dest = SUBREG_REG (dest);
1668     }
1669
1670   if (GET_CODE (dest) == REG)
1671     {
1672       register int offset, bit, i;
1673
1674       regno = REGNO (dest);
1675
1676       /* A hard reg in a wide mode may really be multiple registers.
1677          If so, mark all of them just like the first.  */
1678       if (regno < FIRST_PSEUDO_REGISTER)
1679         {
1680           i = HARD_REGNO_NREGS (regno, GET_MODE (dest));
1681           while (--i >= 0)
1682             {
1683               rtx u;
1684
1685               for (u = reg_last_uses[regno+i]; u; u = XEXP (u, 1))
1686                 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
1687               reg_last_uses[regno + i] = 0;
1688               if (reg_last_sets[regno + i])
1689                 add_dependence (insn, reg_last_sets[regno + i],
1690                                 REG_DEP_OUTPUT);
1691               reg_last_sets[regno + i] = insn;
1692               if ((call_used_regs[i] || global_regs[i])
1693                   && last_function_call)
1694                 /* Function calls clobber all call_used regs.  */
1695                 add_dependence (insn, last_function_call, REG_DEP_ANTI);
1696             }
1697         }
1698       else
1699         {
1700           rtx u;
1701
1702           for (u = reg_last_uses[regno]; u; u = XEXP (u, 1))
1703             add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
1704           reg_last_uses[regno] = 0;
1705           if (reg_last_sets[regno])
1706             add_dependence (insn, reg_last_sets[regno], REG_DEP_OUTPUT);
1707           reg_last_sets[regno] = insn;
1708
1709           /* Pseudos that are REG_EQUIV to something may be replaced
1710              by that during reloading.  We need only add dependencies for
1711              the address in the REG_EQUIV note.  */
1712           if (! reload_completed
1713               && reg_known_equiv_p[regno]
1714               && GET_CODE (reg_known_value[regno]) == MEM)
1715             sched_analyze_2 (XEXP (reg_known_value[regno], 0), insn);
1716
1717           /* Don't let it cross a call after scheduling if it doesn't
1718              already cross one.  */
1719           if (reg_n_calls_crossed[regno] == 0 && last_function_call)
1720             add_dependence (insn, last_function_call, REG_DEP_ANTI);
1721         }
1722     }
1723   else if (GET_CODE (dest) == MEM)
1724     {
1725       /* Writing memory.  */
1726
1727       if (pending_lists_length > 32)
1728         {
1729           /* Flush all pending reads and writes to prevent the pending lists
1730              from getting any larger.  Insn scheduling runs too slowly when
1731              these lists get long.  The number 32 was chosen because it
1732              seems like a reasonable number.  When compiling GCC with itself,
1733              this flush occurs 8 times for sparc, and 10 times for m88k using
1734              the number 32.  */
1735           flush_pending_lists (insn);
1736         }
1737       else
1738         {
1739           rtx pending, pending_mem;
1740
1741           pending = pending_read_insns;
1742           pending_mem = pending_read_mems;
1743           while (pending)
1744             {
1745               /* If a dependency already exists, don't create a new one.  */
1746               if (! find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
1747                 if (anti_dependence (XEXP (pending_mem, 0), dest))
1748                   add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
1749
1750               pending = XEXP (pending, 1);
1751               pending_mem = XEXP (pending_mem, 1);
1752             }
1753
1754           pending = pending_write_insns;
1755           pending_mem = pending_write_mems;
1756           while (pending)
1757             {
1758               /* If a dependency already exists, don't create a new one.  */
1759               if (! find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
1760                 if (output_dependence (XEXP (pending_mem, 0), dest))
1761                   add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
1762
1763               pending = XEXP (pending, 1);
1764               pending_mem = XEXP (pending_mem, 1);
1765             }
1766
1767           if (last_pending_memory_flush)
1768             add_dependence (insn, last_pending_memory_flush, REG_DEP_ANTI);
1769
1770           add_insn_mem_dependence (&pending_write_insns, &pending_write_mems,
1771                                    insn, dest);
1772         }
1773       sched_analyze_2 (XEXP (dest, 0), insn);
1774     }
1775
1776   /* Analyze reads.  */
1777   if (GET_CODE (x) == SET)
1778     sched_analyze_2 (SET_SRC (x), insn);
1779 }
1780
1781 /* Analyze the uses of memory and registers in rtx X in INSN.  */
1782
1783 static void
1784 sched_analyze_2 (x, insn)
1785      rtx x;
1786      rtx insn;
1787 {
1788   register int i;
1789   register int j;
1790   register enum rtx_code code;
1791   register char *fmt;
1792
1793   if (x == 0)
1794     return;
1795
1796   code = GET_CODE (x);
1797
1798   switch (code)
1799     {
1800     case CONST_INT:
1801     case CONST_DOUBLE:
1802     case SYMBOL_REF:
1803     case CONST:
1804     case LABEL_REF:
1805       /* Ignore constants.  Note that we must handle CONST_DOUBLE here
1806          because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but
1807          this does not mean that this insn is using cc0.  */
1808       return;
1809
1810 #ifdef HAVE_cc0
1811     case CC0:
1812       {
1813         rtx link, prev;
1814
1815         /* There may be a note before this insn now, but all notes will
1816            be removed before we actually try to schedule the insns, so
1817            it won't cause a problem later.  We must avoid it here though.  */
1818
1819         /* User of CC0 depends on immediately preceding insn.  */
1820         SCHED_GROUP_P (insn) = 1;
1821
1822         /* Make a copy of all dependencies on the immediately previous insn,
1823            and add to this insn.  This is so that all the dependencies will
1824            apply to the group.  Remove an explicit dependence on this insn
1825            as SCHED_GROUP_P now represents it.  */
1826
1827         prev = PREV_INSN (insn);
1828         while (GET_CODE (prev) == NOTE)
1829           prev = PREV_INSN (prev);
1830
1831         if (find_insn_list (prev, LOG_LINKS (insn)))
1832           remove_dependence (insn, prev);
1833
1834         for (link = LOG_LINKS (prev); link; link = XEXP (link, 1))
1835           add_dependence (insn, XEXP (link, 0), REG_NOTE_KIND (link));
1836
1837         return;
1838       }
1839 #endif
1840
1841     case REG:
1842       {
1843         int regno = REGNO (x);
1844         if (regno < FIRST_PSEUDO_REGISTER)
1845           {
1846             int i;
1847
1848             i = HARD_REGNO_NREGS (regno, GET_MODE (x));
1849             while (--i >= 0)
1850               {
1851                 reg_last_uses[regno + i]
1852                   = gen_rtx (INSN_LIST, VOIDmode,
1853                              insn, reg_last_uses[regno + i]);
1854                 if (reg_last_sets[regno + i])
1855                   add_dependence (insn, reg_last_sets[regno + i], 0);
1856                 if ((call_used_regs[regno + i] || global_regs[regno + i])
1857                     && last_function_call)
1858                   /* Function calls clobber all call_used regs.  */
1859                   add_dependence (insn, last_function_call, REG_DEP_ANTI);
1860               }
1861           }
1862         else
1863           {
1864             reg_last_uses[regno]
1865               = gen_rtx (INSN_LIST, VOIDmode, insn, reg_last_uses[regno]);
1866             if (reg_last_sets[regno])
1867               add_dependence (insn, reg_last_sets[regno], 0);
1868
1869             /* Pseudos that are REG_EQUIV to something may be replaced
1870                by that during reloading.  We need only add dependencies for
1871                the address in the REG_EQUIV note.  */
1872             if (! reload_completed
1873                 && reg_known_equiv_p[regno]
1874                 && GET_CODE (reg_known_value[regno]) == MEM)
1875               sched_analyze_2 (XEXP (reg_known_value[regno], 0), insn);
1876
1877             /* If the register does not already cross any calls, then add this
1878                insn to the sched_before_next_call list so that it will still
1879                not cross calls after scheduling.  */
1880             if (reg_n_calls_crossed[regno] == 0)
1881               add_dependence (sched_before_next_call, insn, REG_DEP_ANTI);
1882           }
1883         return;
1884       }
1885
1886     case MEM:
1887       {
1888         /* Reading memory.  */
1889
1890         rtx pending, pending_mem;
1891
1892         pending = pending_read_insns;
1893         pending_mem = pending_read_mems;
1894         while (pending)
1895           {
1896             /* If a dependency already exists, don't create a new one.  */
1897             if (! find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
1898               if (read_dependence (XEXP (pending_mem, 0), x))
1899                 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
1900
1901             pending = XEXP (pending, 1);
1902             pending_mem = XEXP (pending_mem, 1);
1903           }
1904
1905         pending = pending_write_insns;
1906         pending_mem = pending_write_mems;
1907         while (pending)
1908           {
1909             /* If a dependency already exists, don't create a new one.  */
1910             if (! find_insn_list (XEXP (pending, 0), LOG_LINKS (insn)))
1911               if (true_dependence (XEXP (pending_mem, 0), x))
1912                 add_dependence (insn, XEXP (pending, 0), 0);
1913
1914             pending = XEXP (pending, 1);
1915             pending_mem = XEXP (pending_mem, 1);
1916           }
1917         if (last_pending_memory_flush)
1918           add_dependence (insn, last_pending_memory_flush, REG_DEP_ANTI);
1919
1920         /* Always add these dependencies to pending_reads, since
1921            this insn may be followed by a write.  */
1922         add_insn_mem_dependence (&pending_read_insns, &pending_read_mems,
1923                                  insn, x);
1924
1925         /* Take advantage of tail recursion here.  */
1926         sched_analyze_2 (XEXP (x, 0), insn);
1927         return;
1928       }
1929
1930     case ASM_OPERANDS:
1931     case ASM_INPUT:
1932     case UNSPEC_VOLATILE:
1933     case TRAP_IF:
1934       {
1935         rtx u;
1936
1937         /* Traditional and volatile asm instructions must be considered to use
1938            and clobber all hard registers, all pseudo-registers and all of
1939            memory.  So must TRAP_IF and UNSPEC_VOLATILE operations.
1940
1941            Consider for instance a volatile asm that changes the fpu rounding
1942            mode.  An insn should not be moved across this even if it only uses
1943            pseudo-regs because it might give an incorrectly rounded result.  */
1944         if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
1945           {
1946             int max_reg = max_reg_num ();
1947             for (i = 0; i < max_reg; i++)
1948               {
1949                 for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
1950                   add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
1951                 reg_last_uses[i] = 0;
1952                 if (reg_last_sets[i])
1953                   add_dependence (insn, reg_last_sets[i], 0);
1954                 reg_last_sets[i] = insn;
1955               }
1956
1957             flush_pending_lists (insn);
1958           }
1959
1960         /* For all ASM_OPERANDS, we must traverse the vector of input operands.
1961            We can not just fall through here since then we would be confused
1962            by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
1963            traditional asms unlike their normal usage.  */
1964
1965         if (code == ASM_OPERANDS)
1966           {
1967             for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
1968               sched_analyze_2 (ASM_OPERANDS_INPUT (x, j), insn);
1969             return;
1970           }
1971         break;
1972       }
1973
1974     case PRE_DEC:
1975     case POST_DEC:
1976     case PRE_INC:
1977     case POST_INC:
1978       /* These both read and modify the result.  We must handle them as writes
1979          to get proper dependencies for following instructions.  We must handle
1980          them as reads to get proper dependencies from this to previous
1981          instructions.  Thus we need to pass them to both sched_analyze_1
1982          and sched_analyze_2.  We must call sched_analyze_2 first in order
1983          to get the proper antecedent for the read.  */
1984       sched_analyze_2 (XEXP (x, 0), insn);
1985       sched_analyze_1 (x, insn);
1986       return;
1987     }
1988
1989   /* Other cases: walk the insn.  */
1990   fmt = GET_RTX_FORMAT (code);
1991   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1992     {
1993       if (fmt[i] == 'e')
1994         sched_analyze_2 (XEXP (x, i), insn);
1995       else if (fmt[i] == 'E')
1996         for (j = 0; j < XVECLEN (x, i); j++)
1997           sched_analyze_2 (XVECEXP (x, i, j), insn);
1998     }
1999 }
2000
2001 /* Analyze an INSN with pattern X to find all dependencies.  */
2002
2003 static void
2004 sched_analyze_insn (x, insn)
2005      rtx x, insn;
2006 {
2007   register RTX_CODE code = GET_CODE (x);
2008   rtx link;
2009
2010   if (code == SET || code == CLOBBER)
2011     sched_analyze_1 (x, insn);
2012   else if (code == PARALLEL)
2013     {
2014       register int i;
2015       for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
2016         {
2017           code = GET_CODE (XVECEXP (x, 0, i));
2018           if (code == SET || code == CLOBBER)
2019             sched_analyze_1 (XVECEXP (x, 0, i), insn);
2020           else
2021             sched_analyze_2 (XVECEXP (x, 0, i), insn);
2022         }
2023     }
2024   else
2025     sched_analyze_2 (x, insn);
2026
2027   /* Handle function calls and function returns created by the epilogue
2028      threading code.  */
2029   if (GET_CODE (insn) == CALL_INSN || GET_CODE (insn) == JUMP_INSN)
2030     {
2031       rtx dep_insn;
2032       rtx prev_dep_insn;
2033
2034       /* When scheduling instructions, we make sure calls don't lose their
2035          accompanying USE insns by depending them one on another in order.
2036
2037          Also, we must do the same thing for returns created by the epilogue
2038          threading code.  Note this code works only in this special case,
2039          because other passes make no guarantee that they will never emit
2040          an instruction between a USE and a RETURN.  There is such a guarantee
2041          for USE instructions immediately before a call.  */
2042
2043       prev_dep_insn = insn;
2044       dep_insn = PREV_INSN (insn);
2045       while (GET_CODE (dep_insn) == INSN
2046              && GET_CODE (PATTERN (dep_insn)) == USE)
2047         {
2048           SCHED_GROUP_P (prev_dep_insn) = 1;
2049
2050           /* Make a copy of all dependencies on dep_insn, and add to insn.
2051              This is so that all of the dependencies will apply to the
2052              group.  */
2053
2054           for (link = LOG_LINKS (dep_insn); link; link = XEXP (link, 1))
2055             add_dependence (insn, XEXP (link, 0), REG_NOTE_KIND (link));
2056
2057           prev_dep_insn = dep_insn;
2058           dep_insn = PREV_INSN (dep_insn);
2059         }
2060     }
2061 }
2062
2063 /* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
2064    for every dependency.  */
2065
2066 static int
2067 sched_analyze (head, tail)
2068      rtx head, tail;
2069 {
2070   register rtx insn;
2071   register int n_insns = 0;
2072   register rtx u;
2073   register int luid = 0;
2074
2075   for (insn = head; ; insn = NEXT_INSN (insn))
2076     {
2077       INSN_LUID (insn) = luid++;
2078
2079       if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
2080         {
2081           sched_analyze_insn (PATTERN (insn), insn);
2082           n_insns += 1;
2083         }
2084       else if (GET_CODE (insn) == CALL_INSN)
2085         {
2086           rtx dest = 0;
2087           rtx x;
2088           register int i;
2089
2090           /* Any instruction using a hard register which may get clobbered
2091              by a call needs to be marked as dependent on this call.
2092              This prevents a use of a hard return reg from being moved
2093              past a void call (i.e. it does not explicitly set the hard
2094              return reg).  */
2095
2096           /* If this call is followed by a NOTE_INSN_SETJMP, then assume that
2097              all registers, not just hard registers, may be clobbered by this
2098              call.  */
2099
2100           /* Insn, being a CALL_INSN, magically depends on
2101              `last_function_call' already.  */
2102
2103           if (NEXT_INSN (insn) && GET_CODE (NEXT_INSN (insn)) == NOTE
2104               && NOTE_LINE_NUMBER (NEXT_INSN (insn)) == NOTE_INSN_SETJMP)
2105             {
2106               int max_reg = max_reg_num ();
2107               for (i = 0; i < max_reg; i++)
2108                 {
2109                   for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
2110                     add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
2111                   reg_last_uses[i] = 0;
2112                   if (reg_last_sets[i])
2113                     add_dependence (insn, reg_last_sets[i], 0);
2114                   reg_last_sets[i] = insn;
2115                 }
2116
2117               /* Add a fake REG_NOTE which we will later convert
2118                  back into a NOTE_INSN_SETJMP note.  */
2119               REG_NOTES (insn) = gen_rtx (EXPR_LIST, REG_DEAD, constm1_rtx,
2120                                           REG_NOTES (insn));
2121             }
2122           else
2123             {
2124               for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2125                 if (call_used_regs[i] || global_regs[i])
2126                   {
2127                     for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
2128                       add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
2129                     reg_last_uses[i] = 0;
2130                     if (reg_last_sets[i])
2131                       add_dependence (insn, reg_last_sets[i], REG_DEP_ANTI);
2132                     reg_last_sets[i] = insn;
2133                   }
2134             }
2135
2136           /* For each insn which shouldn't cross a call, add a dependence
2137              between that insn and this call insn.  */
2138           x = LOG_LINKS (sched_before_next_call);
2139           while (x)
2140             {
2141               add_dependence (insn, XEXP (x, 0), REG_DEP_ANTI);
2142               x = XEXP (x, 1);
2143             }
2144           LOG_LINKS (sched_before_next_call) = 0;
2145
2146           sched_analyze_insn (PATTERN (insn), insn);
2147
2148           /* We don't need to flush memory for a function call which does
2149              not involve memory.  */
2150           if (! CONST_CALL_P (insn))
2151             {
2152               /* In the absence of interprocedural alias analysis,
2153                  we must flush all pending reads and writes, and
2154                  start new dependencies starting from here.  */
2155               flush_pending_lists (insn);
2156             }
2157
2158           /* Depend this function call (actually, the user of this
2159              function call) on all hard register clobberage.  */
2160           last_function_call = insn;
2161           n_insns += 1;
2162         }
2163
2164       if (insn == tail)
2165         return n_insns;
2166     }
2167 }
2168 \f
2169 /* Called when we see a set of a register.  If death is true, then we are
2170    scanning backwards.  Mark that register as unborn.  If nobody says
2171    otherwise, that is how things will remain.  If death is false, then we
2172    are scanning forwards.  Mark that register as being born.  */
2173
2174 static void
2175 sched_note_set (b, x, death)
2176      int b;
2177      rtx x;
2178      int death;
2179 {
2180   register int regno, j;
2181   register rtx reg = SET_DEST (x);
2182   int subreg_p = 0;
2183
2184   if (reg == 0)
2185     return;
2186
2187   while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == STRICT_LOW_PART
2188          || GET_CODE (reg) == SIGN_EXTRACT || GET_CODE (reg) == ZERO_EXTRACT)
2189     {
2190       /* Must treat modification of just one hardware register of a multi-reg
2191          value or just a byte field of a register exactly the same way that
2192          mark_set_1 in flow.c does, i.e. anything except a paradoxical subreg
2193          does not kill the entire register.  */
2194       if (GET_CODE (reg) != SUBREG
2195           || REG_SIZE (SUBREG_REG (reg)) > REG_SIZE (reg))
2196         subreg_p = 1;
2197
2198       reg = SUBREG_REG (reg);
2199     }
2200
2201   if (GET_CODE (reg) != REG)
2202     return;
2203
2204   /* Global registers are always live, so the code below does not apply
2205      to them.  */
2206
2207   regno = REGNO (reg);
2208   if (regno >= FIRST_PSEUDO_REGISTER || ! global_regs[regno])
2209     {
2210       register int offset = regno / REGSET_ELT_BITS;
2211       register REGSET_ELT_TYPE bit
2212         = (REGSET_ELT_TYPE) 1 << (regno % REGSET_ELT_BITS);
2213
2214       if (death)
2215         {
2216           /* If we only set part of the register, then this set does not
2217              kill it.  */
2218           if (subreg_p)
2219             return;
2220
2221           /* Try killing this register.  */
2222           if (regno < FIRST_PSEUDO_REGISTER)
2223             {
2224               int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
2225               while (--j >= 0)
2226                 {
2227                   offset = (regno + j) / REGSET_ELT_BITS;
2228                   bit = (REGSET_ELT_TYPE) 1 << ((regno + j) % REGSET_ELT_BITS);
2229
2230                   bb_live_regs[offset] &= ~bit;
2231                   bb_dead_regs[offset] |= bit;
2232                 }
2233             }
2234           else
2235             {
2236               bb_live_regs[offset] &= ~bit;
2237               bb_dead_regs[offset] |= bit;
2238             }
2239         }
2240       else
2241         {
2242           /* Make the register live again.  */
2243           if (regno < FIRST_PSEUDO_REGISTER)
2244             {
2245               int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
2246               while (--j >= 0)
2247                 {
2248                   offset = (regno + j) / REGSET_ELT_BITS;
2249                   bit = (REGSET_ELT_TYPE) 1 << ((regno + j) % REGSET_ELT_BITS);
2250
2251                   bb_live_regs[offset] |= bit;
2252                   bb_dead_regs[offset] &= ~bit;
2253                 }
2254             }
2255           else
2256             {
2257               bb_live_regs[offset] |= bit;
2258               bb_dead_regs[offset] &= ~bit;
2259             }
2260         }
2261     }
2262 }
2263 \f
2264 /* Macros and functions for keeping the priority queue sorted, and
2265    dealing with queueing and unqueueing of instructions.  */
2266
2267 #define SCHED_SORT(READY, NEW_READY, OLD_READY) \
2268   do { if ((NEW_READY) - (OLD_READY) == 1)                              \
2269          swap_sort (READY, NEW_READY);                                  \
2270        else if ((NEW_READY) - (OLD_READY) > 1)                          \
2271          qsort (READY, NEW_READY, sizeof (rtx), rank_for_schedule); }   \
2272   while (0)
2273
2274 /* Returns a positive value if y is preferred; returns a negative value if
2275    x is preferred.  Should never return 0, since that will make the sort
2276    unstable.  */
2277
2278 static int
2279 rank_for_schedule (x, y)
2280      rtx *x, *y;
2281 {
2282   rtx tmp = *y;
2283   rtx tmp2 = *x;
2284   rtx link;
2285   int tmp_class, tmp2_class;
2286   int value;
2287
2288   /* Choose the instruction with the highest priority, if different.  */
2289   if (value = INSN_PRIORITY (tmp) - INSN_PRIORITY (tmp2))
2290     return value;
2291
2292   if (last_scheduled_insn)
2293     {
2294       /* Classify the instructions into three classes:
2295          1) Data dependent on last schedule insn.
2296          2) Anti/Output dependent on last scheduled insn.
2297          3) Independent of last scheduled insn, or has latency of one.
2298          Choose the insn from the highest numbered class if different.  */
2299       link = find_insn_list (tmp, LOG_LINKS (last_scheduled_insn));
2300       if (link == 0 || insn_cost (tmp, link, last_scheduled_insn) == 1)
2301         tmp_class = 3;
2302       else if (REG_NOTE_KIND (link) == 0) /* Data dependence.  */
2303         tmp_class = 1;
2304       else
2305         tmp_class = 2;
2306
2307       link = find_insn_list (tmp2, LOG_LINKS (last_scheduled_insn));
2308       if (link == 0 || insn_cost (tmp2, link, last_scheduled_insn) == 1)
2309         tmp2_class = 3;
2310       else if (REG_NOTE_KIND (link) == 0) /* Data dependence.  */
2311         tmp2_class = 1;
2312       else
2313         tmp2_class = 2;
2314
2315       if (value = tmp_class - tmp2_class)
2316         return value;
2317     }
2318
2319   /* If insns are equally good, sort by INSN_LUID (original insn order),
2320      so that we make the sort stable.  This minimizes instruction movement,
2321      thus minimizing sched's effect on debugging and cross-jumping.  */
2322   return INSN_LUID (tmp) - INSN_LUID (tmp2);
2323 }
2324
2325 /* Resort the array A in which only element at index N may be out of order.  */
2326
2327 __inline static void
2328 swap_sort (a, n)
2329      rtx *a;
2330      int n;
2331 {
2332   rtx insn = a[n-1];
2333   int i = n-2;
2334
2335   while (i >= 0 && rank_for_schedule (a+i, &insn) >= 0)
2336     {
2337       a[i+1] = a[i];
2338       i -= 1;
2339     }
2340   a[i+1] = insn;
2341 }
2342
2343 static int max_priority;
2344
2345 /* Add INSN to the insn queue so that it fires at least N_CYCLES
2346    before the currently executing insn.  */
2347
2348 __inline static void
2349 queue_insn (insn, n_cycles)
2350      rtx insn;
2351      int n_cycles;
2352 {
2353   int next_q = NEXT_Q_AFTER (q_ptr, n_cycles);
2354   NEXT_INSN (insn) = insn_queue[next_q];
2355   insn_queue[next_q] = insn;
2356   q_size += 1;
2357 }
2358
2359 /* Return nonzero if PAT is the pattern of an insn which makes a
2360    register live.  */
2361
2362 __inline static int
2363 birthing_insn_p (pat)
2364      rtx pat;
2365 {
2366   int j;
2367
2368   if (reload_completed == 1)
2369     return 0;
2370
2371   if (GET_CODE (pat) == SET
2372       && GET_CODE (SET_DEST (pat)) == REG)
2373     {
2374       rtx dest = SET_DEST (pat);
2375       int i = REGNO (dest);
2376       int offset = i / REGSET_ELT_BITS;
2377       REGSET_ELT_TYPE bit = (REGSET_ELT_TYPE) 1 << (i % REGSET_ELT_BITS);
2378
2379       /* It would be more accurate to use refers_to_regno_p or
2380          reg_mentioned_p to determine when the dest is not live before this
2381          insn.  */
2382
2383       if (bb_live_regs[offset] & bit)
2384         return (reg_n_sets[i] == 1);
2385
2386       return 0;
2387     }
2388   if (GET_CODE (pat) == PARALLEL)
2389     {
2390       for (j = 0; j < XVECLEN (pat, 0); j++)
2391         if (birthing_insn_p (XVECEXP (pat, 0, j)))
2392           return 1;
2393     }
2394   return 0;
2395 }
2396
2397 /* PREV is an insn that is ready to execute.  Adjust its priority if that
2398    will help shorten register lifetimes.  */
2399
2400 __inline static void
2401 adjust_priority (prev)
2402      rtx prev;
2403 {
2404   /* Trying to shorten register lives after reload has completed
2405      is useless and wrong.  It gives inaccurate schedules.  */
2406   if (reload_completed == 0)
2407     {
2408       rtx note;
2409       int n_deaths = 0;
2410
2411       /* ??? This code has no effect, because REG_DEAD notes are removed
2412          before we ever get here.  */
2413       for (note = REG_NOTES (prev); note; note = XEXP (note, 1))
2414         if (REG_NOTE_KIND (note) == REG_DEAD)
2415           n_deaths += 1;
2416
2417       /* Defer scheduling insns which kill registers, since that
2418          shortens register lives.  Prefer scheduling insns which
2419          make registers live for the same reason.  */
2420       switch (n_deaths)
2421         {
2422         default:
2423           INSN_PRIORITY (prev) >>= 3;
2424           break;
2425         case 3:
2426           INSN_PRIORITY (prev) >>= 2;
2427           break;
2428         case 2:
2429         case 1:
2430           INSN_PRIORITY (prev) >>= 1;
2431           break;
2432         case 0:
2433           if (birthing_insn_p (PATTERN (prev)))
2434             {
2435               int max = max_priority;
2436
2437               if (max > INSN_PRIORITY (prev))
2438                 INSN_PRIORITY (prev) = max;
2439             }
2440           break;
2441         }
2442     }
2443 }
2444
2445 /* INSN is the "currently executing insn".  Launch each insn which was
2446    waiting on INSN (in the backwards dataflow sense).  READY is a
2447    vector of insns which are ready to fire.  N_READY is the number of
2448    elements in READY.  CLOCK is the current virtual cycle.  */
2449
2450 static int
2451 schedule_insn (insn, ready, n_ready, clock)
2452      rtx insn;
2453      rtx *ready;
2454      int n_ready;
2455      int clock;
2456 {
2457   rtx link;
2458   int new_ready = n_ready;
2459
2460   if (MAX_BLOCKAGE > 1)
2461     schedule_unit (insn_unit (insn), insn, clock);
2462
2463   if (LOG_LINKS (insn) == 0)
2464     return n_ready;
2465
2466   /* This is used by the function adjust_priority above.  */
2467   if (n_ready > 0)
2468     max_priority = MAX (INSN_PRIORITY (ready[0]), INSN_PRIORITY (insn));
2469   else
2470     max_priority = INSN_PRIORITY (insn);
2471
2472   for (link = LOG_LINKS (insn); link != 0; link = XEXP (link, 1))
2473     {
2474       rtx prev = XEXP (link, 0);
2475       int cost = insn_cost (prev, link, insn);
2476
2477       if ((INSN_REF_COUNT (prev) -= 1) != 0)
2478         {
2479           /* We satisfied one requirement to fire PREV.  Record the earliest
2480              time when PREV can fire.  No need to do this if the cost is 1,
2481              because PREV can fire no sooner than the next cycle.  */
2482           if (cost > 1)
2483             INSN_TICK (prev) = MAX (INSN_TICK (prev), clock + cost);
2484         }
2485       else
2486         {
2487           /* We satisfied the last requirement to fire PREV.  Ensure that all
2488              timing requirements are satisfied.  */
2489           if (INSN_TICK (prev) - clock > cost)
2490             cost = INSN_TICK (prev) - clock;
2491
2492           /* Adjust the priority of PREV and either put it on the ready
2493              list or queue it.  */
2494           adjust_priority (prev);
2495           if (cost <= 1)
2496             ready[new_ready++] = prev;
2497           else
2498             queue_insn (prev, cost);
2499         }
2500     }
2501
2502   return new_ready;
2503 }
2504
2505 /* Given N_READY insns in the ready list READY at time CLOCK, queue
2506    those that are blocked due to function unit hazards and rearrange
2507    the remaining ones to minimize subsequent function unit hazards.  */
2508
2509 static int
2510 schedule_select (ready, n_ready, clock, file)
2511      rtx *ready;
2512      int n_ready, clock;
2513      FILE *file;
2514 {
2515   int pri = INSN_PRIORITY (ready[0]);
2516   int i, j, k, q, cost, best_cost, best_insn = 0, new_ready = n_ready;
2517   rtx insn;
2518
2519   /* Work down the ready list in groups of instructions with the same
2520      priority value.  Queue insns in the group that are blocked and
2521      select among those that remain for the one with the largest
2522      potential hazard.  */
2523   for (i = 0; i < n_ready; i = j)
2524     {
2525       int opri = pri;
2526       for (j = i + 1; j < n_ready; j++)
2527         if ((pri = INSN_PRIORITY (ready[j])) != opri)
2528           break;
2529
2530       /* Queue insns in the group that are blocked.  */
2531       for (k = i, q = 0; k < j; k++)
2532         {
2533           insn = ready[k];
2534           if ((cost = actual_hazard (insn_unit (insn), insn, clock, 0)) != 0)
2535             {
2536               q++;
2537               ready[k] = 0;
2538               queue_insn (insn, cost);
2539               if (file)
2540                 fprintf (file, "\n;; blocking insn %d for %d cycles",
2541                          INSN_UID (insn), cost);
2542             }
2543         }
2544       new_ready -= q;
2545
2546       /* Check the next group if all insns were queued.  */
2547       if (j - i - q == 0)
2548         continue;
2549
2550       /* If more than one remains, select the first one with the largest
2551          potential hazard.  */
2552       else if (j - i - q > 1)
2553         {
2554           best_cost = -1;
2555           for (k = i; k < j; k++)
2556             {
2557               if ((insn = ready[k]) == 0)
2558                 continue;
2559               if ((cost = potential_hazard (insn_unit (insn), insn, 0))
2560                   > best_cost)
2561                 {
2562                   best_cost = cost;
2563                   best_insn = k;
2564                 }
2565             }
2566         }
2567       /* We have found a suitable insn to schedule.  */
2568       break;
2569     }
2570
2571   /* Move the best insn to be front of the ready list.  */
2572   if (best_insn != 0)
2573     {
2574       if (file)
2575         {
2576           fprintf (file, ", now");
2577           for (i = 0; i < n_ready; i++)
2578             if (ready[i])
2579               fprintf (file, " %d", INSN_UID (ready[i]));
2580           fprintf (file, "\n;; insn %d has a greater potential hazard",
2581                    INSN_UID (ready[best_insn]));
2582         }
2583       for (i = best_insn; i > 0; i--)
2584         {
2585           insn = ready[i-1];
2586           ready[i-1] = ready[i];
2587           ready[i] = insn;
2588         }
2589     }
2590
2591   /* Compact the ready list.  */
2592   if (new_ready < n_ready)
2593     for (i = j = 0; i < n_ready; i++)
2594       if (ready[i])
2595         ready[j++] = ready[i];
2596
2597   return new_ready;
2598 }
2599
2600 /* Add a REG_DEAD note for REG to INSN, reusing a REG_DEAD note from the
2601    dead_notes list.  */
2602
2603 static void
2604 create_reg_dead_note (reg, insn)
2605      rtx reg, insn;
2606 {
2607   rtx link, backlink;
2608
2609   /* The number of registers killed after scheduling must be the same as the
2610      number of registers killed before scheduling.  The number of REG_DEAD
2611      notes may not be conserved, i.e. two SImode hard register REG_DEAD notes
2612      might become one DImode hard register REG_DEAD note, but the number of
2613      registers killed will be conserved.
2614
2615      We carefully remove REG_DEAD notes from the dead_notes list, so that
2616      there will be none left at the end.  If we run out early, then there
2617      is a bug somewhere in flow, combine and/or sched.  */
2618
2619   if (dead_notes == 0)
2620     {
2621 #if 1
2622       abort ();
2623 #else
2624       link = rtx_alloc (EXPR_LIST);
2625       PUT_REG_NOTE_KIND (link, REG_DEAD);
2626 #endif
2627     }
2628   else
2629     {
2630       /* Number of regs killed by REG.  */
2631       int regs_killed = (REGNO (reg) >= FIRST_PSEUDO_REGISTER ? 1
2632                          : HARD_REGNO_NREGS (REGNO (reg), GET_MODE (reg)));
2633       /* Number of regs killed by REG_DEAD notes taken off the list.  */
2634       int reg_note_regs;
2635
2636       link = dead_notes;
2637       reg_note_regs = (REGNO (XEXP (link, 0)) >= FIRST_PSEUDO_REGISTER ? 1
2638                        : HARD_REGNO_NREGS (REGNO (XEXP (link, 0)),
2639                                            GET_MODE (XEXP (link, 0))));
2640       while (reg_note_regs < regs_killed)
2641         {
2642           link = XEXP (link, 1);
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         }
2647       dead_notes = XEXP (link, 1);
2648
2649       /* If we took too many regs kills off, put the extra ones back.  */
2650       while (reg_note_regs > regs_killed)
2651         {
2652           rtx temp_reg, temp_link;
2653
2654           temp_reg = gen_rtx (REG, word_mode, 0);
2655           temp_link = rtx_alloc (EXPR_LIST);
2656           PUT_REG_NOTE_KIND (temp_link, REG_DEAD);
2657           XEXP (temp_link, 0) = temp_reg;
2658           XEXP (temp_link, 1) = dead_notes;
2659           dead_notes = temp_link;
2660           reg_note_regs--;
2661         }
2662     }
2663
2664   XEXP (link, 0) = reg;
2665   XEXP (link, 1) = REG_NOTES (insn);
2666   REG_NOTES (insn) = link;
2667 }
2668
2669 /* Subroutine on attach_deaths_insn--handles the recursive search
2670    through INSN.  If SET_P is true, then x is being modified by the insn.  */
2671
2672 static void
2673 attach_deaths (x, insn, set_p)
2674      rtx x;
2675      rtx insn;
2676      int set_p;
2677 {
2678   register int i;
2679   register int j;
2680   register enum rtx_code code;
2681   register char *fmt;
2682
2683   if (x == 0)
2684     return;
2685
2686   code = GET_CODE (x);
2687
2688   switch (code)
2689     {
2690     case CONST_INT:
2691     case CONST_DOUBLE:
2692     case LABEL_REF:
2693     case SYMBOL_REF:
2694     case CONST:
2695     case CODE_LABEL:
2696     case PC:
2697     case CC0:
2698       /* Get rid of the easy cases first.  */
2699       return;
2700
2701     case REG:
2702       {
2703         /* If the register dies in this insn, queue that note, and mark
2704            this register as needing to die.  */
2705         /* This code is very similar to mark_used_1 (if set_p is false)
2706            and mark_set_1 (if set_p is true) in flow.c.  */
2707
2708         register int regno = REGNO (x);
2709         register int offset = regno / REGSET_ELT_BITS;
2710         register REGSET_ELT_TYPE bit
2711           = (REGSET_ELT_TYPE) 1 << (regno % REGSET_ELT_BITS);
2712         REGSET_ELT_TYPE all_needed = (old_live_regs[offset] & bit);
2713         REGSET_ELT_TYPE some_needed = (old_live_regs[offset] & bit);
2714
2715         if (set_p)
2716           return;
2717
2718         if (regno < FIRST_PSEUDO_REGISTER)
2719           {
2720             int n;
2721
2722             n = HARD_REGNO_NREGS (regno, GET_MODE (x));
2723             while (--n > 0)
2724               {
2725                 some_needed |= (old_live_regs[(regno + n) / REGSET_ELT_BITS]
2726                                 & ((REGSET_ELT_TYPE) 1
2727                                    << ((regno + n) % REGSET_ELT_BITS)));
2728                 all_needed &= (old_live_regs[(regno + n) / REGSET_ELT_BITS]
2729                                & ((REGSET_ELT_TYPE) 1
2730                                   << ((regno + n) % REGSET_ELT_BITS)));
2731               }
2732           }
2733
2734         /* If it wasn't live before we started, then add a REG_DEAD note.
2735            We must check the previous lifetime info not the current info,
2736            because we may have to execute this code several times, e.g.
2737            once for a clobber (which doesn't add a note) and later
2738            for a use (which does add a note).
2739
2740            Always make the register live.  We must do this even if it was
2741            live before, because this may be an insn which sets and uses
2742            the same register, in which case the register has already been
2743            killed, so we must make it live again.
2744
2745            Global registers are always live, and should never have a REG_DEAD
2746            note added for them, so none of the code below applies to them.  */
2747
2748         if (regno >= FIRST_PSEUDO_REGISTER || ! global_regs[regno])
2749           {
2750             /* Never add REG_DEAD notes for the FRAME_POINTER_REGNUM or the
2751                STACK_POINTER_REGNUM, since these are always considered to be
2752                live.  Similarly for ARG_POINTER_REGNUM if it is fixed.  */
2753             if (regno != FRAME_POINTER_REGNUM
2754 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
2755                 && ! (regno == HARD_FRAME_POINTER_REGNUM)
2756 #endif
2757 #if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
2758                 && ! (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
2759 #endif
2760                 && regno != STACK_POINTER_REGNUM)
2761               {
2762                 if (! all_needed && ! dead_or_set_p (insn, x))
2763                   {
2764                     /* If none of the words in X is needed, make a REG_DEAD
2765                        note.  Otherwise, we must make partial REG_DEAD
2766                        notes.  */
2767                     if (! some_needed)
2768                       create_reg_dead_note (x, insn);
2769                     else
2770                       {
2771                         int i;
2772
2773                         /* Don't make a REG_DEAD note for a part of a
2774                            register that is set in the insn.  */
2775                         for (i = HARD_REGNO_NREGS (regno, GET_MODE (x)) - 1;
2776                              i >= 0; i--)
2777                           if ((old_live_regs[(regno + i) / REGSET_ELT_BITS]
2778                                & ((REGSET_ELT_TYPE) 1
2779                                   << ((regno +i) % REGSET_ELT_BITS))) == 0
2780                               && ! dead_or_set_regno_p (insn, regno + i))
2781                             create_reg_dead_note (gen_rtx (REG, word_mode,
2782                                                            regno + i),
2783                                                   insn);
2784                       }
2785                   }
2786               }
2787
2788             if (regno < FIRST_PSEUDO_REGISTER)
2789               {
2790                 int j = HARD_REGNO_NREGS (regno, GET_MODE (x));
2791                 while (--j >= 0)
2792                   {
2793                     offset = (regno + j) / REGSET_ELT_BITS;
2794                     bit
2795                       = (REGSET_ELT_TYPE) 1 << ((regno + j) % REGSET_ELT_BITS);
2796
2797                     bb_dead_regs[offset] &= ~bit;
2798                     bb_live_regs[offset] |= bit;
2799                   }
2800               }
2801             else
2802               {
2803                 bb_dead_regs[offset] &= ~bit;
2804                 bb_live_regs[offset] |= bit;
2805               }
2806           }
2807         return;
2808       }
2809
2810     case MEM:
2811       /* Handle tail-recursive case.  */
2812       attach_deaths (XEXP (x, 0), insn, 0);
2813       return;
2814
2815     case SUBREG:
2816     case STRICT_LOW_PART:
2817       /* These two cases preserve the value of SET_P, so handle them
2818          separately.  */
2819       attach_deaths (XEXP (x, 0), insn, set_p);
2820       return;
2821
2822     case ZERO_EXTRACT:
2823     case SIGN_EXTRACT:
2824       /* This case preserves the value of SET_P for the first operand, but
2825          clears it for the other two.  */
2826       attach_deaths (XEXP (x, 0), insn, set_p);
2827       attach_deaths (XEXP (x, 1), insn, 0);
2828       attach_deaths (XEXP (x, 2), insn, 0);
2829       return;
2830
2831     default:
2832       /* Other cases: walk the insn.  */
2833       fmt = GET_RTX_FORMAT (code);
2834       for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2835         {
2836           if (fmt[i] == 'e')
2837             attach_deaths (XEXP (x, i), insn, 0);
2838           else if (fmt[i] == 'E')
2839             for (j = 0; j < XVECLEN (x, i); j++)
2840               attach_deaths (XVECEXP (x, i, j), insn, 0);
2841         }
2842     }
2843 }
2844
2845 /* After INSN has executed, add register death notes for each register
2846    that is dead after INSN.  */
2847
2848 static void
2849 attach_deaths_insn (insn)
2850      rtx insn;
2851 {
2852   rtx x = PATTERN (insn);
2853   register RTX_CODE code = GET_CODE (x);
2854
2855   if (code == SET)
2856     {
2857       attach_deaths (SET_SRC (x), insn, 0);
2858
2859       /* A register might die here even if it is the destination, e.g.
2860          it is the target of a volatile read and is otherwise unused.
2861          Hence we must always call attach_deaths for the SET_DEST.  */
2862       attach_deaths (SET_DEST (x), insn, 1);
2863     }
2864   else if (code == PARALLEL)
2865     {
2866       register int i;
2867       for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
2868         {
2869           code = GET_CODE (XVECEXP (x, 0, i));
2870           if (code == SET)
2871             {
2872               attach_deaths (SET_SRC (XVECEXP (x, 0, i)), insn, 0);
2873
2874               attach_deaths (SET_DEST (XVECEXP (x, 0, i)), insn, 1);
2875             }
2876           /* Flow does not add REG_DEAD notes to registers that die in
2877              clobbers, so we can't either.  */
2878           else if (code != CLOBBER)
2879             attach_deaths (XVECEXP (x, 0, i), insn, 0);
2880         }
2881     }
2882   /* If this is a CLOBBER, only add REG_DEAD notes to registers inside a
2883      MEM being clobbered, just like flow.  */
2884   else if (code == CLOBBER && GET_CODE (XEXP (x, 0)) == MEM)
2885     attach_deaths (XEXP (XEXP (x, 0), 0), insn, 0);
2886   /* Otherwise don't add a death note to things being clobbered.  */
2887   else if (code != CLOBBER)
2888     attach_deaths (x, insn, 0);
2889 }
2890
2891 /* Delete notes beginning with INSN and maybe put them in the chain
2892    of notes ended by NOTE_LIST.
2893    Returns the insn following the notes.  */
2894
2895 static rtx
2896 unlink_notes (insn, tail)
2897      rtx insn, tail;
2898 {
2899   rtx prev = PREV_INSN (insn);
2900
2901   while (insn != tail && GET_CODE (insn) == NOTE)
2902     {
2903       rtx next = NEXT_INSN (insn);
2904       /* Delete the note from its current position.  */
2905       if (prev)
2906         NEXT_INSN (prev) = next;
2907       if (next)
2908         PREV_INSN (next) = prev;
2909
2910       if (write_symbols != NO_DEBUG && NOTE_LINE_NUMBER (insn) > 0)
2911         /* Record line-number notes so they can be reused.  */
2912         LINE_NOTE (insn) = insn;
2913
2914       /* Don't save away NOTE_INSN_SETJMPs, because they must remain
2915          immediately after the call they follow.  We use a fake
2916          (REG_DEAD (const_int -1)) note to remember them.  */
2917       else if (NOTE_LINE_NUMBER (insn) != NOTE_INSN_SETJMP)
2918         {
2919           /* Insert the note at the end of the notes list.  */
2920           PREV_INSN (insn) = note_list;
2921           if (note_list)
2922             NEXT_INSN (note_list) = insn;
2923           note_list = insn;
2924         }
2925
2926       insn = next;
2927     }
2928   return insn;
2929 }
2930
2931 /* Constructor for `sometimes' data structure.  */
2932
2933 static int
2934 new_sometimes_live (regs_sometimes_live, offset, bit, sometimes_max)
2935      struct sometimes *regs_sometimes_live;
2936      int offset, bit;
2937      int sometimes_max;
2938 {
2939   register struct sometimes *p;
2940   register int regno = offset * REGSET_ELT_BITS + bit;
2941   int i;
2942
2943   /* There should never be a register greater than max_regno here.  If there
2944      is, it means that a define_split has created a new pseudo reg.  This
2945      is not allowed, since there will not be flow info available for any
2946      new register, so catch the error here.  */
2947   if (regno >= max_regno)
2948     abort ();
2949
2950   p = &regs_sometimes_live[sometimes_max];
2951   p->offset = offset;
2952   p->bit = bit;
2953   p->live_length = 0;
2954   p->calls_crossed = 0;
2955   sometimes_max++;
2956   return sometimes_max;
2957 }
2958
2959 /* Count lengths of all regs we are currently tracking,
2960    and find new registers no longer live.  */
2961
2962 static void
2963 finish_sometimes_live (regs_sometimes_live, sometimes_max)
2964      struct sometimes *regs_sometimes_live;
2965      int sometimes_max;
2966 {
2967   int i;
2968
2969   for (i = 0; i < sometimes_max; i++)
2970     {
2971       register struct sometimes *p = &regs_sometimes_live[i];
2972       int regno;
2973
2974       regno = p->offset * REGSET_ELT_BITS + p->bit;
2975
2976       sched_reg_live_length[regno] += p->live_length;
2977       sched_reg_n_calls_crossed[regno] += p->calls_crossed;
2978     }
2979 }
2980
2981 /* Use modified list scheduling to rearrange insns in basic block
2982    B.  FILE, if nonzero, is where we dump interesting output about
2983    this pass.  */
2984
2985 static void
2986 schedule_block (b, file)
2987      int b;
2988      FILE *file;
2989 {
2990   rtx insn, last;
2991   rtx last_note = 0;
2992   rtx *ready, link;
2993   int i, j, n_ready = 0, new_ready, n_insns = 0;
2994   int sched_n_insns = 0;
2995   int clock;
2996 #define NEED_NOTHING    0
2997 #define NEED_HEAD       1
2998 #define NEED_TAIL       2
2999   int new_needs;
3000
3001   /* HEAD and TAIL delimit the region being scheduled.  */
3002   rtx head = basic_block_head[b];
3003   rtx tail = basic_block_end[b];
3004   /* PREV_HEAD and NEXT_TAIL are the boundaries of the insns
3005      being scheduled.  When the insns have been ordered,
3006      these insns delimit where the new insns are to be
3007      spliced back into the insn chain.  */
3008   rtx next_tail;
3009   rtx prev_head;
3010
3011   /* Keep life information accurate.  */
3012   register struct sometimes *regs_sometimes_live;
3013   int sometimes_max;
3014
3015   if (file)
3016     fprintf (file, ";;\t -- basic block number %d from %d to %d --\n",
3017              b, INSN_UID (basic_block_head[b]), INSN_UID (basic_block_end[b]));
3018
3019   i = max_reg_num ();
3020   reg_last_uses = (rtx *) alloca (i * sizeof (rtx));
3021   bzero (reg_last_uses, i * sizeof (rtx));
3022   reg_last_sets = (rtx *) alloca (i * sizeof (rtx));
3023   bzero (reg_last_sets, i * sizeof (rtx));
3024   clear_units ();
3025
3026   /* Remove certain insns at the beginning from scheduling,
3027      by advancing HEAD.  */
3028
3029   /* At the start of a function, before reload has run, don't delay getting
3030      parameters from hard registers into pseudo registers.  */
3031   if (reload_completed == 0 && b == 0)
3032     {
3033       while (head != tail
3034              && GET_CODE (head) == NOTE
3035              && NOTE_LINE_NUMBER (head) != NOTE_INSN_FUNCTION_BEG)
3036         head = NEXT_INSN (head);
3037       while (head != tail
3038              && GET_CODE (head) == INSN
3039              && GET_CODE (PATTERN (head)) == SET)
3040         {
3041           rtx src = SET_SRC (PATTERN (head));
3042           while (GET_CODE (src) == SUBREG
3043                  || GET_CODE (src) == SIGN_EXTEND
3044                  || GET_CODE (src) == ZERO_EXTEND
3045                  || GET_CODE (src) == SIGN_EXTRACT
3046                  || GET_CODE (src) == ZERO_EXTRACT)
3047             src = XEXP (src, 0);
3048           if (GET_CODE (src) != REG
3049               || REGNO (src) >= FIRST_PSEUDO_REGISTER)
3050             break;
3051           /* Keep this insn from ever being scheduled.  */
3052           INSN_REF_COUNT (head) = 1;
3053           head = NEXT_INSN (head);
3054         }
3055     }
3056
3057   /* Don't include any notes or labels at the beginning of the
3058      basic block, or notes at the ends of basic blocks.  */
3059   while (head != tail)
3060     {
3061       if (GET_CODE (head) == NOTE)
3062         head = NEXT_INSN (head);
3063       else if (GET_CODE (tail) == NOTE)
3064         tail = PREV_INSN (tail);
3065       else if (GET_CODE (head) == CODE_LABEL)
3066         head = NEXT_INSN (head);
3067       else break;
3068     }
3069   /* If the only insn left is a NOTE or a CODE_LABEL, then there is no need
3070      to schedule this block.  */
3071   if (head == tail
3072       && (GET_CODE (head) == NOTE || GET_CODE (head) == CODE_LABEL))
3073     return;
3074
3075 #if 0
3076   /* This short-cut doesn't work.  It does not count call insns crossed by
3077      registers in reg_sometimes_live.  It does not mark these registers as
3078      dead if they die in this block.  It does not mark these registers live
3079      (or create new reg_sometimes_live entries if necessary) if they are born
3080      in this block.
3081
3082      The easy solution is to just always schedule a block.  This block only
3083      has one insn, so this won't slow down this pass by much.  */
3084
3085   if (head == tail)
3086     return;
3087 #endif
3088
3089   /* Now HEAD through TAIL are the insns actually to be rearranged;
3090      Let PREV_HEAD and NEXT_TAIL enclose them.  */
3091   prev_head = PREV_INSN (head);
3092   next_tail = NEXT_INSN (tail);
3093
3094   /* Initialize basic block data structures.  */
3095   dead_notes = 0;
3096   pending_read_insns = 0;
3097   pending_read_mems = 0;
3098   pending_write_insns = 0;
3099   pending_write_mems = 0;
3100   pending_lists_length = 0;
3101   last_pending_memory_flush = 0;
3102   last_function_call = 0;
3103   last_scheduled_insn = 0;
3104
3105   LOG_LINKS (sched_before_next_call) = 0;
3106
3107   n_insns += sched_analyze (head, tail);
3108   if (n_insns == 0)
3109     {
3110       free_pending_lists ();
3111       return;
3112     }
3113
3114   /* Allocate vector to hold insns to be rearranged (except those
3115      insns which are controlled by an insn with SCHED_GROUP_P set).
3116      All these insns are included between ORIG_HEAD and ORIG_TAIL,
3117      as those variables ultimately are set up.  */
3118   ready = (rtx *) alloca ((n_insns+1) * sizeof (rtx));
3119
3120   /* TAIL is now the last of the insns to be rearranged.
3121      Put those insns into the READY vector.  */
3122   insn = tail;
3123
3124   /* For all branches, calls, uses, and cc0 setters, force them to remain
3125      in order at the end of the block by adding dependencies and giving
3126      the last a high priority.  There may be notes present, and prev_head
3127      may also be a note.
3128
3129      Branches must obviously remain at the end.  Calls should remain at the
3130      end since moving them results in worse register allocation.  Uses remain
3131      at the end to ensure proper register allocation.  cc0 setters remaim
3132      at the end because they can't be moved away from their cc0 user.  */
3133   last = 0;
3134   while (GET_CODE (insn) == CALL_INSN || GET_CODE (insn) == JUMP_INSN
3135          || (GET_CODE (insn) == INSN
3136              && (GET_CODE (PATTERN (insn)) == USE
3137 #ifdef HAVE_cc0
3138                  || sets_cc0_p (PATTERN (insn))
3139 #endif
3140                  ))
3141          || GET_CODE (insn) == NOTE)
3142     {
3143       if (GET_CODE (insn) != NOTE)
3144         {
3145           priority (insn);
3146           if (last == 0)
3147             {
3148               ready[n_ready++] = insn;
3149               INSN_PRIORITY (insn) = TAIL_PRIORITY - i;
3150               INSN_REF_COUNT (insn) = 0;
3151             }
3152           else if (! find_insn_list (insn, LOG_LINKS (last)))
3153             {
3154               add_dependence (last, insn, REG_DEP_ANTI);
3155               INSN_REF_COUNT (insn)++;
3156             }
3157           last = insn;
3158
3159           /* Skip over insns that are part of a group.  */
3160           while (SCHED_GROUP_P (insn))
3161             {
3162               insn = prev_nonnote_insn (insn);
3163               priority (insn);
3164             }
3165         }
3166
3167       insn = PREV_INSN (insn);
3168       /* Don't overrun the bounds of the basic block.  */
3169       if (insn == prev_head)
3170         break;
3171     }
3172
3173   /* Assign priorities to instructions.  Also check whether they
3174      are in priority order already.  If so then I will be nonnegative.
3175      We use this shortcut only before reloading.  */
3176 #if 0
3177   i = reload_completed ? DONE_PRIORITY : MAX_PRIORITY;
3178 #endif
3179
3180   for (; insn != prev_head; insn = PREV_INSN (insn))
3181     {
3182       if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
3183         {
3184           priority (insn);
3185           if (INSN_REF_COUNT (insn) == 0)
3186             {
3187               if (last == 0)
3188                 ready[n_ready++] = insn;
3189               else
3190                 {
3191                   /* Make this dependent on the last of the instructions
3192                      that must remain in order at the end of the block.  */
3193                   add_dependence (last, insn, REG_DEP_ANTI);
3194                   INSN_REF_COUNT (insn) = 1;
3195                 }
3196             }
3197           if (SCHED_GROUP_P (insn))
3198             {
3199               while (SCHED_GROUP_P (insn))
3200                 {
3201                   insn = PREV_INSN (insn);
3202                   while (GET_CODE (insn) == NOTE)
3203                     insn = PREV_INSN (insn);
3204                   priority (insn);
3205                 }
3206               continue;
3207             }
3208 #if 0
3209           if (i < 0)
3210             continue;
3211           if (INSN_PRIORITY (insn) < i)
3212             i = INSN_PRIORITY (insn);
3213           else if (INSN_PRIORITY (insn) > i)
3214             i = DONE_PRIORITY;
3215 #endif
3216         }
3217     }
3218
3219 #if 0
3220   /* This short-cut doesn't work.  It does not count call insns crossed by
3221      registers in reg_sometimes_live.  It does not mark these registers as
3222      dead if they die in this block.  It does not mark these registers live
3223      (or create new reg_sometimes_live entries if necessary) if they are born
3224      in this block.
3225
3226      The easy solution is to just always schedule a block.  These blocks tend
3227      to be very short, so this doesn't slow down this pass by much.  */
3228
3229   /* If existing order is good, don't bother to reorder.  */
3230   if (i != DONE_PRIORITY)
3231     {
3232       if (file)
3233         fprintf (file, ";; already scheduled\n");
3234
3235       if (reload_completed == 0)
3236         {
3237           for (i = 0; i < sometimes_max; i++)
3238             regs_sometimes_live[i].live_length += n_insns;
3239
3240           finish_sometimes_live (regs_sometimes_live, sometimes_max);
3241         }
3242       free_pending_lists ();
3243       return;
3244     }
3245 #endif
3246
3247   /* Scan all the insns to be scheduled, removing NOTE insns
3248      and register death notes.
3249      Line number NOTE insns end up in NOTE_LIST.
3250      Register death notes end up in DEAD_NOTES.
3251
3252      Recreate the register life information for the end of this basic
3253      block.  */
3254
3255   if (reload_completed == 0)
3256     {
3257       bcopy (basic_block_live_at_start[b], bb_live_regs, regset_bytes);
3258       bzero (bb_dead_regs, regset_bytes);
3259
3260       if (b == 0)
3261         {
3262           /* This is the first block in the function.  There may be insns
3263              before head that we can't schedule.   We still need to examine
3264              them though for accurate register lifetime analysis.  */
3265
3266           /* We don't want to remove any REG_DEAD notes as the code below
3267              does.  */
3268
3269           for (insn = basic_block_head[b]; insn != head;
3270                insn = NEXT_INSN (insn))
3271             if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
3272               {
3273                 /* See if the register gets born here.  */
3274                 /* We must check for registers being born before we check for
3275                    registers dying.  It is possible for a register to be born
3276                    and die in the same insn, e.g. reading from a volatile
3277                    memory location into an otherwise unused register.  Such
3278                    a register must be marked as dead after this insn.  */
3279                 if (GET_CODE (PATTERN (insn)) == SET
3280                     || GET_CODE (PATTERN (insn)) == CLOBBER)
3281                   sched_note_set (b, PATTERN (insn), 0);
3282                 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
3283                   {
3284                     int j;
3285                     for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
3286                       if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
3287                           || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
3288                         sched_note_set (b, XVECEXP (PATTERN (insn), 0, j), 0);
3289
3290                     /* ??? This code is obsolete and should be deleted.  It
3291                        is harmless though, so we will leave it in for now.  */
3292                     for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
3293                       if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == USE)
3294                         sched_note_set (b, XVECEXP (PATTERN (insn), 0, j), 0);
3295                   }
3296
3297                 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
3298                   {
3299                     if ((REG_NOTE_KIND (link) == REG_DEAD
3300                          || REG_NOTE_KIND (link) == REG_UNUSED)
3301                         /* Verify that the REG_NOTE has a legal value.  */
3302                         && GET_CODE (XEXP (link, 0)) == REG)
3303                       {
3304                         register int regno = REGNO (XEXP (link, 0));
3305                         register int offset = regno / REGSET_ELT_BITS;
3306                         register REGSET_ELT_TYPE bit
3307                           = (REGSET_ELT_TYPE) 1 << (regno % REGSET_ELT_BITS);
3308
3309                         if (regno < FIRST_PSEUDO_REGISTER)
3310                           {
3311                             int j = HARD_REGNO_NREGS (regno,
3312                                                       GET_MODE (XEXP (link, 0)));
3313                             while (--j >= 0)
3314                               {
3315                                 offset = (regno + j) / REGSET_ELT_BITS;
3316                                 bit = ((REGSET_ELT_TYPE) 1
3317                                        << ((regno + j) % REGSET_ELT_BITS));
3318
3319                                 bb_live_regs[offset] &= ~bit;
3320                                 bb_dead_regs[offset] |= bit;
3321                               }
3322                           }
3323                         else
3324                           {
3325                             bb_live_regs[offset] &= ~bit;
3326                             bb_dead_regs[offset] |= bit;
3327                           }
3328                       }
3329                   }
3330               }
3331         }
3332     }
3333
3334   /* If debugging information is being produced, keep track of the line
3335      number notes for each insn.  */
3336   if (write_symbols != NO_DEBUG)
3337     {
3338       /* We must use the true line number for the first insn in the block
3339          that was computed and saved at the start of this pass.  We can't
3340          use the current line number, because scheduling of the previous
3341          block may have changed the current line number.  */
3342       rtx line = line_note_head[b];
3343
3344       for (insn = basic_block_head[b];
3345            insn != next_tail;
3346            insn = NEXT_INSN (insn))
3347         if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
3348           line = insn;
3349         else
3350           LINE_NOTE (insn) = line;
3351     }
3352
3353   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
3354     {
3355       rtx prev, next, link;
3356
3357       /* Farm out notes.  This is needed to keep the debugger from
3358          getting completely deranged.  */
3359       if (GET_CODE (insn) == NOTE)
3360         {
3361           prev = insn;
3362           insn = unlink_notes (insn, next_tail);
3363           if (prev == tail)
3364             abort ();
3365           if (prev == head)
3366             abort ();
3367           if (insn == next_tail)
3368             abort ();
3369         }
3370
3371       if (reload_completed == 0
3372           && GET_RTX_CLASS (GET_CODE (insn)) == 'i')
3373         {
3374           /* See if the register gets born here.  */
3375           /* We must check for registers being born before we check for
3376              registers dying.  It is possible for a register to be born and
3377              die in the same insn, e.g. reading from a volatile memory
3378              location into an otherwise unused register.  Such a register
3379              must be marked as dead after this insn.  */
3380           if (GET_CODE (PATTERN (insn)) == SET
3381               || GET_CODE (PATTERN (insn)) == CLOBBER)
3382             sched_note_set (b, PATTERN (insn), 0);
3383           else if (GET_CODE (PATTERN (insn)) == PARALLEL)
3384             {
3385               int j;
3386               for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
3387                 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
3388                     || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
3389                   sched_note_set (b, XVECEXP (PATTERN (insn), 0, j), 0);
3390
3391               /* ??? This code is obsolete and should be deleted.  It
3392                  is harmless though, so we will leave it in for now.  */
3393               for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
3394                 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == USE)
3395                   sched_note_set (b, XVECEXP (PATTERN (insn), 0, j), 0);
3396             }
3397
3398           /* Need to know what registers this insn kills.  */
3399           for (prev = 0, link = REG_NOTES (insn); link; link = next)
3400             {
3401               int regno;
3402
3403               next = XEXP (link, 1);
3404               if ((REG_NOTE_KIND (link) == REG_DEAD
3405                    || REG_NOTE_KIND (link) == REG_UNUSED)
3406                   /* Verify that the REG_NOTE has a legal value.  */
3407                   && GET_CODE (XEXP (link, 0)) == REG)
3408                 {
3409                   register int regno = REGNO (XEXP (link, 0));
3410                   register int offset = regno / REGSET_ELT_BITS;
3411                   register REGSET_ELT_TYPE bit
3412                     = (REGSET_ELT_TYPE) 1 << (regno % REGSET_ELT_BITS);
3413
3414                   /* Only unlink REG_DEAD notes; leave REG_UNUSED notes
3415                      alone.  */
3416                   if (REG_NOTE_KIND (link) == REG_DEAD)
3417                     {
3418                       if (prev)
3419                         XEXP (prev, 1) = next;
3420                       else
3421                         REG_NOTES (insn) = next;
3422                       XEXP (link, 1) = dead_notes;
3423                       dead_notes = link;
3424                     }
3425                   else
3426                     prev = link;
3427
3428                   if (regno < FIRST_PSEUDO_REGISTER)
3429                     {
3430                       int j = HARD_REGNO_NREGS (regno,
3431                                                 GET_MODE (XEXP (link, 0)));
3432                       while (--j >= 0)
3433                         {
3434                           offset = (regno + j) / REGSET_ELT_BITS;
3435                           bit = ((REGSET_ELT_TYPE) 1
3436                                  << ((regno + j) % REGSET_ELT_BITS));
3437
3438                           bb_live_regs[offset] &= ~bit;
3439                           bb_dead_regs[offset] |= bit;
3440                         }
3441                     }
3442                   else
3443                     {
3444                       bb_live_regs[offset] &= ~bit;
3445                       bb_dead_regs[offset] |= bit;
3446                     }
3447                 }
3448               else
3449                 prev = link;
3450             }
3451         }
3452     }
3453
3454   if (reload_completed == 0)
3455     {
3456       /* Keep track of register lives.  */
3457       old_live_regs = (regset) alloca (regset_bytes);
3458       regs_sometimes_live
3459         = (struct sometimes *) alloca (max_regno * sizeof (struct sometimes));
3460       sometimes_max = 0;
3461
3462       /* Start with registers live at end.  */
3463       for (j = 0; j < regset_size; j++)
3464         {
3465           REGSET_ELT_TYPE live = bb_live_regs[j];
3466           old_live_regs[j] = live;
3467           if (live)
3468             {
3469               register int bit;
3470               for (bit = 0; bit < REGSET_ELT_BITS; bit++)
3471                 if (live & ((REGSET_ELT_TYPE) 1 << bit))
3472                   sometimes_max = new_sometimes_live (regs_sometimes_live, j,
3473                                                       bit, sometimes_max);
3474             }
3475         }
3476     }
3477
3478   SCHED_SORT (ready, n_ready, 1);
3479
3480   if (file)
3481     {
3482       fprintf (file, ";; ready list initially:\n;; ");
3483       for (i = 0; i < n_ready; i++)
3484         fprintf (file, "%d ", INSN_UID (ready[i]));
3485       fprintf (file, "\n\n");
3486
3487       for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
3488         if (INSN_PRIORITY (insn) > 0)
3489           fprintf (file, ";; insn[%4d]: priority = %4d, ref_count = %4d\n",
3490                    INSN_UID (insn), INSN_PRIORITY (insn),
3491                    INSN_REF_COUNT (insn));
3492     }
3493
3494   /* Now HEAD and TAIL are going to become disconnected
3495      entirely from the insn chain.  */
3496   tail = 0;
3497
3498   /* Q_SIZE will always be zero here.  */
3499   q_ptr = 0; clock = 0;
3500   bzero (insn_queue, sizeof (insn_queue));
3501
3502   /* Now, perform list scheduling.  */
3503
3504   /* Where we start inserting insns is after TAIL.  */
3505   last = next_tail;
3506
3507   new_needs = (NEXT_INSN (prev_head) == basic_block_head[b]
3508                ? NEED_HEAD : NEED_NOTHING);
3509   if (PREV_INSN (next_tail) == basic_block_end[b])
3510     new_needs |= NEED_TAIL;
3511
3512   new_ready = n_ready;
3513   while (sched_n_insns < n_insns)
3514     {
3515       q_ptr = NEXT_Q (q_ptr); clock++;
3516
3517       /* Add all pending insns that can be scheduled without stalls to the
3518          ready list.  */
3519       for (insn = insn_queue[q_ptr]; insn; insn = NEXT_INSN (insn))
3520         {
3521           if (file)
3522             fprintf (file, ";; launching %d before %d with no stalls at T-%d\n",
3523                      INSN_UID (insn), INSN_UID (last), clock);
3524           ready[new_ready++] = insn;
3525           q_size -= 1;
3526         }
3527       insn_queue[q_ptr] = 0;
3528
3529       /* If there are no ready insns, stall until one is ready and add all
3530          of the pending insns at that point to the ready list.  */
3531       if (new_ready == 0)
3532         {
3533           register int stalls;
3534
3535           for (stalls = 1; stalls < INSN_QUEUE_SIZE; stalls++)
3536             if (insn = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)])
3537               {
3538                 for (; insn; insn = NEXT_INSN (insn))
3539                   {
3540                     if (file)
3541                       fprintf (file, ";; launching %d before %d with %d stalls at T-%d\n",
3542                                INSN_UID (insn), INSN_UID (last), stalls, clock);
3543                     ready[new_ready++] = insn;
3544                     q_size -= 1;
3545                   }
3546                 insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = 0;
3547                 break;
3548               }
3549
3550           q_ptr = NEXT_Q_AFTER (q_ptr, stalls); clock += stalls;
3551         }
3552
3553       /* There should be some instructions waiting to fire.  */
3554       if (new_ready == 0)
3555         abort ();
3556
3557       if (file)
3558         {
3559           fprintf (file, ";; ready list at T-%d:", clock);
3560           for (i = 0; i < new_ready; i++)
3561             fprintf (file, " %d (%x)",
3562                      INSN_UID (ready[i]), INSN_PRIORITY (ready[i]));
3563         }
3564
3565       /* Sort the ready list and choose the best insn to schedule.  Select
3566          which insn should issue in this cycle and queue those that are
3567          blocked by function unit hazards.
3568
3569          N_READY holds the number of items that were scheduled the last time,
3570          minus the one instruction scheduled on the last loop iteration; it
3571          is not modified for any other reason in this loop.  */
3572
3573       SCHED_SORT (ready, new_ready, n_ready);
3574       if (MAX_BLOCKAGE > 1)
3575         {
3576           new_ready = schedule_select (ready, new_ready, clock, file);
3577           if (new_ready == 0)
3578             {
3579               if (file)
3580                 fprintf (file, "\n");
3581               /* We must set n_ready here, to ensure that sorting always
3582                  occurs when we come back to the SCHED_SORT line above.  */
3583               n_ready = 0;
3584               continue;
3585             }
3586         }
3587       n_ready = new_ready;
3588       last_scheduled_insn = insn = ready[0];
3589
3590       /* The first insn scheduled becomes the new tail.  */
3591       if (tail == 0)
3592         tail = insn;
3593
3594       if (file)
3595         {
3596           fprintf (file, ", now");
3597           for (i = 0; i < n_ready; i++)
3598             fprintf (file, " %d", INSN_UID (ready[i]));
3599           fprintf (file, "\n");
3600         }
3601
3602       if (DONE_PRIORITY_P (insn))
3603         abort ();
3604
3605       if (reload_completed == 0)
3606         {
3607           /* Process this insn, and each insn linked to this one which must
3608              be immediately output after this insn.  */
3609           do
3610             {
3611               /* First we kill registers set by this insn, and then we
3612                  make registers used by this insn live.  This is the opposite
3613                  order used above because we are traversing the instructions
3614                  backwards.  */
3615
3616               /* Strictly speaking, we should scan REG_UNUSED notes and make
3617                  every register mentioned there live, however, we will just
3618                  kill them again immediately below, so there doesn't seem to
3619                  be any reason why we bother to do this.  */
3620
3621               /* See if this is the last notice we must take of a register.  */
3622               if (GET_CODE (PATTERN (insn)) == SET
3623                   || GET_CODE (PATTERN (insn)) == CLOBBER)
3624                 sched_note_set (b, PATTERN (insn), 1);
3625               else if (GET_CODE (PATTERN (insn)) == PARALLEL)
3626                 {
3627                   int j;
3628                   for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
3629                     if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
3630                         || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
3631                       sched_note_set (b, XVECEXP (PATTERN (insn), 0, j), 1);
3632                 }
3633
3634               /* This code keeps life analysis information up to date.  */
3635               if (GET_CODE (insn) == CALL_INSN)
3636                 {
3637                   register struct sometimes *p;
3638
3639                   /* A call kills all call used and global registers, except
3640                      for those mentioned in the call pattern which will be
3641                      made live again later.  */
3642                   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3643                     if (call_used_regs[i] || global_regs[i])
3644                       {
3645                         register int offset = i / REGSET_ELT_BITS;
3646                         register REGSET_ELT_TYPE bit
3647                           = (REGSET_ELT_TYPE) 1 << (i % REGSET_ELT_BITS);
3648
3649                         bb_live_regs[offset] &= ~bit;
3650                         bb_dead_regs[offset] |= bit;
3651                       }
3652
3653                   /* Regs live at the time of a call instruction must not
3654                      go in a register clobbered by calls.  Record this for
3655                      all regs now live.  Note that insns which are born or
3656                      die in a call do not cross a call, so this must be done
3657                      after the killings (above) and before the births
3658                      (below).  */
3659                   p = regs_sometimes_live;
3660                   for (i = 0; i < sometimes_max; i++, p++)
3661                     if (bb_live_regs[p->offset]
3662                         & ((REGSET_ELT_TYPE) 1 << p->bit))
3663                       p->calls_crossed += 1;
3664                 }
3665
3666               /* Make every register used live, and add REG_DEAD notes for
3667                  registers which were not live before we started.  */
3668               attach_deaths_insn (insn);
3669
3670               /* Find registers now made live by that instruction.  */
3671               for (i = 0; i < regset_size; i++)
3672                 {
3673                   REGSET_ELT_TYPE diff = bb_live_regs[i] & ~old_live_regs[i];
3674                   if (diff)
3675                     {
3676                       register int bit;
3677                       old_live_regs[i] |= diff;
3678                       for (bit = 0; bit < REGSET_ELT_BITS; bit++)
3679                         if (diff & ((REGSET_ELT_TYPE) 1 << bit))
3680                           sometimes_max
3681                             = new_sometimes_live (regs_sometimes_live, i, bit,
3682                                                   sometimes_max);
3683                     }
3684                 }
3685
3686               /* Count lengths of all regs we are worrying about now,
3687                  and handle registers no longer live.  */
3688
3689               for (i = 0; i < sometimes_max; i++)
3690                 {
3691                   register struct sometimes *p = &regs_sometimes_live[i];
3692                   int regno = p->offset*REGSET_ELT_BITS + p->bit;
3693
3694                   p->live_length += 1;
3695
3696                   if ((bb_live_regs[p->offset]
3697                        & ((REGSET_ELT_TYPE) 1 << p->bit)) == 0)
3698                     {
3699                       /* This is the end of one of this register's lifetime
3700                          segments.  Save the lifetime info collected so far,
3701                          and clear its bit in the old_live_regs entry.  */
3702                       sched_reg_live_length[regno] += p->live_length;
3703                       sched_reg_n_calls_crossed[regno] += p->calls_crossed;
3704                       old_live_regs[p->offset]
3705                         &= ~((REGSET_ELT_TYPE) 1 << p->bit);
3706
3707                       /* Delete the reg_sometimes_live entry for this reg by
3708                          copying the last entry over top of it.  */
3709                       *p = regs_sometimes_live[--sometimes_max];
3710                       /* ...and decrement i so that this newly copied entry
3711                          will be processed.  */
3712                       i--;
3713                     }
3714                 }
3715
3716               link = insn;
3717               insn = PREV_INSN (insn);
3718             }
3719           while (SCHED_GROUP_P (link));
3720
3721           /* Set INSN back to the insn we are scheduling now.  */
3722           insn = ready[0];
3723         }
3724
3725       /* Schedule INSN.  Remove it from the ready list.  */
3726       ready += 1;
3727       n_ready -= 1;
3728
3729       sched_n_insns += 1;
3730       NEXT_INSN (insn) = last;
3731       PREV_INSN (last) = insn;
3732       last = insn;
3733
3734       /* Check to see if we need to re-emit a NOTE_INSN_SETJMP here.  */
3735       if (GET_CODE (insn) == CALL_INSN)
3736         {
3737           rtx note = find_reg_note (insn, REG_DEAD, constm1_rtx);
3738
3739           if (note)
3740             {
3741               emit_note_after (NOTE_INSN_SETJMP, insn);
3742               remove_note (insn, note);
3743             }
3744         }
3745
3746       /* Everything that precedes INSN now either becomes "ready", if
3747          it can execute immediately before INSN, or "pending", if
3748          there must be a delay.  Give INSN high enough priority that
3749          at least one (maybe more) reg-killing insns can be launched
3750          ahead of all others.  Mark INSN as scheduled by changing its
3751          priority to -1.  */
3752       INSN_PRIORITY (insn) = LAUNCH_PRIORITY;
3753       new_ready = schedule_insn (insn, ready, n_ready, clock);
3754       INSN_PRIORITY (insn) = DONE_PRIORITY;
3755
3756       /* Schedule all prior insns that must not be moved.  */
3757       if (SCHED_GROUP_P (insn))
3758         {
3759           /* Disable these insns from being launched.  */
3760           link = insn;
3761           while (SCHED_GROUP_P (link))
3762             {
3763               /* Disable these insns from being launched by anybody.  */
3764               link = PREV_INSN (link);
3765               INSN_REF_COUNT (link) = 0;
3766             }
3767
3768           /* None of these insns can move forward into delay slots.  */
3769           while (SCHED_GROUP_P (insn))
3770             {
3771               insn = PREV_INSN (insn);
3772               new_ready = schedule_insn (insn, ready, new_ready, clock);
3773               INSN_PRIORITY (insn) = DONE_PRIORITY;
3774
3775               sched_n_insns += 1;
3776               NEXT_INSN (insn) = last;
3777               PREV_INSN (last) = insn;
3778               last = insn;
3779             }
3780         }
3781     }
3782   if (q_size != 0)
3783     abort ();
3784
3785   if (reload_completed == 0)
3786     finish_sometimes_live (regs_sometimes_live, sometimes_max);
3787
3788   /* HEAD is now the first insn in the chain of insns that
3789      been scheduled by the loop above.
3790      TAIL is the last of those insns.  */
3791   head = insn;
3792
3793   /* NOTE_LIST is the end of a chain of notes previously found
3794      among the insns.  Insert them at the beginning of the insns.  */
3795   if (note_list != 0)
3796     {
3797       rtx note_head = note_list;
3798       while (PREV_INSN (note_head))
3799         note_head = PREV_INSN (note_head);
3800
3801       PREV_INSN (head) = note_list;
3802       NEXT_INSN (note_list) = head;
3803       head = note_head;
3804     }
3805
3806   /* There should be no REG_DEAD notes leftover at the end.
3807      In practice, this can occur as the result of bugs in flow, combine.c,
3808      and/or sched.c.  The values of the REG_DEAD notes remaining are
3809      meaningless, because dead_notes is just used as a free list.  */
3810 #if 1
3811   if (dead_notes != 0)
3812     abort ();
3813 #endif
3814
3815   if (new_needs & NEED_HEAD)
3816     basic_block_head[b] = head;
3817   PREV_INSN (head) = prev_head;
3818   NEXT_INSN (prev_head) = head;
3819
3820   if (new_needs & NEED_TAIL)
3821     basic_block_end[b] = tail;
3822   NEXT_INSN (tail) = next_tail;
3823   PREV_INSN (next_tail) = tail;
3824
3825   /* Restore the line-number notes of each insn.  */
3826   if (write_symbols != NO_DEBUG)
3827     {
3828       rtx line, note, prev, new;
3829       int notes = 0;
3830
3831       head = basic_block_head[b];
3832       next_tail = NEXT_INSN (basic_block_end[b]);
3833
3834       /* Determine the current line-number.  We want to know the current
3835          line number of the first insn of the block here, in case it is
3836          different from the true line number that was saved earlier.  If
3837          different, then we need a line number note before the first insn
3838          of this block.  If it happens to be the same, then we don't want to
3839          emit another line number note here.  */
3840       for (line = head; line; line = PREV_INSN (line))
3841         if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
3842           break;
3843
3844       /* Walk the insns keeping track of the current line-number and inserting
3845          the line-number notes as needed.  */
3846       for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
3847         if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
3848           line = insn;
3849       /* This used to emit line number notes before every non-deleted note.
3850          However, this confuses a debugger, because line notes not separated
3851          by real instructions all end up at the same address.  I can find no
3852          use for line number notes before other notes, so none are emitted.  */
3853         else if (GET_CODE (insn) != NOTE
3854                  && (note = LINE_NOTE (insn)) != 0
3855                  && note != line
3856                  && (line == 0
3857                      || NOTE_LINE_NUMBER (note) != NOTE_LINE_NUMBER (line)
3858                      || NOTE_SOURCE_FILE (note) != NOTE_SOURCE_FILE (line)))
3859           {
3860             line = note;
3861             prev = PREV_INSN (insn);
3862             if (LINE_NOTE (note))
3863               {
3864                 /* Re-use the original line-number note. */
3865                 LINE_NOTE (note) = 0;
3866                 PREV_INSN (note) = prev;
3867                 NEXT_INSN (prev) = note;
3868                 PREV_INSN (insn) = note;
3869                 NEXT_INSN (note) = insn;
3870               }
3871             else
3872               {
3873                 notes++;
3874                 new = emit_note_after (NOTE_LINE_NUMBER (note), prev);
3875                 NOTE_SOURCE_FILE (new) = NOTE_SOURCE_FILE (note);
3876               }
3877           }
3878       if (file && notes)
3879         fprintf (file, ";; added %d line-number notes\n", notes);
3880     }
3881
3882   if (file)
3883     {
3884       fprintf (file, ";; total time = %d\n;; new basic block head = %d\n;; new basic block end = %d\n\n",
3885                clock, INSN_UID (basic_block_head[b]), INSN_UID (basic_block_end[b]));
3886     }
3887
3888   /* Yow! We're done!  */
3889   free_pending_lists ();
3890
3891   return;
3892 }
3893 \f
3894 /* Subroutine of split_hard_reg_notes.  Searches X for any reference to
3895    REGNO, returning the rtx of the reference found if any.  Otherwise,
3896    returns 0.  */
3897
3898 static rtx
3899 regno_use_in (regno, x)
3900      int regno;
3901      rtx x;
3902 {
3903   register char *fmt;
3904   int i, j;
3905   rtx tem;
3906
3907   if (GET_CODE (x) == REG && REGNO (x) == regno)
3908     return x;
3909
3910   fmt = GET_RTX_FORMAT (GET_CODE (x));
3911   for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
3912     {
3913       if (fmt[i] == 'e')
3914         {
3915           if (tem = regno_use_in (regno, XEXP (x, i)))
3916             return tem;
3917         }
3918       else if (fmt[i] == 'E')
3919         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3920           if (tem = regno_use_in (regno , XVECEXP (x, i, j)))
3921             return tem;
3922     }
3923
3924   return 0;
3925 }
3926
3927 /* Subroutine of update_flow_info.  Determines whether any new REG_NOTEs are
3928    needed for the hard register mentioned in the note.  This can happen
3929    if the reference to the hard register in the original insn was split into
3930    several smaller hard register references in the split insns.  */
3931
3932 static void
3933 split_hard_reg_notes (note, first, last, orig_insn)
3934      rtx note, first, last, orig_insn;
3935 {
3936   rtx reg, temp, link;
3937   int n_regs, i, new_reg;
3938   rtx insn;
3939
3940   /* Assume that this is a REG_DEAD note.  */
3941   if (REG_NOTE_KIND (note) != REG_DEAD)
3942     abort ();
3943
3944   reg = XEXP (note, 0);
3945
3946   n_regs = HARD_REGNO_NREGS (REGNO (reg), GET_MODE (reg));
3947
3948   for (i = 0; i < n_regs; i++)
3949     {
3950       new_reg = REGNO (reg) + i;
3951
3952       /* Check for references to new_reg in the split insns.  */
3953       for (insn = last; ; insn = PREV_INSN (insn))
3954         {
3955           if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
3956               && (temp = regno_use_in (new_reg, PATTERN (insn))))
3957             {
3958               /* Create a new reg dead note here.  */
3959               link = rtx_alloc (EXPR_LIST);
3960               PUT_REG_NOTE_KIND (link, REG_DEAD);
3961               XEXP (link, 0) = temp;
3962               XEXP (link, 1) = REG_NOTES (insn);
3963               REG_NOTES (insn) = link;
3964
3965               /* If killed multiple registers here, then add in the excess.  */
3966               i += HARD_REGNO_NREGS (REGNO (temp), GET_MODE (temp)) - 1;
3967
3968               break;
3969             }
3970           /* It isn't mentioned anywhere, so no new reg note is needed for
3971              this register.  */
3972           if (insn == first)
3973             break;
3974         }
3975     }
3976 }
3977
3978 /* Subroutine of update_flow_info.  Determines whether a SET or CLOBBER in an
3979    insn created by splitting needs a REG_DEAD or REG_UNUSED note added.  */
3980
3981 static void
3982 new_insn_dead_notes (pat, insn, last, orig_insn)
3983      rtx pat, insn, last, orig_insn;
3984 {
3985   rtx dest, tem, set;
3986
3987   /* PAT is either a CLOBBER or a SET here.  */
3988   dest = XEXP (pat, 0);
3989
3990   while (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SUBREG
3991          || GET_CODE (dest) == STRICT_LOW_PART
3992          || GET_CODE (dest) == SIGN_EXTRACT)
3993     dest = XEXP (dest, 0);
3994
3995   if (GET_CODE (dest) == REG)
3996     {
3997       for (tem = last; tem != insn; tem = PREV_INSN (tem))
3998         {
3999           if (GET_RTX_CLASS (GET_CODE (tem)) == 'i'
4000               && reg_overlap_mentioned_p (dest, PATTERN (tem))
4001               && (set = single_set (tem)))
4002             {
4003               rtx tem_dest = SET_DEST (set);
4004
4005               while (GET_CODE (tem_dest) == ZERO_EXTRACT
4006                      || GET_CODE (tem_dest) == SUBREG
4007                      || GET_CODE (tem_dest) == STRICT_LOW_PART
4008                      || GET_CODE (tem_dest) == SIGN_EXTRACT)
4009                 tem_dest = XEXP (tem_dest, 0);
4010
4011               if (! rtx_equal_p (tem_dest, dest))
4012                 {
4013                   /* Use the same scheme as combine.c, don't put both REG_DEAD
4014                      and REG_UNUSED notes on the same insn.  */
4015                   if (! find_regno_note (tem, REG_UNUSED, REGNO (dest))
4016                       && ! find_regno_note (tem, REG_DEAD, REGNO (dest)))
4017                     {
4018                       rtx note = rtx_alloc (EXPR_LIST);
4019                       PUT_REG_NOTE_KIND (note, REG_DEAD);
4020                       XEXP (note, 0) = dest;
4021                       XEXP (note, 1) = REG_NOTES (tem);
4022                       REG_NOTES (tem) = note;
4023                     }
4024                   /* The reg only dies in one insn, the last one that uses
4025                      it.  */
4026                   break;
4027                 }
4028               else if (reg_overlap_mentioned_p (dest, SET_SRC (set)))
4029                 /* We found an instruction that both uses the register,
4030                    and sets it, so no new REG_NOTE is needed for this set.  */
4031                 break;
4032             }
4033         }
4034       /* If this is a set, it must die somewhere, unless it is the dest of
4035          the original insn, and hence is live after the original insn.  Abort
4036          if it isn't supposed to be live after the original insn.
4037
4038          If this is a clobber, then just add a REG_UNUSED note.  */
4039       if (tem == insn)
4040         {
4041           int live_after_orig_insn = 0;
4042           rtx pattern = PATTERN (orig_insn);
4043           int i;
4044
4045           if (GET_CODE (pat) == CLOBBER)
4046             {
4047               rtx note = rtx_alloc (EXPR_LIST);
4048               PUT_REG_NOTE_KIND (note, REG_UNUSED);
4049               XEXP (note, 0) = dest;
4050               XEXP (note, 1) = REG_NOTES (insn);
4051               REG_NOTES (insn) = note;
4052               return;
4053             }
4054
4055           /* The original insn could have multiple sets, so search the
4056              insn for all sets.  */
4057           if (GET_CODE (pattern) == SET)
4058             {
4059               if (reg_overlap_mentioned_p (dest, SET_DEST (pattern)))
4060                 live_after_orig_insn = 1;
4061             }
4062           else if (GET_CODE (pattern) == PARALLEL)
4063             {
4064               for (i = 0; i < XVECLEN (pattern, 0); i++)
4065                 if (GET_CODE (XVECEXP (pattern, 0, i)) == SET
4066                     && reg_overlap_mentioned_p (dest,
4067                                                 SET_DEST (XVECEXP (pattern,
4068                                                                    0, i))))
4069                   live_after_orig_insn = 1;
4070             }
4071
4072           if (! live_after_orig_insn)
4073             abort ();
4074         }
4075     }
4076 }
4077
4078 /* Subroutine of update_flow_info.  Update the value of reg_n_sets for all
4079    registers modified by X.  INC is -1 if the containing insn is being deleted,
4080    and is 1 if the containing insn is a newly generated insn.  */
4081
4082 static void
4083 update_n_sets (x, inc)
4084      rtx x;
4085      int inc;
4086 {
4087   rtx dest = SET_DEST (x);
4088
4089   while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
4090          || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
4091     dest = SUBREG_REG (dest);
4092
4093   if (GET_CODE (dest) == REG)
4094     {
4095       int regno = REGNO (dest);
4096
4097       if (regno < FIRST_PSEUDO_REGISTER)
4098         {
4099           register int i;
4100           int endregno = regno + HARD_REGNO_NREGS (regno, GET_MODE (dest));
4101
4102           for (i = regno; i < endregno; i++)
4103             reg_n_sets[i] += inc;
4104         }
4105       else
4106         reg_n_sets[regno] += inc;
4107     }
4108 }
4109
4110 /* Updates all flow-analysis related quantities (including REG_NOTES) for
4111    the insns from FIRST to LAST inclusive that were created by splitting
4112    ORIG_INSN.  NOTES are the original REG_NOTES.  */
4113
4114 static void
4115 update_flow_info (notes, first, last, orig_insn)
4116      rtx notes;
4117      rtx first, last;
4118      rtx orig_insn;
4119 {
4120   rtx insn, note;
4121   rtx next;
4122   rtx orig_dest, temp;
4123   rtx set;
4124
4125   /* Get and save the destination set by the original insn.  */
4126
4127   orig_dest = single_set (orig_insn);
4128   if (orig_dest)
4129     orig_dest = SET_DEST (orig_dest);
4130
4131   /* Move REG_NOTES from the original insn to where they now belong.  */
4132
4133   for (note = notes; note; note = next)
4134     {
4135       next = XEXP (note, 1);
4136       switch (REG_NOTE_KIND (note))
4137         {
4138         case REG_DEAD:
4139         case REG_UNUSED:
4140           /* Move these notes from the original insn to the last new insn where
4141              the register is now set.  */
4142
4143           for (insn = last; ; insn = PREV_INSN (insn))
4144             {
4145               if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
4146                   && reg_mentioned_p (XEXP (note, 0), PATTERN (insn)))
4147                 {
4148                   /* If this note refers to a multiple word hard register, it
4149                      may have been split into several smaller hard register
4150                      references, so handle it specially.  */
4151                   temp = XEXP (note, 0);
4152                   if (REG_NOTE_KIND (note) == REG_DEAD
4153                       && GET_CODE (temp) == REG
4154                       && REGNO (temp) < FIRST_PSEUDO_REGISTER
4155                       && HARD_REGNO_NREGS (REGNO (temp), GET_MODE (temp)) > 1)
4156                     split_hard_reg_notes (note, first, last, orig_insn);
4157                   else
4158                     {
4159                       XEXP (note, 1) = REG_NOTES (insn);
4160                       REG_NOTES (insn) = note;
4161                     }
4162
4163                   /* Sometimes need to convert REG_UNUSED notes to REG_DEAD
4164                      notes.  */
4165                   /* ??? This won't handle multiple word registers correctly,
4166                      but should be good enough for now.  */
4167                   if (REG_NOTE_KIND (note) == REG_UNUSED
4168                       && ! dead_or_set_p (insn, XEXP (note, 0)))
4169                     PUT_REG_NOTE_KIND (note, REG_DEAD);
4170
4171                   /* The reg only dies in one insn, the last one that uses
4172                      it.  */
4173                   break;
4174                 }
4175               /* It must die somewhere, fail it we couldn't find where it died.
4176
4177                  If this is a REG_UNUSED note, then it must be a temporary
4178                  register that was not needed by this instantiation of the
4179                  pattern, so we can safely ignore it.  */
4180               if (insn == first)
4181                 {
4182                   if (REG_NOTE_KIND (note) != REG_UNUSED)
4183                     abort ();
4184
4185                   break;
4186                 }
4187             }
4188           break;
4189
4190         case REG_WAS_0:
4191           /* This note applies to the dest of the original insn.  Find the
4192              first new insn that now has the same dest, and move the note
4193              there.  */
4194
4195           if (! orig_dest)
4196             abort ();
4197
4198           for (insn = first; ; insn = NEXT_INSN (insn))
4199             {
4200               if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
4201                   && (temp = single_set (insn))
4202                   && rtx_equal_p (SET_DEST (temp), orig_dest))
4203                 {
4204                   XEXP (note, 1) = REG_NOTES (insn);
4205                   REG_NOTES (insn) = note;
4206                   /* The reg is only zero before one insn, the first that
4207                      uses it.  */
4208                   break;
4209                 }
4210               /* It must be set somewhere, fail if we couldn't find where it
4211                  was set.  */
4212               if (insn == last)
4213                 abort ();
4214             }
4215           break;
4216
4217         case REG_EQUAL:
4218         case REG_EQUIV:
4219           /* A REG_EQUIV or REG_EQUAL note on an insn with more than one
4220              set is meaningless.  Just drop the note.  */
4221           if (! orig_dest)
4222             break;
4223
4224         case REG_NO_CONFLICT:
4225           /* These notes apply to the dest of the original insn.  Find the last
4226              new insn that now has the same dest, and move the note there.  */
4227
4228           if (! orig_dest)
4229             abort ();
4230
4231           for (insn = last; ; insn = PREV_INSN (insn))
4232             {
4233               if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
4234                   && (temp = single_set (insn))
4235                   && rtx_equal_p (SET_DEST (temp), orig_dest))
4236                 {
4237                   XEXP (note, 1) = REG_NOTES (insn);
4238                   REG_NOTES (insn) = note;
4239                   /* Only put this note on one of the new insns.  */
4240                   break;
4241                 }
4242
4243               /* The original dest must still be set someplace.  Abort if we
4244                  couldn't find it.  */
4245               if (insn == first)
4246                 abort ();
4247             }
4248           break;
4249
4250         case REG_LIBCALL:
4251           /* Move a REG_LIBCALL note to the first insn created, and update
4252              the corresponding REG_RETVAL note.  */
4253           XEXP (note, 1) = REG_NOTES (first);
4254           REG_NOTES (first) = note;
4255
4256           insn = XEXP (note, 0);
4257           note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
4258           if (note)
4259             XEXP (note, 0) = first;
4260           break;
4261
4262         case REG_RETVAL:
4263           /* Move a REG_RETVAL note to the last insn created, and update
4264              the corresponding REG_LIBCALL note.  */
4265           XEXP (note, 1) = REG_NOTES (last);
4266           REG_NOTES (last) = note;
4267
4268           insn = XEXP (note, 0);
4269           note = find_reg_note (insn, REG_LIBCALL, NULL_RTX);
4270           if (note)
4271             XEXP (note, 0) = last;
4272           break;
4273
4274         case REG_NONNEG:
4275           /* This should be moved to whichever instruction is a JUMP_INSN.  */
4276
4277           for (insn = last; ; insn = PREV_INSN (insn))
4278             {
4279               if (GET_CODE (insn) == JUMP_INSN)
4280                 {
4281                   XEXP (note, 1) = REG_NOTES (insn);
4282                   REG_NOTES (insn) = note;
4283                   /* Only put this note on one of the new insns.  */
4284                   break;
4285                 }
4286               /* Fail if we couldn't find a JUMP_INSN.  */
4287               if (insn == first)
4288                 abort ();
4289             }
4290           break;
4291
4292         case REG_INC:
4293           /* This should be moved to whichever instruction now has the
4294              increment operation.  */
4295           abort ();
4296
4297         case REG_LABEL:
4298           /* Should be moved to the new insn(s) which use the label.  */
4299           for (insn = first; insn != NEXT_INSN (last); insn = NEXT_INSN (insn))
4300             if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
4301                 && reg_mentioned_p (XEXP (note, 0), PATTERN (insn)))
4302               REG_NOTES (insn) = gen_rtx (EXPR_LIST, REG_LABEL,
4303                                           XEXP (note, 0), REG_NOTES (insn));
4304           break;
4305
4306         case REG_CC_SETTER:
4307         case REG_CC_USER:
4308           /* These two notes will never appear until after reorg, so we don't
4309              have to handle them here.  */
4310         default:
4311           abort ();
4312         }
4313     }
4314
4315   /* Each new insn created, except the last, has a new set.  If the destination
4316      is a register, then this reg is now live across several insns, whereas
4317      previously the dest reg was born and died within the same insn.  To
4318      reflect this, we now need a REG_DEAD note on the insn where this
4319      dest reg dies.
4320
4321      Similarly, the new insns may have clobbers that need REG_UNUSED notes.  */
4322
4323   for (insn = first; insn != last; insn = NEXT_INSN (insn))
4324     {
4325       rtx pat;
4326       int i;
4327
4328       pat = PATTERN (insn);
4329       if (GET_CODE (pat) == SET || GET_CODE (pat) == CLOBBER)
4330         new_insn_dead_notes (pat, insn, last, orig_insn);
4331       else if (GET_CODE (pat) == PARALLEL)
4332         {
4333           for (i = 0; i < XVECLEN (pat, 0); i++)
4334             if (GET_CODE (XVECEXP (pat, 0, i)) == SET
4335                 || GET_CODE (XVECEXP (pat, 0, i)) == CLOBBER)
4336               new_insn_dead_notes (XVECEXP (pat, 0, i), insn, last, orig_insn);
4337         }
4338     }
4339
4340   /* If any insn, except the last, uses the register set by the last insn,
4341      then we need a new REG_DEAD note on that insn.  In this case, there
4342      would not have been a REG_DEAD note for this register in the original
4343      insn because it was used and set within one insn.
4344
4345      There is no new REG_DEAD note needed if the last insn uses the register
4346      that it is setting.  */
4347
4348   set = single_set (last);
4349   if (set)
4350     {
4351       rtx dest = SET_DEST (set);
4352
4353       while (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SUBREG
4354              || GET_CODE (dest) == STRICT_LOW_PART
4355              || GET_CODE (dest) == SIGN_EXTRACT)
4356         dest = XEXP (dest, 0);
4357
4358       if (GET_CODE (dest) == REG
4359           && ! reg_overlap_mentioned_p (dest, SET_SRC (set)))
4360         {
4361           for (insn = PREV_INSN (last); ; insn = PREV_INSN (insn))
4362             {
4363               if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
4364                   && reg_mentioned_p (dest, PATTERN (insn))
4365                   && (set = single_set (insn)))
4366                 {
4367                   rtx insn_dest = SET_DEST (set);
4368
4369                   while (GET_CODE (insn_dest) == ZERO_EXTRACT
4370                          || GET_CODE (insn_dest) == SUBREG
4371                          || GET_CODE (insn_dest) == STRICT_LOW_PART
4372                          || GET_CODE (insn_dest) == SIGN_EXTRACT)
4373                     insn_dest = XEXP (insn_dest, 0);
4374
4375                   if (insn_dest != dest)
4376                     {
4377                       note = rtx_alloc (EXPR_LIST);
4378                       PUT_REG_NOTE_KIND (note, REG_DEAD);
4379                       XEXP (note, 0) = dest;
4380                       XEXP (note, 1) = REG_NOTES (insn);
4381                       REG_NOTES (insn) = note;
4382                       /* The reg only dies in one insn, the last one
4383                          that uses it.  */
4384                       break;
4385                     }
4386                 }
4387               if (insn == first)
4388                 break;
4389             }
4390         }
4391     }
4392
4393   /* If the original dest is modifying a multiple register target, and the
4394      original instruction was split such that the original dest is now set
4395      by two or more SUBREG sets, then the split insns no longer kill the
4396      destination of the original insn.
4397
4398      In this case, if there exists an instruction in the same basic block,
4399      before the split insn, which uses the original dest, and this use is
4400      killed by the original insn, then we must remove the REG_DEAD note on
4401      this insn, because it is now superfluous.
4402
4403      This does not apply when a hard register gets split, because the code
4404      knows how to handle overlapping hard registers properly.  */
4405   if (orig_dest && GET_CODE (orig_dest) == REG)
4406     {
4407       int found_orig_dest = 0;
4408       int found_split_dest = 0;
4409
4410       for (insn = first; ; insn = NEXT_INSN (insn))
4411         {
4412           set = single_set (insn);
4413           if (set)
4414             {
4415               if (GET_CODE (SET_DEST (set)) == REG
4416                   && REGNO (SET_DEST (set)) == REGNO (orig_dest))
4417                 {
4418                   found_orig_dest = 1;
4419                   break;
4420                 }
4421               else if (GET_CODE (SET_DEST (set)) == SUBREG
4422                        && SUBREG_REG (SET_DEST (set)) == orig_dest)
4423                 {
4424                   found_split_dest = 1;
4425                   break;
4426                 }
4427             }
4428
4429           if (insn == last)
4430             break;
4431         }
4432
4433       if (found_split_dest)
4434         {
4435           /* Search backwards from FIRST, looking for the first insn that uses
4436              the original dest.  Stop if we pass a CODE_LABEL or a JUMP_INSN.
4437              If we find an insn, and it has a REG_DEAD note, then delete the
4438              note.  */
4439
4440           for (insn = first; insn; insn = PREV_INSN (insn))
4441             {
4442               if (GET_CODE (insn) == CODE_LABEL
4443                   || GET_CODE (insn) == JUMP_INSN)
4444                 break;
4445               else if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
4446                        && reg_mentioned_p (orig_dest, insn))
4447                 {
4448                   note = find_regno_note (insn, REG_DEAD, REGNO (orig_dest));
4449                   if (note)
4450                     remove_note (insn, note);
4451                 }
4452             }
4453         }
4454       else if (! found_orig_dest)
4455         {
4456           /* This should never happen.  */
4457           abort ();
4458         }
4459     }
4460
4461   /* Update reg_n_sets.  This is necessary to prevent local alloc from
4462      converting REG_EQUAL notes to REG_EQUIV when splitting has modified
4463      a reg from set once to set multiple times.  */
4464
4465   {
4466     rtx x = PATTERN (orig_insn);
4467     RTX_CODE code = GET_CODE (x);
4468
4469     if (code == SET || code == CLOBBER)
4470       update_n_sets (x, -1);
4471     else if (code == PARALLEL)
4472       {
4473         int i;
4474         for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
4475           {
4476             code = GET_CODE (XVECEXP (x, 0, i));
4477             if (code == SET || code == CLOBBER)
4478               update_n_sets (XVECEXP (x, 0, i), -1);
4479           }
4480       }
4481
4482     for (insn = first; ; insn = NEXT_INSN (insn))
4483       {
4484         x = PATTERN (insn);
4485         code = GET_CODE (x);
4486
4487         if (code == SET || code == CLOBBER)
4488           update_n_sets (x, 1);
4489         else if (code == PARALLEL)
4490           {
4491             int i;
4492             for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
4493               {
4494                 code = GET_CODE (XVECEXP (x, 0, i));
4495                 if (code == SET || code == CLOBBER)
4496                   update_n_sets (XVECEXP (x, 0, i), 1);
4497               }
4498           }
4499
4500         if (insn == last)
4501           break;
4502       }
4503   }
4504 }
4505
4506 /* The one entry point in this file.  DUMP_FILE is the dump file for
4507    this pass.  */
4508
4509 void
4510 schedule_insns (dump_file)
4511      FILE *dump_file;
4512 {
4513   int max_uid = MAX_INSNS_PER_SPLIT * (get_max_uid () + 1);
4514   int i, b;
4515   rtx insn;
4516
4517   /* Taking care of this degenerate case makes the rest of
4518      this code simpler.  */
4519   if (n_basic_blocks == 0)
4520     return;
4521
4522   /* Create an insn here so that we can hang dependencies off of it later.  */
4523   sched_before_next_call
4524     = gen_rtx (INSN, VOIDmode, 0, NULL_RTX, NULL_RTX,
4525                NULL_RTX, 0, NULL_RTX, 0);
4526
4527   /* Initialize the unused_*_lists.  We can't use the ones left over from
4528      the previous function, because gcc has freed that memory.  We can use
4529      the ones left over from the first sched pass in the second pass however,
4530      so only clear them on the first sched pass.  The first pass is before
4531      reload if flag_schedule_insns is set, otherwise it is afterwards.  */
4532
4533   if (reload_completed == 0 || ! flag_schedule_insns)
4534     {
4535       unused_insn_list = 0;
4536       unused_expr_list = 0;
4537     }
4538
4539   /* We create no insns here, only reorder them, so we
4540      remember how far we can cut back the stack on exit.  */
4541
4542   /* Allocate data for this pass.  See comments, above,
4543      for what these vectors do.  */
4544   insn_luid = (int *) alloca (max_uid * sizeof (int));
4545   insn_priority = (int *) alloca (max_uid * sizeof (int));
4546   insn_tick = (int *) alloca (max_uid * sizeof (int));
4547   insn_costs = (short *) alloca (max_uid * sizeof (short));
4548   insn_units = (short *) alloca (max_uid * sizeof (short));
4549   insn_blockage = (unsigned int *) alloca (max_uid * sizeof (unsigned int));
4550   insn_ref_count = (int *) alloca (max_uid * sizeof (int));
4551
4552   if (reload_completed == 0)
4553     {
4554       sched_reg_n_deaths = (short *) alloca (max_regno * sizeof (short));
4555       sched_reg_n_calls_crossed = (int *) alloca (max_regno * sizeof (int));
4556       sched_reg_live_length = (int *) alloca (max_regno * sizeof (int));
4557       bb_dead_regs = (regset) alloca (regset_bytes);
4558       bb_live_regs = (regset) alloca (regset_bytes);
4559       bzero (sched_reg_n_calls_crossed, max_regno * sizeof (int));
4560       bzero (sched_reg_live_length, max_regno * sizeof (int));
4561       bcopy (reg_n_deaths, sched_reg_n_deaths, max_regno * sizeof (short));
4562       init_alias_analysis ();
4563     }
4564   else
4565     {
4566       sched_reg_n_deaths = 0;
4567       sched_reg_n_calls_crossed = 0;
4568       sched_reg_live_length = 0;
4569       bb_dead_regs = 0;
4570       bb_live_regs = 0;
4571       if (! flag_schedule_insns)
4572         init_alias_analysis ();
4573     }
4574
4575   if (write_symbols != NO_DEBUG)
4576     {
4577       rtx line;
4578
4579       line_note = (rtx *) alloca (max_uid * sizeof (rtx));
4580       bzero (line_note, max_uid * sizeof (rtx));
4581       line_note_head = (rtx *) alloca (n_basic_blocks * sizeof (rtx));
4582       bzero (line_note_head, n_basic_blocks * sizeof (rtx));
4583
4584       /* Determine the line-number at the start of each basic block.
4585          This must be computed and saved now, because after a basic block's
4586          predecessor has been scheduled, it is impossible to accurately
4587          determine the correct line number for the first insn of the block.  */
4588
4589       for (b = 0; b < n_basic_blocks; b++)
4590         for (line = basic_block_head[b]; line; line = PREV_INSN (line))
4591           if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
4592             {
4593               line_note_head[b] = line;
4594               break;
4595             }
4596     }
4597
4598   bzero (insn_luid, max_uid * sizeof (int));
4599   bzero (insn_priority, max_uid * sizeof (int));
4600   bzero (insn_tick, max_uid * sizeof (int));
4601   bzero (insn_costs, max_uid * sizeof (short));
4602   bzero (insn_units, max_uid * sizeof (short));
4603   bzero (insn_blockage, max_uid * sizeof (unsigned int));
4604   bzero (insn_ref_count, max_uid * sizeof (int));
4605
4606   /* Schedule each basic block, block by block.  */
4607
4608   /* ??? Add a NOTE after the last insn of the last basic block.  It is not
4609      known why this is done.  */
4610
4611   insn = basic_block_end[n_basic_blocks-1];
4612   if (NEXT_INSN (insn) == 0
4613       || (GET_CODE (insn) != NOTE
4614           && GET_CODE (insn) != CODE_LABEL
4615           /* Don't emit a NOTE if it would end up between an unconditional
4616              jump and a BARRIER.  */
4617           && ! (GET_CODE (insn) == JUMP_INSN
4618                 && GET_CODE (NEXT_INSN (insn)) == BARRIER)))
4619     emit_note_after (NOTE_INSN_DELETED, basic_block_end[n_basic_blocks-1]);
4620
4621   for (b = 0; b < n_basic_blocks; b++)
4622     {
4623       rtx insn, next;
4624       rtx insns;
4625
4626       note_list = 0;
4627
4628       for (insn = basic_block_head[b]; ; insn = next)
4629         {
4630           rtx prev;
4631           rtx set;
4632
4633           /* Can't use `next_real_insn' because that
4634              might go across CODE_LABELS and short-out basic blocks.  */
4635           next = NEXT_INSN (insn);
4636           if (GET_CODE (insn) != INSN)
4637             {
4638               if (insn == basic_block_end[b])
4639                 break;
4640
4641               continue;
4642             }
4643
4644           /* Don't split no-op move insns.  These should silently disappear
4645              later in final.  Splitting such insns would break the code
4646              that handles REG_NO_CONFLICT blocks.  */
4647           set = single_set (insn);
4648           if (set && rtx_equal_p (SET_SRC (set), SET_DEST (set)))
4649             {
4650               if (insn == basic_block_end[b])
4651                 break;
4652
4653               /* Nops get in the way while scheduling, so delete them now if
4654                  register allocation has already been done.  It is too risky
4655                  to try to do this before register allocation, and there are
4656                  unlikely to be very many nops then anyways.  */
4657               if (reload_completed)
4658                 {
4659                   PUT_CODE (insn, NOTE);
4660                   NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
4661                   NOTE_SOURCE_FILE (insn) = 0;
4662                 }
4663
4664               continue;
4665             }
4666
4667           /* Split insns here to get max fine-grain parallelism.  */
4668           prev = PREV_INSN (insn);
4669           if (reload_completed == 0)
4670             {
4671               rtx last, first = PREV_INSN (insn);
4672               rtx notes = REG_NOTES (insn);
4673
4674               last = try_split (PATTERN (insn), insn, 1);
4675               if (last != insn)
4676                 {
4677                   /* try_split returns the NOTE that INSN became.  */
4678                   first = NEXT_INSN (first);
4679                   update_flow_info (notes, first, last, insn);
4680
4681                   PUT_CODE (insn, NOTE);
4682                   NOTE_SOURCE_FILE (insn) = 0;
4683                   NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
4684                   if (insn == basic_block_head[b])
4685                     basic_block_head[b] = first;
4686                   if (insn == basic_block_end[b])
4687                     {
4688                       basic_block_end[b] = last;
4689                       break;
4690                     }
4691                 }
4692             }
4693
4694           if (insn == basic_block_end[b])
4695             break;
4696         }
4697
4698       schedule_block (b, dump_file);
4699
4700 #ifdef USE_C_ALLOCA
4701       alloca (0);
4702 #endif
4703     }
4704
4705   /* Reposition the prologue and epilogue notes in case we moved the
4706      prologue/epilogue insns.  */
4707   if (reload_completed)
4708     reposition_prologue_and_epilogue_notes (get_insns ());
4709
4710   if (write_symbols != NO_DEBUG)
4711     {
4712       rtx line = 0;
4713       rtx insn = get_insns ();
4714       int active_insn = 0;
4715       int notes = 0;
4716
4717       /* Walk the insns deleting redundant line-number notes.  Many of these
4718          are already present.  The remainder tend to occur at basic
4719          block boundaries.  */
4720       for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
4721         if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
4722           {
4723             /* If there are no active insns following, INSN is redundant.  */
4724             if (active_insn == 0)
4725               {
4726                 notes++;
4727                 NOTE_SOURCE_FILE (insn) = 0;
4728                 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
4729               }
4730             /* If the line number is unchanged, LINE is redundant.  */
4731             else if (line
4732                      && NOTE_LINE_NUMBER (line) == NOTE_LINE_NUMBER (insn)
4733                      && NOTE_SOURCE_FILE (line) == NOTE_SOURCE_FILE (insn))
4734               {
4735                 notes++;
4736                 NOTE_SOURCE_FILE (line) = 0;
4737                 NOTE_LINE_NUMBER (line) = NOTE_INSN_DELETED;
4738                 line = insn;
4739               }
4740             else
4741               line = insn;
4742             active_insn = 0;
4743           }
4744         else if (! ((GET_CODE (insn) == NOTE
4745                      && NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED)
4746                     || (GET_CODE (insn) == INSN
4747                         && (GET_CODE (PATTERN (insn)) == USE
4748                             || GET_CODE (PATTERN (insn)) == CLOBBER))))
4749           active_insn++;
4750
4751       if (dump_file && notes)
4752         fprintf (dump_file, ";; deleted %d line-number notes\n", notes);
4753     }
4754
4755   if (reload_completed == 0)
4756     {
4757       int regno;
4758       for (regno = 0; regno < max_regno; regno++)
4759         if (sched_reg_live_length[regno])
4760           {
4761             if (dump_file)
4762               {
4763                 if (reg_live_length[regno] > sched_reg_live_length[regno])
4764                   fprintf (dump_file,
4765                            ";; register %d life shortened from %d to %d\n",
4766                            regno, reg_live_length[regno],
4767                            sched_reg_live_length[regno]);
4768                 /* Negative values are special; don't overwrite the current
4769                    reg_live_length value if it is negative.  */
4770                 else if (reg_live_length[regno] < sched_reg_live_length[regno]
4771                          && reg_live_length[regno] >= 0)
4772                   fprintf (dump_file,
4773                            ";; register %d life extended from %d to %d\n",
4774                            regno, reg_live_length[regno],
4775                            sched_reg_live_length[regno]);
4776
4777                 if (! reg_n_calls_crossed[regno]
4778                     && sched_reg_n_calls_crossed[regno])
4779                   fprintf (dump_file,
4780                            ";; register %d now crosses calls\n", regno);
4781                 else if (reg_n_calls_crossed[regno]
4782                          && ! sched_reg_n_calls_crossed[regno]
4783                          && reg_basic_block[regno] != REG_BLOCK_GLOBAL)
4784                   fprintf (dump_file,
4785                            ";; register %d no longer crosses calls\n", regno);
4786
4787               }
4788             /* Negative values are special; don't overwrite the current
4789                reg_live_length value if it is negative.  */
4790             if (reg_live_length[regno] >= 0)
4791               reg_live_length[regno] = sched_reg_live_length[regno];
4792
4793             /* We can't change the value of reg_n_calls_crossed to zero for
4794                pseudos which are live in more than one block.
4795
4796                This is because combine might have made an optimization which
4797                invalidated basic_block_live_at_start and reg_n_calls_crossed,
4798                but it does not update them.  If we update reg_n_calls_crossed
4799                here, the two variables are now inconsistent, and this might
4800                confuse the caller-save code into saving a register that doesn't
4801                need to be saved.  This is only a problem when we zero calls
4802                crossed for a pseudo live in multiple basic blocks.
4803
4804                Alternatively, we could try to correctly update basic block live
4805                at start here in sched, but that seems complicated.  */
4806             if (sched_reg_n_calls_crossed[regno]
4807                 || reg_basic_block[regno] != REG_BLOCK_GLOBAL)
4808               reg_n_calls_crossed[regno] = sched_reg_n_calls_crossed[regno];
4809           }
4810     }
4811 }
4812 #endif /* INSN_SCHEDULING */