gcc/haifa-sched.c

   1 /* Instruction scheduling pass.
   2    Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
   3    1999, 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
   4    Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
   5    and currently maintained by, Jim Wilson (wilson@cygnus.com)
   6
   7 This file is part of GCC.
   8
   9 GCC is free software; you can redistribute it and/or modify it under
  10 the terms of the GNU General Public License as published by the Free
  11 Software Foundation; either version 2, or (at your option) any later
  12 version.
  13
  14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  16 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  17 for more details.
  18
  19 You should have received a copy of the GNU General Public License
  20 along with GCC; see the file COPYING.  If not, write to the Free
  21 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  22 02110-1301, USA.  */
  23
  24 /* Instruction scheduling pass.  This file, along with sched-deps.c,
  25    contains the generic parts.  The actual entry point is found for
  26    the normal instruction scheduling pass is found in sched-rgn.c.
  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 values
  39    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    The following list shows the order in which we want to break ties
  58    among insns in the ready list:
  59
  60    1.  choose insn with the longest path to end of bb, ties
  61    broken by
  62    2.  choose insn with least contribution to register pressure,
  63    ties broken by
  64    3.  prefer in-block upon interblock motion, ties broken by
  65    4.  prefer useful upon speculative motion, ties broken by
  66    5.  choose insn with largest control flow probability, ties
  67    broken by
  68    6.  choose insn with the least dependences upon the previously
  69    scheduled insn, or finally
  70    7   choose the insn which has the most insns dependent on it.
  71    8.  choose insn with lowest UID.
  72
  73    Memory references complicate matters.  Only if we can be certain
  74    that memory references are not part of the data dependency graph
  75    (via true, anti, or output dependence), can we move operations past
  76    memory references.  To first approximation, reads can be done
  77    independently, while writes introduce dependencies.  Better
  78    approximations will yield fewer dependencies.
  79
  80    Before reload, an extended analysis of interblock data dependences
  81    is required for interblock scheduling.  This is performed in
  82    compute_block_backward_dependences ().
  83
  84    Dependencies set up by memory references are treated in exactly the
  85    same way as other dependencies, by using LOG_LINKS backward
  86    dependences.  LOG_LINKS are translated into INSN_DEPEND forward
  87    dependences for the purpose of forward list scheduling.
  88
  89    Having optimized the critical path, we may have also unduly
  90    extended the lifetimes of some registers.  If an operation requires
  91    that constants be loaded into registers, it is certainly desirable
  92    to load those constants as early as necessary, but no earlier.
  93    I.e., it will not do to load up a bunch of registers at the
  94    beginning of a basic block only to use them at the end, if they
  95    could be loaded later, since this may result in excessive register
  96    utilization.
  97
  98    Note that since branches are never in basic blocks, but only end
  99    basic blocks, this pass will not move branches.  But that is ok,
 100    since we can use GNU's delayed branch scheduling pass to take care
 101    of this case.
 102
 103    Also note that no further optimizations based on algebraic
 104    identities are performed, so this pass would be a good one to
 105    perform instruction splitting, such as breaking up a multiply
 106    instruction into shifts and adds where that is profitable.
 107
 108    Given the memory aliasing analysis that this pass should perform,
 109    it should be possible to remove redundant stores to memory, and to
 110    load values from registers instead of hitting memory.
 111
 112    Before reload, speculative insns are moved only if a 'proof' exists
 113    that no exception will be caused by this, and if no live registers
 114    exist that inhibit the motion (live registers constraints are not
 115    represented by data dependence edges).
 116
 117    This pass must update information that subsequent passes expect to
 118    be correct.  Namely: reg_n_refs, reg_n_sets, reg_n_deaths,
 119    reg_n_calls_crossed, and reg_live_length.  Also, BB_HEAD, BB_END.
 120
 121    The information in the line number notes is carefully retained by
 122    this pass.  Notes that refer to the starting and ending of
 123    exception regions are also carefully retained by this pass.  All
 124    other NOTE insns are grouped in their same relative order at the
 125    beginning of basic blocks and regions that have been scheduled.  */
 126 \f
 127 #include "config.h"
 128 #include "system.h"
 129 #include "coretypes.h"
 130 #include "tm.h"
 131 #include "toplev.h"
 132 #include "rtl.h"
 133 #include "tm_p.h"
 134 #include "hard-reg-set.h"
 135 #include "regs.h"
 136 #include "function.h"
 137 #include "flags.h"
 138 #include "insn-config.h"
 139 #include "insn-attr.h"
 140 #include "except.h"
 141 #include "toplev.h"
 142 #include "recog.h"
 143 #include "sched-int.h"
 144 #include "target.h"
 145
 146 #ifdef INSN_SCHEDULING
 147
 148 /* issue_rate is the number of insns that can be scheduled in the same
 149    machine cycle.  It can be defined in the config/mach/mach.h file,
 150    otherwise we set it to 1.  */
 151
 152 static int issue_rate;
 153
 154 /* sched-verbose controls the amount of debugging output the
 155    scheduler prints.  It is controlled by -fsched-verbose=N:
 156    N>0 and no -DSR : the output is directed to stderr.
 157    N>=10 will direct the printouts to stderr (regardless of -dSR).
 158    N=1: same as -dSR.
 159    N=2: bb's probabilities, detailed ready list info, unit/insn info.
 160    N=3: rtl at abort point, control-flow, regions info.
 161    N=5: dependences info.  */
 162
 163 static int sched_verbose_param = 0;
 164 int sched_verbose = 0;
 165
 166 /* Debugging file.  All printouts are sent to dump, which is always set,
 167    either to stderr, or to the dump listing file (-dRS).  */
 168 FILE *sched_dump = 0;
 169
 170 /* Highest uid before scheduling.  */
 171 static int old_max_uid;
 172
 173 /* fix_sched_param() is called from toplev.c upon detection
 174    of the -fsched-verbose=N option.  */
 175
 176 void
 177 fix_sched_param (const char *param, const char *val)
 178 {
 179   if (!strcmp (param, "verbose"))
 180     sched_verbose_param = atoi (val);
 181   else
 182     warning (0, "fix_sched_param: unknown param: %s", param);
 183 }
 184
 185 struct haifa_insn_data *h_i_d;
 186
 187 #define LINE_NOTE(INSN)         (h_i_d[INSN_UID (INSN)].line_note)
 188 #define INSN_TICK(INSN)         (h_i_d[INSN_UID (INSN)].tick)
 189
 190 /* Vector indexed by basic block number giving the starting line-number
 191    for each basic block.  */
 192 static rtx *line_note_head;
 193
 194 /* List of important notes we must keep around.  This is a pointer to the
 195    last element in the list.  */
 196 static rtx note_list;
 197
 198 /* Queues, etc.  */
 199
 200 /* An instruction is ready to be scheduled when all insns preceding it
 201    have already been scheduled.  It is important to ensure that all
 202    insns which use its result will not be executed until its result
 203    has been computed.  An insn is maintained in one of four structures:
 204
 205    (P) the "Pending" set of insns which cannot be scheduled until
 206    their dependencies have been satisfied.
 207    (Q) the "Queued" set of insns that can be scheduled when sufficient
 208    time has passed.
 209    (R) the "Ready" list of unscheduled, uncommitted insns.
 210    (S) the "Scheduled" list of insns.
 211
 212    Initially, all insns are either "Pending" or "Ready" depending on
 213    whether their dependencies are satisfied.
 214
 215    Insns move from the "Ready" list to the "Scheduled" list as they
 216    are committed to the schedule.  As this occurs, the insns in the
 217    "Pending" list have their dependencies satisfied and move to either
 218    the "Ready" list or the "Queued" set depending on whether
 219    sufficient time has passed to make them ready.  As time passes,
 220    insns move from the "Queued" set to the "Ready" list.
 221
 222    The "Pending" list (P) are the insns in the INSN_DEPEND of the unscheduled
 223    insns, i.e., those that are ready, queued, and pending.
 224    The "Queued" set (Q) is implemented by the variable `insn_queue'.
 225    The "Ready" list (R) is implemented by the variables `ready' and
 226    `n_ready'.
 227    The "Scheduled" list (S) is the new insn chain built by this pass.
 228
 229    The transition (R->S) is implemented in the scheduling loop in
 230    `schedule_block' when the best insn to schedule is chosen.
 231    The transitions (P->R and P->Q) are implemented in `schedule_insn' as
 232    insns move from the ready list to the scheduled list.
 233    The transition (Q->R) is implemented in 'queue_to_insn' as time
 234    passes or stalls are introduced.  */
 235
 236 /* Implement a circular buffer to delay instructions until sufficient
 237    time has passed.  For the new pipeline description interface,
 238    MAX_INSN_QUEUE_INDEX is a power of two minus one which is larger
 239    than maximal time of instruction execution computed by genattr.c on
 240    the base maximal time of functional unit reservations and getting a
 241    result.  This is the longest time an insn may be queued.  */
 242
 243 static rtx *insn_queue;
 244 static int q_ptr = 0;
 245 static int q_size = 0;
 246 #define NEXT_Q(X) (((X)+1) & max_insn_queue_index)
 247 #define NEXT_Q_AFTER(X, C) (((X)+C) & max_insn_queue_index)
 248
 249 /* The following variable value refers for all current and future
 250    reservations of the processor units.  */
 251 state_t curr_state;
 252
 253 /* The following variable value is size of memory representing all
 254    current and future reservations of the processor units.  */
 255 static size_t dfa_state_size;
 256
 257 /* The following array is used to find the best insn from ready when
 258    the automaton pipeline interface is used.  */
 259 static char *ready_try;
 260
 261 /* Describe the ready list of the scheduler.
 262    VEC holds space enough for all insns in the current region.  VECLEN
 263    says how many exactly.
 264    FIRST is the index of the element with the highest priority; i.e. the
 265    last one in the ready list, since elements are ordered by ascending
 266    priority.
 267    N_READY determines how many insns are on the ready list.  */
 268
 269 struct ready_list
 270 {
 271   rtx *vec;
 272   int veclen;
 273   int first;
 274   int n_ready;
 275 };
 276
 277 static int may_trap_exp (rtx, int);
 278
 279 /* Nonzero iff the address is comprised from at most 1 register.  */
 280 #define CONST_BASED_ADDRESS_P(x)                        \
 281   (REG_P (x)                                    \
 282    || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS   \
 283         || (GET_CODE (x) == LO_SUM))                    \
 284        && (CONSTANT_P (XEXP (x, 0))                     \
 285            || CONSTANT_P (XEXP (x, 1)))))
 286
 287 /* Returns a class that insn with GET_DEST(insn)=x may belong to,
 288    as found by analyzing insn's expression.  */
 289
 290 static int
 291 may_trap_exp (rtx x, int is_store)
 292 {
 293   enum rtx_code code;
 294
 295   if (x == 0)
 296     return TRAP_FREE;
 297   code = GET_CODE (x);
 298   if (is_store)
 299     {
 300       if (code == MEM && may_trap_p (x))
 301         return TRAP_RISKY;
 302       else
 303         return TRAP_FREE;
 304     }
 305   if (code == MEM)
 306     {
 307       /* The insn uses memory:  a volatile load.  */
 308       if (MEM_VOLATILE_P (x))
 309         return IRISKY;
 310       /* An exception-free load.  */
 311       if (!may_trap_p (x))
 312         return IFREE;
 313       /* A load with 1 base register, to be further checked.  */
 314       if (CONST_BASED_ADDRESS_P (XEXP (x, 0)))
 315         return PFREE_CANDIDATE;
 316       /* No info on the load, to be further checked.  */
 317       return PRISKY_CANDIDATE;
 318     }
 319   else
 320     {
 321       const char *fmt;
 322       int i, insn_class = TRAP_FREE;
 323
 324       /* Neither store nor load, check if it may cause a trap.  */
 325       if (may_trap_p (x))
 326         return TRAP_RISKY;
 327       /* Recursive step: walk the insn...  */
 328       fmt = GET_RTX_FORMAT (code);
 329       for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 330         {
 331           if (fmt[i] == 'e')
 332             {
 333               int tmp_class = may_trap_exp (XEXP (x, i), is_store);
 334               insn_class = WORST_CLASS (insn_class, tmp_class);
 335             }
 336           else if (fmt[i] == 'E')
 337             {
 338               int j;
 339               for (j = 0; j < XVECLEN (x, i); j++)
 340                 {
 341                   int tmp_class = may_trap_exp (XVECEXP (x, i, j), is_store);
 342                   insn_class = WORST_CLASS (insn_class, tmp_class);
 343                   if (insn_class == TRAP_RISKY || insn_class == IRISKY)
 344                     break;
 345                 }
 346             }
 347           if (insn_class == TRAP_RISKY || insn_class == IRISKY)
 348             break;
 349         }
 350       return insn_class;
 351     }
 352 }
 353
 354 /* Classifies insn for the purpose of verifying that it can be
 355    moved speculatively, by examining it's patterns, returning:
 356    TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
 357    TRAP_FREE: non-load insn.
 358    IFREE: load from a globally safe location.
 359    IRISKY: volatile load.
 360    PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
 361    being either PFREE or PRISKY.  */
 362
 363 int
 364 haifa_classify_insn (rtx insn)
 365 {
 366   rtx pat = PATTERN (insn);
 367   int tmp_class = TRAP_FREE;
 368   int insn_class = TRAP_FREE;
 369   enum rtx_code code;
 370
 371   if (GET_CODE (pat) == PARALLEL)
 372     {
 373       int i, len = XVECLEN (pat, 0);
 374
 375       for (i = len - 1; i >= 0; i--)
 376         {
 377           code = GET_CODE (XVECEXP (pat, 0, i));
 378           switch (code)
 379             {
 380             case CLOBBER:
 381               /* Test if it is a 'store'.  */
 382               tmp_class = may_trap_exp (XEXP (XVECEXP (pat, 0, i), 0), 1);
 383               break;
 384             case SET:
 385               /* Test if it is a store.  */
 386               tmp_class = may_trap_exp (SET_DEST (XVECEXP (pat, 0, i)), 1);
 387               if (tmp_class == TRAP_RISKY)
 388                 break;
 389               /* Test if it is a load.  */
 390               tmp_class
 391                 = WORST_CLASS (tmp_class,
 392                                may_trap_exp (SET_SRC (XVECEXP (pat, 0, i)),
 393                                              0));
 394               break;
 395             case COND_EXEC:
 396             case TRAP_IF:
 397               tmp_class = TRAP_RISKY;
 398               break;
 399             default:
 400               ;
 401             }
 402           insn_class = WORST_CLASS (insn_class, tmp_class);
 403           if (insn_class == TRAP_RISKY || insn_class == IRISKY)
 404             break;
 405         }
 406     }
 407   else
 408     {
 409       code = GET_CODE (pat);
 410       switch (code)
 411         {
 412         case CLOBBER:
 413           /* Test if it is a 'store'.  */
 414           tmp_class = may_trap_exp (XEXP (pat, 0), 1);
 415           break;
 416         case SET:
 417           /* Test if it is a store.  */
 418           tmp_class = may_trap_exp (SET_DEST (pat), 1);
 419           if (tmp_class == TRAP_RISKY)
 420             break;
 421           /* Test if it is a load.  */
 422           tmp_class =
 423             WORST_CLASS (tmp_class,
 424                          may_trap_exp (SET_SRC (pat), 0));
 425           break;
 426         case COND_EXEC:
 427         case TRAP_IF:
 428           tmp_class = TRAP_RISKY;
 429           break;
 430         default:;
 431         }
 432       insn_class = tmp_class;
 433     }
 434
 435   return insn_class;
 436 }
 437
 438 /* Forward declarations.  */
 439
 440 static int priority (rtx);
 441 static int rank_for_schedule (const void *, const void *);
 442 static void swap_sort (rtx *, int);
 443 static void queue_insn (rtx, int);
 444 static int schedule_insn (rtx, struct ready_list *, int);
 445 static int find_set_reg_weight (rtx);
 446 static void find_insn_reg_weight (int);
 447 static void adjust_priority (rtx);
 448 static void advance_one_cycle (void);
 449
 450 /* Notes handling mechanism:
 451    =========================
 452    Generally, NOTES are saved before scheduling and restored after scheduling.
 453    The scheduler distinguishes between three types of notes:
 454
 455    (1) LINE_NUMBER notes, generated and used for debugging.  Here,
 456    before scheduling a region, a pointer to the LINE_NUMBER note is
 457    added to the insn following it (in save_line_notes()), and the note
 458    is removed (in rm_line_notes() and unlink_line_notes()).  After
 459    scheduling the region, this pointer is used for regeneration of
 460    the LINE_NUMBER note (in restore_line_notes()).
 461
 462    (2) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes:
 463    Before scheduling a region, a pointer to the note is added to the insn
 464    that follows or precedes it.  (This happens as part of the data dependence
 465    computation).  After scheduling an insn, the pointer contained in it is
 466    used for regenerating the corresponding note (in reemit_notes).
 467
 468    (3) All other notes (e.g. INSN_DELETED):  Before scheduling a block,
 469    these notes are put in a list (in rm_other_notes() and
 470    unlink_other_notes ()).  After scheduling the block, these notes are
 471    inserted at the beginning of the block (in schedule_block()).  */
 472
 473 static rtx unlink_other_notes (rtx, rtx);
 474 static rtx unlink_line_notes (rtx, rtx);
 475 static rtx reemit_notes (rtx, rtx);
 476
 477 static rtx *ready_lastpos (struct ready_list *);
 478 static void ready_sort (struct ready_list *);
 479 static rtx ready_remove_first (struct ready_list *);
 480
 481 static void queue_to_ready (struct ready_list *);
 482 static int early_queue_to_ready (state_t, struct ready_list *);
 483
 484 static void debug_ready_list (struct ready_list *);
 485
 486 static rtx move_insn1 (rtx, rtx);
 487 static rtx move_insn (rtx, rtx);
 488
 489 /* The following functions are used to implement multi-pass scheduling
 490    on the first cycle.  */
 491 static rtx ready_element (struct ready_list *, int);
 492 static rtx ready_remove (struct ready_list *, int);
 493 static int max_issue (struct ready_list *, int *);
 494
 495 static rtx choose_ready (struct ready_list *);
 496
 497 #endif /* INSN_SCHEDULING */
 498 \f
 499 /* Point to state used for the current scheduling pass.  */
 500 struct sched_info *current_sched_info;
 501 \f
 502 #ifndef INSN_SCHEDULING
 503 void
 504 schedule_insns (FILE *dump_file ATTRIBUTE_UNUSED)
 505 {
 506 }
 507 #else
 508
 509 /* Pointer to the last instruction scheduled.  Used by rank_for_schedule,
 510    so that insns independent of the last scheduled insn will be preferred
 511    over dependent instructions.  */
 512
 513 static rtx last_scheduled_insn;
 514
 515 /* Compute cost of executing INSN given the dependence LINK on the insn USED.
 516    This is the number of cycles between instruction issue and
 517    instruction results.  */
 518
 519 HAIFA_INLINE int
 520 insn_cost (rtx insn, rtx link, rtx used)
 521 {
 522   int cost = INSN_COST (insn);
 523
 524   if (cost < 0)
 525     {
 526       /* A USE insn, or something else we don't need to
 527          understand.  We can't pass these directly to
 528          result_ready_cost or insn_default_latency because it will
 529          trigger a fatal error for unrecognizable insns.  */
 530       if (recog_memoized (insn) < 0)
 531         {
 532           INSN_COST (insn) = 0;
 533           return 0;
 534         }
 535       else
 536         {
 537           cost = insn_default_latency (insn);
 538           if (cost < 0)
 539             cost = 0;
 540
 541           INSN_COST (insn) = cost;
 542         }
 543     }
 544
 545   /* In this case estimate cost without caring how insn is used.  */
 546   if (link == 0 || used == 0)
 547     return cost;
 548
 549   /* A USE insn should never require the value used to be computed.
 550      This allows the computation of a function's result and parameter
 551      values to overlap the return and call.  */
 552   if (recog_memoized (used) < 0)
 553     cost = 0;
 554   else
 555     {
 556       if (INSN_CODE (insn) >= 0)
 557         {
 558           if (REG_NOTE_KIND (link) == REG_DEP_ANTI)
 559             cost = 0;
 560           else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT)
 561             {
 562               cost = (insn_default_latency (insn)
 563                       - insn_default_latency (used));
 564               if (cost <= 0)
 565                 cost = 1;
 566             }
 567           else if (bypass_p (insn))
 568             cost = insn_latency (insn, used);
 569         }
 570
 571       if (targetm.sched.adjust_cost)
 572         cost = targetm.sched.adjust_cost (used, link, insn, cost);
 573
 574       if (cost < 0)
 575         cost = 0;
 576     }
 577
 578   return cost;
 579 }
 580
 581 /* Compute the priority number for INSN.  */
 582
 583 static int
 584 priority (rtx insn)
 585 {
 586   rtx link;
 587
 588   if (! INSN_P (insn))
 589     return 0;
 590
 591   if (! INSN_PRIORITY_KNOWN (insn))
 592     {
 593       int this_priority = 0;
 594
 595       if (INSN_DEPEND (insn) == 0)
 596         this_priority = insn_cost (insn, 0, 0);
 597       else
 598         {
 599           for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
 600             {
 601               rtx next;
 602               int next_priority;
 603
 604               next = XEXP (link, 0);
 605
 606               /* Critical path is meaningful in block boundaries only.  */
 607               if (! (*current_sched_info->contributes_to_priority) (next, insn))
 608                 continue;
 609
 610               next_priority = insn_cost (insn, link, next) + priority (next);
 611               if (next_priority > this_priority)
 612                 this_priority = next_priority;
 613             }
 614         }
 615       INSN_PRIORITY (insn) = this_priority;
 616       INSN_PRIORITY_KNOWN (insn) = 1;
 617     }
 618
 619   return INSN_PRIORITY (insn);
 620 }
 621 \f
 622 /* Macros and functions for keeping the priority queue sorted, and
 623    dealing with queuing and dequeuing of instructions.  */
 624
 625 #define SCHED_SORT(READY, N_READY)                                   \
 626 do { if ((N_READY) == 2)                                             \
 627        swap_sort (READY, N_READY);                                   \
 628      else if ((N_READY) > 2)                                         \
 629          qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); }  \
 630 while (0)
 631
 632 /* Returns a positive value if x is preferred; returns a negative value if
 633    y is preferred.  Should never return 0, since that will make the sort
 634    unstable.  */
 635
 636 static int
 637 rank_for_schedule (const void *x, const void *y)
 638 {
 639   rtx tmp = *(const rtx *) y;
 640   rtx tmp2 = *(const rtx *) x;
 641   rtx link;
 642   int tmp_class, tmp2_class, depend_count1, depend_count2;
 643   int val, priority_val, weight_val, info_val;
 644
 645   /* The insn in a schedule group should be issued the first.  */
 646   if (SCHED_GROUP_P (tmp) != SCHED_GROUP_P (tmp2))
 647     return SCHED_GROUP_P (tmp2) ? 1 : -1;
 648
 649   /* Prefer insn with higher priority.  */
 650   priority_val = INSN_PRIORITY (tmp2) - INSN_PRIORITY (tmp);
 651
 652   if (priority_val)
 653     return priority_val;
 654
 655   /* Prefer an insn with smaller contribution to registers-pressure.  */
 656   if (!reload_completed &&
 657       (weight_val = INSN_REG_WEIGHT (tmp) - INSN_REG_WEIGHT (tmp2)))
 658     return weight_val;
 659
 660   info_val = (*current_sched_info->rank) (tmp, tmp2);
 661   if (info_val)
 662     return info_val;
 663
 664   /* Compare insns based on their relation to the last-scheduled-insn.  */
 665   if (last_scheduled_insn)
 666     {
 667       /* Classify the instructions into three classes:
 668          1) Data dependent on last schedule insn.
 669          2) Anti/Output dependent on last scheduled insn.
 670          3) Independent of last scheduled insn, or has latency of one.
 671          Choose the insn from the highest numbered class if different.  */
 672       link = find_insn_list (tmp, INSN_DEPEND (last_scheduled_insn));
 673       if (link == 0 || insn_cost (last_scheduled_insn, link, tmp) == 1)
 674         tmp_class = 3;
 675       else if (REG_NOTE_KIND (link) == 0)       /* Data dependence.  */
 676         tmp_class = 1;
 677       else
 678         tmp_class = 2;
 679
 680       link = find_insn_list (tmp2, INSN_DEPEND (last_scheduled_insn));
 681       if (link == 0 || insn_cost (last_scheduled_insn, link, tmp2) == 1)
 682         tmp2_class = 3;
 683       else if (REG_NOTE_KIND (link) == 0)       /* Data dependence.  */
 684         tmp2_class = 1;
 685       else
 686         tmp2_class = 2;
 687
 688       if ((val = tmp2_class - tmp_class))
 689         return val;
 690     }
 691
 692   /* Prefer the insn which has more later insns that depend on it.
 693      This gives the scheduler more freedom when scheduling later
 694      instructions at the expense of added register pressure.  */
 695   depend_count1 = 0;
 696   for (link = INSN_DEPEND (tmp); link; link = XEXP (link, 1))
 697     depend_count1++;
 698
 699   depend_count2 = 0;
 700   for (link = INSN_DEPEND (tmp2); link; link = XEXP (link, 1))
 701     depend_count2++;
 702
 703   val = depend_count2 - depend_count1;
 704   if (val)
 705     return val;
 706
 707   /* If insns are equally good, sort by INSN_LUID (original insn order),
 708      so that we make the sort stable.  This minimizes instruction movement,
 709      thus minimizing sched's effect on debugging and cross-jumping.  */
 710   return INSN_LUID (tmp) - INSN_LUID (tmp2);
 711 }
 712
 713 /* Resort the array A in which only element at index N may be out of order.  */
 714
 715 HAIFA_INLINE static void
 716 swap_sort (rtx *a, int n)
 717 {
 718   rtx insn = a[n - 1];
 719   int i = n - 2;
 720
 721   while (i >= 0 && rank_for_schedule (a + i, &insn) >= 0)
 722     {
 723       a[i + 1] = a[i];
 724       i -= 1;
 725     }
 726   a[i + 1] = insn;
 727 }
 728
 729 /* Add INSN to the insn queue so that it can be executed at least
 730    N_CYCLES after the currently executing insn.  Preserve insns
 731    chain for debugging purposes.  */
 732
 733 HAIFA_INLINE static void
 734 queue_insn (rtx insn, int n_cycles)
 735 {
 736   int next_q = NEXT_Q_AFTER (q_ptr, n_cycles);
 737   rtx link = alloc_INSN_LIST (insn, insn_queue[next_q]);
 738   insn_queue[next_q] = link;
 739   q_size += 1;
 740
 741   if (sched_verbose >= 2)
 742     {
 743       fprintf (sched_dump, ";;\t\tReady-->Q: insn %s: ",
 744                (*current_sched_info->print_insn) (insn, 0));
 745
 746       fprintf (sched_dump, "queued for %d cycles.\n", n_cycles);
 747     }
 748 }
 749
 750 /* Return a pointer to the bottom of the ready list, i.e. the insn
 751    with the lowest priority.  */
 752
 753 HAIFA_INLINE static rtx *
 754 ready_lastpos (struct ready_list *ready)
 755 {
 756   gcc_assert (ready->n_ready);
 757   return ready->vec + ready->first - ready->n_ready + 1;
 758 }
 759
 760 /* Add an element INSN to the ready list so that it ends up with the lowest
 761    priority.  */
 762
 763 HAIFA_INLINE void
 764 ready_add (struct ready_list *ready, rtx insn)
 765 {
 766   if (ready->first == ready->n_ready)
 767     {
 768       memmove (ready->vec + ready->veclen - ready->n_ready,
 769                ready_lastpos (ready),
 770                ready->n_ready * sizeof (rtx));
 771       ready->first = ready->veclen - 1;
 772     }
 773   ready->vec[ready->first - ready->n_ready] = insn;
 774   ready->n_ready++;
 775 }
 776
 777 /* Remove the element with the highest priority from the ready list and
 778    return it.  */
 779
 780 HAIFA_INLINE static rtx
 781 ready_remove_first (struct ready_list *ready)
 782 {
 783   rtx t;
 784
 785   gcc_assert (ready->n_ready);
 786   t = ready->vec[ready->first--];
 787   ready->n_ready--;
 788   /* If the queue becomes empty, reset it.  */
 789   if (ready->n_ready == 0)
 790     ready->first = ready->veclen - 1;
 791   return t;
 792 }
 793
 794 /* The following code implements multi-pass scheduling for the first
 795    cycle.  In other words, we will try to choose ready insn which
 796    permits to start maximum number of insns on the same cycle.  */
 797
 798 /* Return a pointer to the element INDEX from the ready.  INDEX for
 799    insn with the highest priority is 0, and the lowest priority has
 800    N_READY - 1.  */
 801
 802 HAIFA_INLINE static rtx
 803 ready_element (struct ready_list *ready, int index)
 804 {
 805   gcc_assert (ready->n_ready && index < ready->n_ready);
 806
 807   return ready->vec[ready->first - index];
 808 }
 809
 810 /* Remove the element INDEX from the ready list and return it.  INDEX
 811    for insn with the highest priority is 0, and the lowest priority
 812    has N_READY - 1.  */
 813
 814 HAIFA_INLINE static rtx
 815 ready_remove (struct ready_list *ready, int index)
 816 {
 817   rtx t;
 818   int i;
 819
 820   if (index == 0)
 821     return ready_remove_first (ready);
 822   gcc_assert (ready->n_ready && index < ready->n_ready);
 823   t = ready->vec[ready->first - index];
 824   ready->n_ready--;
 825   for (i = index; i < ready->n_ready; i++)
 826     ready->vec[ready->first - i] = ready->vec[ready->first - i - 1];
 827   return t;
 828 }
 829
 830
 831 /* Sort the ready list READY by ascending priority, using the SCHED_SORT
 832    macro.  */
 833
 834 HAIFA_INLINE static void
 835 ready_sort (struct ready_list *ready)
 836 {
 837   rtx *first = ready_lastpos (ready);
 838   SCHED_SORT (first, ready->n_ready);
 839 }
 840
 841 /* PREV is an insn that is ready to execute.  Adjust its priority if that
 842    will help shorten or lengthen register lifetimes as appropriate.  Also
 843    provide a hook for the target to tweek itself.  */
 844
 845 HAIFA_INLINE static void
 846 adjust_priority (rtx prev)
 847 {
 848   /* ??? There used to be code here to try and estimate how an insn
 849      affected register lifetimes, but it did it by looking at REG_DEAD
 850      notes, which we removed in schedule_region.  Nor did it try to
 851      take into account register pressure or anything useful like that.
 852
 853      Revisit when we have a machine model to work with and not before.  */
 854
 855   if (targetm.sched.adjust_priority)
 856     INSN_PRIORITY (prev) =
 857       targetm.sched.adjust_priority (prev, INSN_PRIORITY (prev));
 858 }
 859
 860 /* Advance time on one cycle.  */
 861 HAIFA_INLINE static void
 862 advance_one_cycle (void)
 863 {
 864   if (targetm.sched.dfa_pre_cycle_insn)
 865     state_transition (curr_state,
 866                       targetm.sched.dfa_pre_cycle_insn ());
 867
 868   state_transition (curr_state, NULL);
 869
 870   if (targetm.sched.dfa_post_cycle_insn)
 871     state_transition (curr_state,
 872                       targetm.sched.dfa_post_cycle_insn ());
 873 }
 874
 875 /* Clock at which the previous instruction was issued.  */
 876 static int last_clock_var;
 877
 878 /* INSN is the "currently executing insn".  Launch each insn which was
 879    waiting on INSN.  READY is the ready list which contains the insns
 880    that are ready to fire.  CLOCK is the current cycle.  The function
 881    returns necessary cycle advance after issuing the insn (it is not
 882    zero for insns in a schedule group).  */
 883
 884 static int
 885 schedule_insn (rtx insn, struct ready_list *ready, int clock)
 886 {
 887   rtx link;
 888   int advance = 0;
 889   int premature_issue = 0;
 890
 891   if (sched_verbose >= 1)
 892     {
 893       char buf[2048];
 894
 895       print_insn (buf, insn, 0);
 896       buf[40] = 0;
 897       fprintf (sched_dump, ";;\t%3i--> %-40s:", clock, buf);
 898
 899       if (recog_memoized (insn) < 0)
 900         fprintf (sched_dump, "nothing");
 901       else
 902         print_reservation (sched_dump, insn);
 903       fputc ('\n', sched_dump);
 904     }
 905
 906   if (INSN_TICK (insn) > clock)
 907     {
 908       /* 'insn' has been prematurely moved from the queue to the
 909          ready list.  */
 910       premature_issue = INSN_TICK (insn) - clock;
 911     }
 912
 913   for (link = INSN_DEPEND (insn); link != 0; link = XEXP (link, 1))
 914     {
 915       rtx next = XEXP (link, 0);
 916       int cost = insn_cost (insn, link, next);
 917
 918       INSN_TICK (next) = MAX (INSN_TICK (next), clock + cost + premature_issue);
 919
 920       if ((INSN_DEP_COUNT (next) -= 1) == 0)
 921         {
 922           int effective_cost = INSN_TICK (next) - clock;
 923
 924           if (! (*current_sched_info->new_ready) (next))
 925             continue;
 926
 927           if (sched_verbose >= 2)
 928             {
 929               fprintf (sched_dump, ";;\t\tdependences resolved: insn %s ",
 930                        (*current_sched_info->print_insn) (next, 0));
 931
 932               if (effective_cost < 1)
 933                 fprintf (sched_dump, "into ready\n");
 934               else
 935                 fprintf (sched_dump, "into queue with cost=%d\n",
 936                          effective_cost);
 937             }
 938
 939           /* Adjust the priority of NEXT and either put it on the ready
 940              list or queue it.  */
 941           adjust_priority (next);
 942           if (effective_cost < 1)
 943             ready_add (ready, next);
 944           else
 945             {
 946               queue_insn (next, effective_cost);
 947
 948               if (SCHED_GROUP_P (next) && advance < effective_cost)
 949                 advance = effective_cost;
 950             }
 951         }
 952     }
 953
 954   /* Annotate the instruction with issue information -- TImode
 955      indicates that the instruction is expected not to be able
 956      to issue on the same cycle as the previous insn.  A machine
 957      may use this information to decide how the instruction should
 958      be aligned.  */
 959   if (issue_rate > 1
 960       && GET_CODE (PATTERN (insn)) != USE
 961       && GET_CODE (PATTERN (insn)) != CLOBBER)
 962     {
 963       if (reload_completed)
 964         PUT_MODE (insn, clock > last_clock_var ? TImode : VOIDmode);
 965       last_clock_var = clock;
 966     }
 967   return advance;
 968 }
 969
 970 /* Functions for handling of notes.  */
 971
 972 /* Delete notes beginning with INSN and put them in the chain
 973    of notes ended by NOTE_LIST.
 974    Returns the insn following the notes.  */
 975
 976 static rtx
 977 unlink_other_notes (rtx insn, rtx tail)
 978 {
 979   rtx prev = PREV_INSN (insn);
 980
 981   while (insn != tail && NOTE_P (insn))
 982     {
 983       rtx next = NEXT_INSN (insn);
 984       /* Delete the note from its current position.  */
 985       if (prev)
 986         NEXT_INSN (prev) = next;
 987       if (next)
 988         PREV_INSN (next) = prev;
 989
 990       /* See sched_analyze to see how these are handled.  */
 991       if (NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG
 992           && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_END
 993           && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK
 994           && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_BEG
 995           && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_END)
 996         {
 997           /* Insert the note at the end of the notes list.  */
 998           PREV_INSN (insn) = note_list;
 999           if (note_list)
1000             NEXT_INSN (note_list) = insn;
1001           note_list = insn;
1002         }
1003
1004       insn = next;
1005     }
1006   return insn;
1007 }
1008
1009 /* Delete line notes beginning with INSN. Record line-number notes so
1010    they can be reused.  Returns the insn following the notes.  */
1011
1012 static rtx
1013 unlink_line_notes (rtx insn, rtx tail)
1014 {
1015   rtx prev = PREV_INSN (insn);
1016
1017   while (insn != tail && NOTE_P (insn))
1018     {
1019       rtx next = NEXT_INSN (insn);
1020
1021       if (write_symbols != NO_DEBUG && NOTE_LINE_NUMBER (insn) > 0)
1022         {
1023           /* Delete the note from its current position.  */
1024           if (prev)
1025             NEXT_INSN (prev) = next;
1026           if (next)
1027             PREV_INSN (next) = prev;
1028
1029           /* Record line-number notes so they can be reused.  */
1030           LINE_NOTE (insn) = insn;
1031         }
1032       else
1033         prev = insn;
1034
1035       insn = next;
1036     }
1037   return insn;
1038 }
1039
1040 /* Return the head and tail pointers of BB.  */
1041
1042 void
1043 get_block_head_tail (int b, rtx *headp, rtx *tailp)
1044 {
1045   /* HEAD and TAIL delimit the basic block being scheduled.  */
1046   rtx head = BB_HEAD (BASIC_BLOCK (b));
1047   rtx tail = BB_END (BASIC_BLOCK (b));
1048
1049   /* Don't include any notes or labels at the beginning of the
1050      basic block, or notes at the ends of basic blocks.  */
1051   while (head != tail)
1052     {
1053       if (NOTE_P (head))
1054         head = NEXT_INSN (head);
1055       else if (NOTE_P (tail))
1056         tail = PREV_INSN (tail);
1057       else if (LABEL_P (head))
1058         head = NEXT_INSN (head);
1059       else
1060         break;
1061     }
1062
1063   *headp = head;
1064   *tailp = tail;
1065 }
1066
1067 /* Return nonzero if there are no real insns in the range [ HEAD, TAIL ].  */
1068
1069 int
1070 no_real_insns_p (rtx head, rtx tail)
1071 {
1072   while (head != NEXT_INSN (tail))
1073     {
1074       if (!NOTE_P (head) && !LABEL_P (head))
1075         return 0;
1076       head = NEXT_INSN (head);
1077     }
1078   return 1;
1079 }
1080
1081 /* Delete line notes from one block. Save them so they can be later restored
1082    (in restore_line_notes).  HEAD and TAIL are the boundaries of the
1083    block in which notes should be processed.  */
1084
1085 void
1086 rm_line_notes (rtx head, rtx tail)
1087 {
1088   rtx next_tail;
1089   rtx insn;
1090
1091   next_tail = NEXT_INSN (tail);
1092   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
1093     {
1094       rtx prev;
1095
1096       /* Farm out notes, and maybe save them in NOTE_LIST.
1097          This is needed to keep the debugger from
1098          getting completely deranged.  */
1099       if (NOTE_P (insn))
1100         {
1101           prev = insn;
1102           insn = unlink_line_notes (insn, next_tail);
1103
1104           gcc_assert (prev != tail && prev != head && insn != next_tail);
1105         }
1106     }
1107 }
1108
1109 /* Save line number notes for each insn in block B.  HEAD and TAIL are
1110    the boundaries of the block in which notes should be processed.  */
1111
1112 void
1113 save_line_notes (int b, rtx head, rtx tail)
1114 {
1115   rtx next_tail;
1116
1117   /* We must use the true line number for the first insn in the block
1118      that was computed and saved at the start of this pass.  We can't
1119      use the current line number, because scheduling of the previous
1120      block may have changed the current line number.  */
1121
1122   rtx line = line_note_head[b];
1123   rtx insn;
1124
1125   next_tail = NEXT_INSN (tail);
1126
1127   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
1128     if (NOTE_P (insn) && NOTE_LINE_NUMBER (insn) > 0)
1129       line = insn;
1130     else
1131       LINE_NOTE (insn) = line;
1132 }
1133
1134 /* After a block was scheduled, insert line notes into the insns list.
1135    HEAD and TAIL are the boundaries of the block in which notes should
1136    be processed.  */
1137
1138 void
1139 restore_line_notes (rtx head, rtx tail)
1140 {
1141   rtx line, note, prev, new;
1142   int added_notes = 0;
1143   rtx next_tail, insn;
1144
1145   head = head;
1146   next_tail = NEXT_INSN (tail);
1147
1148   /* Determine the current line-number.  We want to know the current
1149      line number of the first insn of the block here, in case it is
1150      different from the true line number that was saved earlier.  If
1151      different, then we need a line number note before the first insn
1152      of this block.  If it happens to be the same, then we don't want to
1153      emit another line number note here.  */
1154   for (line = head; line; line = PREV_INSN (line))
1155     if (NOTE_P (line) && NOTE_LINE_NUMBER (line) > 0)
1156       break;
1157
1158   /* Walk the insns keeping track of the current line-number and inserting
1159      the line-number notes as needed.  */
1160   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
1161     if (NOTE_P (insn) && NOTE_LINE_NUMBER (insn) > 0)
1162       line = insn;
1163   /* This used to emit line number notes before every non-deleted note.
1164      However, this confuses a debugger, because line notes not separated
1165      by real instructions all end up at the same address.  I can find no
1166      use for line number notes before other notes, so none are emitted.  */
1167     else if (!NOTE_P (insn)
1168              && INSN_UID (insn) < old_max_uid
1169              && (note = LINE_NOTE (insn)) != 0
1170              && note != line
1171              && (line == 0
1172 #ifdef USE_MAPPED_LOCATION
1173                  || NOTE_SOURCE_LOCATION (note) != NOTE_SOURCE_LOCATION (line)
1174 #else
1175                  || NOTE_LINE_NUMBER (note) != NOTE_LINE_NUMBER (line)
1176                  || NOTE_SOURCE_FILE (note) != NOTE_SOURCE_FILE (line)
1177 #endif
1178                  ))
1179       {
1180         line = note;
1181         prev = PREV_INSN (insn);
1182         if (LINE_NOTE (note))
1183           {
1184             /* Re-use the original line-number note.  */
1185             LINE_NOTE (note) = 0;
1186             PREV_INSN (note) = prev;
1187             NEXT_INSN (prev) = note;
1188             PREV_INSN (insn) = note;
1189             NEXT_INSN (note) = insn;
1190           }
1191         else
1192           {
1193             added_notes++;
1194             new = emit_note_after (NOTE_LINE_NUMBER (note), prev);
1195 #ifndef USE_MAPPED_LOCATION
1196             NOTE_SOURCE_FILE (new) = NOTE_SOURCE_FILE (note);
1197 #endif
1198           }
1199       }
1200   if (sched_verbose && added_notes)
1201     fprintf (sched_dump, ";; added %d line-number notes\n", added_notes);
1202 }
1203
1204 /* After scheduling the function, delete redundant line notes from the
1205    insns list.  */
1206
1207 void
1208 rm_redundant_line_notes (void)
1209 {
1210   rtx line = 0;
1211   rtx insn = get_insns ();
1212   int active_insn = 0;
1213   int notes = 0;
1214
1215   /* Walk the insns deleting redundant line-number notes.  Many of these
1216      are already present.  The remainder tend to occur at basic
1217      block boundaries.  */
1218   for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
1219     if (NOTE_P (insn) && NOTE_LINE_NUMBER (insn) > 0)
1220       {
1221         /* If there are no active insns following, INSN is redundant.  */
1222         if (active_insn == 0)
1223           {
1224             notes++;
1225             SET_INSN_DELETED (insn);
1226           }
1227         /* If the line number is unchanged, LINE is redundant.  */
1228         else if (line
1229 #ifdef USE_MAPPED_LOCATION
1230                  && NOTE_SOURCE_LOCATION (line) == NOTE_SOURCE_LOCATION (insn)
1231 #else
1232                  && NOTE_LINE_NUMBER (line) == NOTE_LINE_NUMBER (insn)
1233                  && NOTE_SOURCE_FILE (line) == NOTE_SOURCE_FILE (insn)
1234 #endif
1235 )
1236           {
1237             notes++;
1238             SET_INSN_DELETED (line);
1239             line = insn;
1240           }
1241         else
1242           line = insn;
1243         active_insn = 0;
1244       }
1245     else if (!((NOTE_P (insn)
1246                 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED)
1247                || (NONJUMP_INSN_P (insn)
1248                    && (GET_CODE (PATTERN (insn)) == USE
1249                        || GET_CODE (PATTERN (insn)) == CLOBBER))))
1250       active_insn++;
1251
1252   if (sched_verbose && notes)
1253     fprintf (sched_dump, ";; deleted %d line-number notes\n", notes);
1254 }
1255
1256 /* Delete notes between HEAD and TAIL and put them in the chain
1257    of notes ended by NOTE_LIST.  */
1258
1259 void
1260 rm_other_notes (rtx head, rtx tail)
1261 {
1262   rtx next_tail;
1263   rtx insn;
1264
1265   note_list = 0;
1266   if (head == tail && (! INSN_P (head)))
1267     return;
1268
1269   next_tail = NEXT_INSN (tail);
1270   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
1271     {
1272       rtx prev;
1273
1274       /* Farm out notes, and maybe save them in NOTE_LIST.
1275          This is needed to keep the debugger from
1276          getting completely deranged.  */
1277       if (NOTE_P (insn))
1278         {
1279           prev = insn;
1280
1281           insn = unlink_other_notes (insn, next_tail);
1282
1283           gcc_assert (prev != tail && prev != head && insn != next_tail);
1284         }
1285     }
1286 }
1287
1288 /* Functions for computation of registers live/usage info.  */
1289
1290 /* This function looks for a new register being defined.
1291    If the destination register is already used by the source,
1292    a new register is not needed.  */
1293
1294 static int
1295 find_set_reg_weight (rtx x)
1296 {
1297   if (GET_CODE (x) == CLOBBER
1298       && register_operand (SET_DEST (x), VOIDmode))
1299     return 1;
1300   if (GET_CODE (x) == SET
1301       && register_operand (SET_DEST (x), VOIDmode))
1302     {
1303       if (REG_P (SET_DEST (x)))
1304         {
1305           if (!reg_mentioned_p (SET_DEST (x), SET_SRC (x)))
1306             return 1;
1307           else
1308             return 0;
1309         }
1310       return 1;
1311     }
1312   return 0;
1313 }
1314
1315 /* Calculate INSN_REG_WEIGHT for all insns of a block.  */
1316
1317 static void
1318 find_insn_reg_weight (int b)
1319 {
1320   rtx insn, next_tail, head, tail;
1321
1322   get_block_head_tail (b, &head, &tail);
1323   next_tail = NEXT_INSN (tail);
1324
1325   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
1326     {
1327       int reg_weight = 0;
1328       rtx x;
1329
1330       /* Handle register life information.  */
1331       if (! INSN_P (insn))
1332         continue;
1333
1334       /* Increment weight for each register born here.  */
1335       x = PATTERN (insn);
1336       reg_weight += find_set_reg_weight (x);
1337       if (GET_CODE (x) == PARALLEL)
1338         {
1339           int j;
1340           for (j = XVECLEN (x, 0) - 1; j >= 0; j--)
1341             {
1342               x = XVECEXP (PATTERN (insn), 0, j);
1343               reg_weight += find_set_reg_weight (x);
1344             }
1345         }
1346       /* Decrement weight for each register that dies here.  */
1347       for (x = REG_NOTES (insn); x; x = XEXP (x, 1))
1348         {
1349           if (REG_NOTE_KIND (x) == REG_DEAD
1350               || REG_NOTE_KIND (x) == REG_UNUSED)
1351             reg_weight--;
1352         }
1353
1354       INSN_REG_WEIGHT (insn) = reg_weight;
1355     }
1356 }
1357
1358 /* Scheduling clock, modified in schedule_block() and queue_to_ready ().  */
1359 static int clock_var;
1360
1361 /* Move insns that became ready to fire from queue to ready list.  */
1362
1363 static void
1364 queue_to_ready (struct ready_list *ready)
1365 {
1366   rtx insn;
1367   rtx link;
1368
1369   q_ptr = NEXT_Q (q_ptr);
1370
1371   /* Add all pending insns that can be scheduled without stalls to the
1372      ready list.  */
1373   for (link = insn_queue[q_ptr]; link; link = XEXP (link, 1))
1374     {
1375       insn = XEXP (link, 0);
1376       q_size -= 1;
1377
1378       if (sched_verbose >= 2)
1379         fprintf (sched_dump, ";;\t\tQ-->Ready: insn %s: ",
1380                  (*current_sched_info->print_insn) (insn, 0));
1381
1382       ready_add (ready, insn);
1383       if (sched_verbose >= 2)
1384         fprintf (sched_dump, "moving to ready without stalls\n");
1385     }
1386   insn_queue[q_ptr] = 0;
1387
1388   /* If there are no ready insns, stall until one is ready and add all
1389      of the pending insns at that point to the ready list.  */
1390   if (ready->n_ready == 0)
1391     {
1392       int stalls;
1393
1394       for (stalls = 1; stalls <= max_insn_queue_index; stalls++)
1395         {
1396           if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
1397             {
1398               for (; link; link = XEXP (link, 1))
1399                 {
1400                   insn = XEXP (link, 0);
1401                   q_size -= 1;
1402
1403                   if (sched_verbose >= 2)
1404                     fprintf (sched_dump, ";;\t\tQ-->Ready: insn %s: ",
1405                              (*current_sched_info->print_insn) (insn, 0));
1406
1407                   ready_add (ready, insn);
1408                   if (sched_verbose >= 2)
1409                     fprintf (sched_dump, "moving to ready with %d stalls\n", stalls);
1410                 }
1411               insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = 0;
1412
1413               advance_one_cycle ();
1414
1415               break;
1416             }
1417
1418           advance_one_cycle ();
1419         }
1420
1421       q_ptr = NEXT_Q_AFTER (q_ptr, stalls);
1422       clock_var += stalls;
1423     }
1424 }
1425
1426 /* Used by early_queue_to_ready.  Determines whether it is "ok" to
1427    prematurely move INSN from the queue to the ready list.  Currently,
1428    if a target defines the hook 'is_costly_dependence', this function
1429    uses the hook to check whether there exist any dependences which are
1430    considered costly by the target, between INSN and other insns that
1431    have already been scheduled.  Dependences are checked up to Y cycles
1432    back, with default Y=1; The flag -fsched-stalled-insns-dep=Y allows
1433    controlling this value.
1434    (Other considerations could be taken into account instead (or in
1435    addition) depending on user flags and target hooks.  */
1436
1437 static bool
1438 ok_for_early_queue_removal (rtx insn)
1439 {
1440   int n_cycles;
1441   rtx prev_insn = last_scheduled_insn;
1442
1443   if (targetm.sched.is_costly_dependence)
1444     {
1445       for (n_cycles = flag_sched_stalled_insns_dep; n_cycles; n_cycles--)
1446         {
1447           for ( ; prev_insn; prev_insn = PREV_INSN (prev_insn))
1448             {
1449               rtx dep_link = 0;
1450               int dep_cost;
1451
1452               if (!NOTE_P (prev_insn))
1453                 {
1454                   dep_link = find_insn_list (insn, INSN_DEPEND (prev_insn));
1455                   if (dep_link)
1456                     {
1457                       dep_cost = insn_cost (prev_insn, dep_link, insn) ;
1458                       if (targetm.sched.is_costly_dependence (prev_insn, insn,
1459                                 dep_link, dep_cost,
1460                                 flag_sched_stalled_insns_dep - n_cycles))
1461                         return false;
1462                     }
1463                 }
1464
1465               if (GET_MODE (prev_insn) == TImode) /* end of dispatch group */
1466                 break;
1467             }
1468
1469           if (!prev_insn)
1470             break;
1471           prev_insn = PREV_INSN (prev_insn);
1472         }
1473     }
1474
1475   return true;
1476 }
1477
1478
1479 /* Remove insns from the queue, before they become "ready" with respect
1480    to FU latency considerations.  */
1481
1482 static int
1483 early_queue_to_ready (state_t state, struct ready_list *ready)
1484 {
1485   rtx insn;
1486   rtx link;
1487   rtx next_link;
1488   rtx prev_link;
1489   bool move_to_ready;
1490   int cost;
1491   state_t temp_state = alloca (dfa_state_size);
1492   int stalls;
1493   int insns_removed = 0;
1494
1495   /*
1496      Flag '-fsched-stalled-insns=X' determines the aggressiveness of this
1497      function:
1498
1499      X == 0: There is no limit on how many queued insns can be removed
1500              prematurely.  (flag_sched_stalled_insns = -1).
1501
1502      X >= 1: Only X queued insns can be removed prematurely in each
1503              invocation.  (flag_sched_stalled_insns = X).
1504
1505      Otherwise: Early queue removal is disabled.
1506          (flag_sched_stalled_insns = 0)
1507   */
1508
1509   if (! flag_sched_stalled_insns)
1510     return 0;
1511
1512   for (stalls = 0; stalls <= max_insn_queue_index; stalls++)
1513     {
1514       if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
1515         {
1516           if (sched_verbose > 6)
1517             fprintf (sched_dump, ";; look at index %d + %d\n", q_ptr, stalls);
1518
1519           prev_link = 0;
1520           while (link)
1521             {
1522               next_link = XEXP (link, 1);
1523               insn = XEXP (link, 0);
1524               if (insn && sched_verbose > 6)
1525                 print_rtl_single (sched_dump, insn);
1526
1527               memcpy (temp_state, state, dfa_state_size);
1528               if (recog_memoized (insn) < 0)
1529                 /* non-negative to indicate that it's not ready
1530                    to avoid infinite Q->R->Q->R... */
1531                 cost = 0;
1532               else
1533                 cost = state_transition (temp_state, insn);
1534
1535               if (sched_verbose >= 6)
1536                 fprintf (sched_dump, "transition cost = %d\n", cost);
1537
1538               move_to_ready = false;
1539               if (cost < 0)
1540                 {
1541                   move_to_ready = ok_for_early_queue_removal (insn);
1542                   if (move_to_ready == true)
1543                     {
1544                       /* move from Q to R */
1545                       q_size -= 1;
1546                       ready_add (ready, insn);
1547
1548                       if (prev_link)
1549                         XEXP (prev_link, 1) = next_link;
1550                       else
1551                         insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = next_link;
1552
1553                       free_INSN_LIST_node (link);
1554
1555                       if (sched_verbose >= 2)
1556                         fprintf (sched_dump, ";;\t\tEarly Q-->Ready: insn %s\n",
1557                                  (*current_sched_info->print_insn) (insn, 0));
1558
1559                       insns_removed++;
1560                       if (insns_removed == flag_sched_stalled_insns)
1561                         /* Remove only one insn from Q at a time.  */
1562                         return insns_removed;
1563                     }
1564                 }
1565
1566               if (move_to_ready == false)
1567                 prev_link = link;
1568
1569               link = next_link;
1570             } /* while link */
1571         } /* if link */
1572
1573     } /* for stalls.. */
1574
1575   return insns_removed;
1576 }
1577
1578
1579 /* Print the ready list for debugging purposes.  Callable from debugger.  */
1580
1581 static void
1582 debug_ready_list (struct ready_list *ready)
1583 {
1584   rtx *p;
1585   int i;
1586
1587   if (ready->n_ready == 0)
1588     {
1589       fprintf (sched_dump, "\n");
1590       return;
1591     }
1592
1593   p = ready_lastpos (ready);
1594   for (i = 0; i < ready->n_ready; i++)
1595     fprintf (sched_dump, "  %s", (*current_sched_info->print_insn) (p[i], 0));
1596   fprintf (sched_dump, "\n");
1597 }
1598
1599 /* move_insn1: Remove INSN from insn chain, and link it after LAST insn.  */
1600
1601 static rtx
1602 move_insn1 (rtx insn, rtx last)
1603 {
1604   NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
1605   PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
1606
1607   NEXT_INSN (insn) = NEXT_INSN (last);
1608   PREV_INSN (NEXT_INSN (last)) = insn;
1609
1610   NEXT_INSN (last) = insn;
1611   PREV_INSN (insn) = last;
1612
1613   return insn;
1614 }
1615
1616 /* Search INSN for REG_SAVE_NOTE note pairs for
1617    NOTE_INSN_{LOOP,EHREGION}_{BEG,END}; and convert them back into
1618    NOTEs.  The REG_SAVE_NOTE note following first one is contains the
1619    saved value for NOTE_BLOCK_NUMBER which is useful for
1620    NOTE_INSN_EH_REGION_{BEG,END} NOTEs.  LAST is the last instruction
1621    output by the instruction scheduler.  Return the new value of LAST.  */
1622
1623 static rtx
1624 reemit_notes (rtx insn, rtx last)
1625 {
1626   rtx note, retval;
1627
1628   retval = last;
1629   for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1630     {
1631       if (REG_NOTE_KIND (note) == REG_SAVE_NOTE)
1632         {
1633           enum insn_note note_type = INTVAL (XEXP (note, 0));
1634
1635           last = emit_note_before (note_type, last);
1636           remove_note (insn, note);
1637         }
1638     }
1639   return retval;
1640 }
1641
1642 /* Move INSN.  Reemit notes if needed.
1643
1644    Return the last insn emitted by the scheduler, which is the
1645    return value from the first call to reemit_notes.  */
1646
1647 static rtx
1648 move_insn (rtx insn, rtx last)
1649 {
1650   rtx retval = NULL;
1651
1652   move_insn1 (insn, last);
1653
1654   /* If this is the first call to reemit_notes, then record
1655      its return value.  */
1656   if (retval == NULL_RTX)
1657     retval = reemit_notes (insn, insn);
1658   else
1659     reemit_notes (insn, insn);
1660
1661   SCHED_GROUP_P (insn) = 0;
1662
1663   return retval;
1664 }
1665
1666 /* The following structure describe an entry of the stack of choices.  */
1667 struct choice_entry
1668 {
1669   /* Ordinal number of the issued insn in the ready queue.  */
1670   int index;
1671   /* The number of the rest insns whose issues we should try.  */
1672   int rest;
1673   /* The number of issued essential insns.  */
1674   int n;
1675   /* State after issuing the insn.  */
1676   state_t state;
1677 };
1678
1679 /* The following array is used to implement a stack of choices used in
1680    function max_issue.  */
1681 static struct choice_entry *choice_stack;
1682
1683 /* The following variable value is number of essential insns issued on
1684    the current cycle.  An insn is essential one if it changes the
1685    processors state.  */
1686 static int cycle_issued_insns;
1687
1688 /* The following variable value is maximal number of tries of issuing
1689    insns for the first cycle multipass insn scheduling.  We define
1690    this value as constant*(DFA_LOOKAHEAD**ISSUE_RATE).  We would not
1691    need this constraint if all real insns (with non-negative codes)
1692    had reservations because in this case the algorithm complexity is
1693    O(DFA_LOOKAHEAD**ISSUE_RATE).  Unfortunately, the dfa descriptions
1694    might be incomplete and such insn might occur.  For such
1695    descriptions, the complexity of algorithm (without the constraint)
1696    could achieve DFA_LOOKAHEAD ** N , where N is the queue length.  */
1697 static int max_lookahead_tries;
1698
1699 /* The following value is value of hook
1700    `first_cycle_multipass_dfa_lookahead' at the last call of
1701    `max_issue'.  */
1702 static int cached_first_cycle_multipass_dfa_lookahead = 0;
1703
1704 /* The following value is value of `issue_rate' at the last call of
1705    `sched_init'.  */
1706 static int cached_issue_rate = 0;
1707
1708 /* The following function returns maximal (or close to maximal) number
1709    of insns which can be issued on the same cycle and one of which
1710    insns is insns with the best rank (the first insn in READY).  To
1711    make this function tries different samples of ready insns.  READY
1712    is current queue `ready'.  Global array READY_TRY reflects what
1713    insns are already issued in this try.  INDEX will contain index
1714    of the best insn in READY.  The following function is used only for
1715    first cycle multipass scheduling.  */
1716 static int
1717 max_issue (struct ready_list *ready, int *index)
1718 {
1719   int n, i, all, n_ready, best, delay, tries_num;
1720   struct choice_entry *top;
1721   rtx insn;
1722
1723   best = 0;
1724   memcpy (choice_stack->state, curr_state, dfa_state_size);
1725   top = choice_stack;
1726   top->rest = cached_first_cycle_multipass_dfa_lookahead;
1727   top->n = 0;
1728   n_ready = ready->n_ready;
1729   for (all = i = 0; i < n_ready; i++)
1730     if (!ready_try [i])
1731       all++;
1732   i = 0;
1733   tries_num = 0;
1734   for (;;)
1735     {
1736       if (top->rest == 0 || i >= n_ready)
1737         {
1738           if (top == choice_stack)
1739             break;
1740           if (best < top - choice_stack && ready_try [0])
1741             {
1742               best = top - choice_stack;
1743               *index = choice_stack [1].index;
1744               if (top->n == issue_rate - cycle_issued_insns || best == all)
1745                 break;
1746             }
1747           i = top->index;
1748           ready_try [i] = 0;
1749           top--;
1750           memcpy (curr_state, top->state, dfa_state_size);
1751         }
1752       else if (!ready_try [i])
1753         {
1754           tries_num++;
1755           if (tries_num > max_lookahead_tries)
1756             break;
1757           insn = ready_element (ready, i);
1758           delay = state_transition (curr_state, insn);
1759           if (delay < 0)
1760             {
1761               if (state_dead_lock_p (curr_state))
1762                 top->rest = 0;
1763               else
1764                 top->rest--;
1765               n = top->n;
1766               if (memcmp (top->state, curr_state, dfa_state_size) != 0)
1767                 n++;
1768               top++;
1769               top->rest = cached_first_cycle_multipass_dfa_lookahead;
1770               top->index = i;
1771               top->n = n;
1772               memcpy (top->state, curr_state, dfa_state_size);
1773               ready_try [i] = 1;
1774               i = -1;
1775             }
1776         }
1777       i++;
1778     }
1779   while (top != choice_stack)
1780     {
1781       ready_try [top->index] = 0;
1782       top--;
1783     }
1784   memcpy (curr_state, choice_stack->state, dfa_state_size);
1785   return best;
1786 }
1787
1788 /* The following function chooses insn from READY and modifies
1789    *N_READY and READY.  The following function is used only for first
1790    cycle multipass scheduling.  */
1791
1792 static rtx
1793 choose_ready (struct ready_list *ready)
1794 {
1795   int lookahead = 0;
1796
1797   if (targetm.sched.first_cycle_multipass_dfa_lookahead)
1798     lookahead = targetm.sched.first_cycle_multipass_dfa_lookahead ();
1799   if (lookahead <= 0 || SCHED_GROUP_P (ready_element (ready, 0)))
1800     return ready_remove_first (ready);
1801   else
1802     {
1803       /* Try to choose the better insn.  */
1804       int index = 0, i;
1805       rtx insn;
1806
1807       if (cached_first_cycle_multipass_dfa_lookahead != lookahead)
1808         {
1809           cached_first_cycle_multipass_dfa_lookahead = lookahead;
1810           max_lookahead_tries = 100;
1811           for (i = 0; i < issue_rate; i++)
1812             max_lookahead_tries *= lookahead;
1813         }
1814       insn = ready_element (ready, 0);
1815       if (INSN_CODE (insn) < 0)
1816         return ready_remove_first (ready);
1817       for (i = 1; i < ready->n_ready; i++)
1818         {
1819           insn = ready_element (ready, i);
1820           ready_try [i]
1821             = (INSN_CODE (insn) < 0
1822                || (targetm.sched.first_cycle_multipass_dfa_lookahead_guard
1823                    && !targetm.sched.first_cycle_multipass_dfa_lookahead_guard (insn)));
1824         }
1825       if (max_issue (ready, &index) == 0)
1826         return ready_remove_first (ready);
1827       else
1828         return ready_remove (ready, index);
1829     }
1830 }
1831
1832 /* Use forward list scheduling to rearrange insns of block B in region RGN,
1833    possibly bringing insns from subsequent blocks in the same region.  */
1834
1835 void
1836 schedule_block (int b, int rgn_n_insns)
1837 {
1838   struct ready_list ready;
1839   int i, first_cycle_insn_p;
1840   int can_issue_more;
1841   state_t temp_state = NULL;  /* It is used for multipass scheduling.  */
1842   int sort_p, advance, start_clock_var;
1843
1844   /* Head/tail info for this block.  */
1845   rtx prev_head = current_sched_info->prev_head;
1846   rtx next_tail = current_sched_info->next_tail;
1847   rtx head = NEXT_INSN (prev_head);
1848   rtx tail = PREV_INSN (next_tail);
1849
1850   /* We used to have code to avoid getting parameters moved from hard
1851      argument registers into pseudos.
1852
1853      However, it was removed when it proved to be of marginal benefit
1854      and caused problems because schedule_block and compute_forward_dependences
1855      had different notions of what the "head" insn was.  */
1856
1857   gcc_assert (head != tail || INSN_P (head));
1858
1859   /* Debug info.  */
1860   if (sched_verbose)
1861     {
1862       fprintf (sched_dump,
1863                ";;   ======================================================\n");
1864       fprintf (sched_dump,
1865                ";;   -- basic block %d from %d to %d -- %s reload\n",
1866                b, INSN_UID (head), INSN_UID (tail),
1867                (reload_completed ? "after" : "before"));
1868       fprintf (sched_dump,
1869                ";;   ======================================================\n");
1870       fprintf (sched_dump, "\n");
1871     }
1872
1873   state_reset (curr_state);
1874
1875   /* Allocate the ready list.  */
1876   ready.veclen = rgn_n_insns + 1 + issue_rate;
1877   ready.first = ready.veclen - 1;
1878   ready.vec = xmalloc (ready.veclen * sizeof (rtx));
1879   ready.n_ready = 0;
1880
1881   /* It is used for first cycle multipass scheduling.  */
1882   temp_state = alloca (dfa_state_size);
1883   ready_try = xcalloc ((rgn_n_insns + 1), sizeof (char));
1884   choice_stack = xmalloc ((rgn_n_insns + 1)
1885                           * sizeof (struct choice_entry));
1886   for (i = 0; i <= rgn_n_insns; i++)
1887     choice_stack[i].state = xmalloc (dfa_state_size);
1888
1889   (*current_sched_info->init_ready_list) (&ready);
1890
1891   if (targetm.sched.md_init)
1892     targetm.sched.md_init (sched_dump, sched_verbose, ready.veclen);
1893
1894   /* We start inserting insns after PREV_HEAD.  */
1895   last_scheduled_insn = prev_head;
1896
1897   /* Initialize INSN_QUEUE.  Q_SIZE is the total number of insns in the
1898      queue.  */
1899   q_ptr = 0;
1900   q_size = 0;
1901
1902   insn_queue = alloca ((max_insn_queue_index + 1) * sizeof (rtx));
1903   memset (insn_queue, 0, (max_insn_queue_index + 1) * sizeof (rtx));
1904   last_clock_var = -1;
1905
1906   /* Start just before the beginning of time.  */
1907   clock_var = -1;
1908   advance = 0;
1909
1910   sort_p = TRUE;
1911   /* Loop until all the insns in BB are scheduled.  */
1912   while ((*current_sched_info->schedule_more_p) ())
1913     {
1914       do
1915         {
1916           start_clock_var = clock_var;
1917
1918           clock_var++;
1919
1920           advance_one_cycle ();
1921
1922           /* Add to the ready list all pending insns that can be issued now.
1923              If there are no ready insns, increment clock until one
1924              is ready and add all pending insns at that point to the ready
1925              list.  */
1926           queue_to_ready (&ready);
1927
1928           gcc_assert (ready.n_ready);
1929
1930           if (sched_verbose >= 2)
1931             {
1932               fprintf (sched_dump, ";;\t\tReady list after queue_to_ready:  ");
1933               debug_ready_list (&ready);
1934             }
1935           advance -= clock_var - start_clock_var;
1936         }
1937       while (advance > 0);
1938
1939       if (sort_p)
1940         {
1941           /* Sort the ready list based on priority.  */
1942           ready_sort (&ready);
1943
1944           if (sched_verbose >= 2)
1945             {
1946               fprintf (sched_dump, ";;\t\tReady list after ready_sort:  ");
1947               debug_ready_list (&ready);
1948             }
1949         }
1950
1951       /* Allow the target to reorder the list, typically for
1952          better instruction bundling.  */
1953       if (sort_p && targetm.sched.reorder
1954           && (ready.n_ready == 0
1955               || !SCHED_GROUP_P (ready_element (&ready, 0))))
1956         can_issue_more =
1957           targetm.sched.reorder (sched_dump, sched_verbose,
1958                                  ready_lastpos (&ready),
1959                                  &ready.n_ready, clock_var);
1960       else
1961         can_issue_more = issue_rate;
1962
1963       first_cycle_insn_p = 1;
1964       cycle_issued_insns = 0;
1965       for (;;)
1966         {
1967           rtx insn;
1968           int cost;
1969           bool asm_p = false;
1970
1971           if (sched_verbose >= 2)
1972             {
1973               fprintf (sched_dump, ";;\tReady list (t =%3d):  ",
1974                        clock_var);
1975               debug_ready_list (&ready);
1976             }
1977
1978           if (ready.n_ready == 0
1979               && can_issue_more
1980               && reload_completed)
1981             {
1982               /* Allow scheduling insns directly from the queue in case
1983                  there's nothing better to do (ready list is empty) but
1984                  there are still vacant dispatch slots in the current cycle.  */
1985               if (sched_verbose >= 6)
1986                 fprintf(sched_dump,";;\t\tSecond chance\n");
1987               memcpy (temp_state, curr_state, dfa_state_size);
1988               if (early_queue_to_ready (temp_state, &ready))
1989                 ready_sort (&ready);
1990             }
1991
1992           if (ready.n_ready == 0 || !can_issue_more
1993               || state_dead_lock_p (curr_state)
1994               || !(*current_sched_info->schedule_more_p) ())
1995             break;
1996
1997           /* Select and remove the insn from the ready list.  */
1998           if (sort_p)
1999             insn = choose_ready (&ready);
2000           else
2001             insn = ready_remove_first (&ready);
2002
2003           if (targetm.sched.dfa_new_cycle
2004               && targetm.sched.dfa_new_cycle (sched_dump, sched_verbose,
2005                                               insn, last_clock_var,
2006                                               clock_var, &sort_p))
2007             {
2008               ready_add (&ready, insn);
2009               break;
2010             }
2011
2012           sort_p = TRUE;
2013           memcpy (temp_state, curr_state, dfa_state_size);
2014           if (recog_memoized (insn) < 0)
2015             {
2016               asm_p = (GET_CODE (PATTERN (insn)) == ASM_INPUT
2017                        || asm_noperands (PATTERN (insn)) >= 0);
2018               if (!first_cycle_insn_p && asm_p)
2019                 /* This is asm insn which is tryed to be issued on the
2020                    cycle not first.  Issue it on the next cycle.  */
2021                 cost = 1;
2022               else
2023                 /* A USE insn, or something else we don't need to
2024                    understand.  We can't pass these directly to
2025                    state_transition because it will trigger a
2026                    fatal error for unrecognizable insns.  */
2027                 cost = 0;
2028             }
2029           else
2030             {
2031               cost = state_transition (temp_state, insn);
2032               if (cost < 0)
2033                 cost = 0;
2034               else if (cost == 0)
2035                 cost = 1;
2036             }
2037
2038           if (cost >= 1)
2039             {
2040               queue_insn (insn, cost);
2041               if (SCHED_GROUP_P (insn))
2042                 {
2043                   advance = cost;
2044                   break;
2045                 }
2046
2047               continue;
2048             }
2049
2050           if (! (*current_sched_info->can_schedule_ready_p) (insn))
2051             goto next;
2052
2053           last_scheduled_insn = move_insn (insn, last_scheduled_insn);
2054
2055           if (memcmp (curr_state, temp_state, dfa_state_size) != 0)
2056             cycle_issued_insns++;
2057           memcpy (curr_state, temp_state, dfa_state_size);
2058
2059           if (targetm.sched.variable_issue)
2060             can_issue_more =
2061               targetm.sched.variable_issue (sched_dump, sched_verbose,
2062                                                insn, can_issue_more);
2063           /* A naked CLOBBER or USE generates no instruction, so do
2064              not count them against the issue rate.  */
2065           else if (GET_CODE (PATTERN (insn)) != USE
2066                    && GET_CODE (PATTERN (insn)) != CLOBBER)
2067             can_issue_more--;
2068
2069           advance = schedule_insn (insn, &ready, clock_var);
2070
2071           /* After issuing an asm insn we should start a new cycle.  */
2072           if (advance == 0 && asm_p)
2073             advance = 1;
2074           if (advance != 0)
2075             break;
2076
2077         next:
2078           first_cycle_insn_p = 0;
2079
2080           /* Sort the ready list based on priority.  This must be
2081              redone here, as schedule_insn may have readied additional
2082              insns that will not be sorted correctly.  */
2083           if (ready.n_ready > 0)
2084             ready_sort (&ready);
2085
2086           if (targetm.sched.reorder2
2087               && (ready.n_ready == 0
2088                   || !SCHED_GROUP_P (ready_element (&ready, 0))))
2089             {
2090               can_issue_more =
2091                 targetm.sched.reorder2 (sched_dump, sched_verbose,
2092                                         ready.n_ready
2093                                         ? ready_lastpos (&ready) : NULL,
2094                                         &ready.n_ready, clock_var);
2095             }
2096         }
2097     }
2098
2099   if (targetm.sched.md_finish)
2100     targetm.sched.md_finish (sched_dump, sched_verbose);
2101
2102   /* Debug info.  */
2103   if (sched_verbose)
2104     {
2105       fprintf (sched_dump, ";;\tReady list (final):  ");
2106       debug_ready_list (&ready);
2107     }
2108
2109   /* Sanity check -- queue must be empty now.  Meaningless if region has
2110      multiple bbs.  */
2111   gcc_assert (!current_sched_info->queue_must_finish_empty || !q_size);
2112
2113   /* Update head/tail boundaries.  */
2114   head = NEXT_INSN (prev_head);
2115   tail = last_scheduled_insn;
2116
2117   if (!reload_completed)
2118     {
2119       rtx insn, link, next;
2120
2121       /* INSN_TICK (minimum clock tick at which the insn becomes
2122          ready) may be not correct for the insn in the subsequent
2123          blocks of the region.  We should use a correct value of
2124          `clock_var' or modify INSN_TICK.  It is better to keep
2125          clock_var value equal to 0 at the start of a basic block.
2126          Therefore we modify INSN_TICK here.  */
2127       for (insn = head; insn != tail; insn = NEXT_INSN (insn))
2128         if (INSN_P (insn))
2129           {
2130             for (link = INSN_DEPEND (insn); link != 0; link = XEXP (link, 1))
2131               {
2132                 next = XEXP (link, 0);
2133                 INSN_TICK (next) -= clock_var;
2134               }
2135           }
2136     }
2137
2138   /* Restore-other-notes: NOTE_LIST is the end of a chain of notes
2139      previously found among the insns.  Insert them at the beginning
2140      of the insns.  */
2141   if (note_list != 0)
2142     {
2143       rtx note_head = note_list;
2144
2145       while (PREV_INSN (note_head))
2146         {
2147           note_head = PREV_INSN (note_head);
2148         }
2149
2150       PREV_INSN (note_head) = PREV_INSN (head);
2151       NEXT_INSN (PREV_INSN (head)) = note_head;
2152       PREV_INSN (head) = note_list;
2153       NEXT_INSN (note_list) = head;
2154       head = note_head;
2155     }
2156
2157   /* Debugging.  */
2158   if (sched_verbose)
2159     {
2160       fprintf (sched_dump, ";;   total time = %d\n;;   new head = %d\n",
2161                clock_var, INSN_UID (head));
2162       fprintf (sched_dump, ";;   new tail = %d\n\n",
2163                INSN_UID (tail));
2164     }
2165
2166   current_sched_info->head = head;
2167   current_sched_info->tail = tail;
2168
2169   free (ready.vec);
2170
2171   free (ready_try);
2172   for (i = 0; i <= rgn_n_insns; i++)
2173     free (choice_stack [i].state);
2174   free (choice_stack);
2175 }
2176 \f
2177 /* Set_priorities: compute priority of each insn in the block.  */
2178
2179 int
2180 set_priorities (rtx head, rtx tail)
2181 {
2182   rtx insn;
2183   int n_insn;
2184   int sched_max_insns_priority =
2185         current_sched_info->sched_max_insns_priority;
2186   rtx prev_head;
2187
2188   prev_head = PREV_INSN (head);
2189
2190   if (head == tail && (! INSN_P (head)))
2191     return 0;
2192
2193   n_insn = 0;
2194   sched_max_insns_priority = 0;
2195   for (insn = tail; insn != prev_head; insn = PREV_INSN (insn))
2196     {
2197       if (NOTE_P (insn))
2198         continue;
2199
2200       n_insn++;
2201       (void) priority (insn);
2202
2203       if (INSN_PRIORITY_KNOWN (insn))
2204         sched_max_insns_priority =
2205           MAX (sched_max_insns_priority, INSN_PRIORITY (insn));
2206     }
2207   sched_max_insns_priority += 1;
2208   current_sched_info->sched_max_insns_priority =
2209         sched_max_insns_priority;
2210
2211   return n_insn;
2212 }
2213
2214 /* Initialize some global state for the scheduler.  DUMP_FILE is to be used
2215    for debugging output.  */
2216
2217 void
2218 sched_init (FILE *dump_file)
2219 {
2220   int luid;
2221   basic_block b;
2222   rtx insn;
2223   int i;
2224
2225   /* Disable speculative loads in their presence if cc0 defined.  */
2226 #ifdef HAVE_cc0
2227   flag_schedule_speculative_load = 0;
2228 #endif
2229
2230   /* Set dump and sched_verbose for the desired debugging output.  If no
2231      dump-file was specified, but -fsched-verbose=N (any N), print to stderr.
2232      For -fsched-verbose=N, N>=10, print everything to stderr.  */
2233   sched_verbose = sched_verbose_param;
2234   if (sched_verbose_param == 0 && dump_file)
2235     sched_verbose = 1;
2236   sched_dump = ((sched_verbose_param >= 10 || !dump_file)
2237                 ? stderr : dump_file);
2238
2239   /* Initialize issue_rate.  */
2240   if (targetm.sched.issue_rate)
2241     issue_rate = targetm.sched.issue_rate ();
2242   else
2243     issue_rate = 1;
2244
2245   if (cached_issue_rate != issue_rate)
2246     {
2247       cached_issue_rate = issue_rate;
2248       /* To invalidate max_lookahead_tries:  */
2249       cached_first_cycle_multipass_dfa_lookahead = 0;
2250     }
2251
2252   /* We use LUID 0 for the fake insn (UID 0) which holds dependencies for
2253      pseudos which do not cross calls.  */
2254   old_max_uid = get_max_uid () + 1;
2255
2256   h_i_d = xcalloc (old_max_uid, sizeof (*h_i_d));
2257
2258   for (i = 0; i < old_max_uid; i++)
2259     h_i_d [i].cost = -1;
2260
2261   if (targetm.sched.init_dfa_pre_cycle_insn)
2262     targetm.sched.init_dfa_pre_cycle_insn ();
2263
2264   if (targetm.sched.init_dfa_post_cycle_insn)
2265     targetm.sched.init_dfa_post_cycle_insn ();
2266
2267   dfa_start ();
2268   dfa_state_size = state_size ();
2269   curr_state = xmalloc (dfa_state_size);
2270
2271   h_i_d[0].luid = 0;
2272   luid = 1;
2273   FOR_EACH_BB (b)
2274     for (insn = BB_HEAD (b); ; insn = NEXT_INSN (insn))
2275       {
2276         INSN_LUID (insn) = luid;
2277
2278         /* Increment the next luid, unless this is a note.  We don't
2279            really need separate IDs for notes and we don't want to
2280            schedule differently depending on whether or not there are
2281            line-number notes, i.e., depending on whether or not we're
2282            generating debugging information.  */
2283         if (!NOTE_P (insn))
2284           ++luid;
2285
2286         if (insn == BB_END (b))
2287           break;
2288       }
2289
2290   init_dependency_caches (luid);
2291
2292   init_alias_analysis ();
2293
2294   if (write_symbols != NO_DEBUG)
2295     {
2296       rtx line;
2297
2298       line_note_head = xcalloc (last_basic_block, sizeof (rtx));
2299
2300       /* Save-line-note-head:
2301          Determine the line-number at the start of each basic block.
2302          This must be computed and saved now, because after a basic block's
2303          predecessor has been scheduled, it is impossible to accurately
2304          determine the correct line number for the first insn of the block.  */
2305
2306       FOR_EACH_BB (b)
2307         {
2308           for (line = BB_HEAD (b); line; line = PREV_INSN (line))
2309             if (NOTE_P (line) && NOTE_LINE_NUMBER (line) > 0)
2310               {
2311                 line_note_head[b->index] = line;
2312                 break;
2313               }
2314           /* Do a forward search as well, since we won't get to see the first
2315              notes in a basic block.  */
2316           for (line = BB_HEAD (b); line; line = NEXT_INSN (line))
2317             {
2318               if (INSN_P (line))
2319                 break;
2320               if (NOTE_P (line) && NOTE_LINE_NUMBER (line) > 0)
2321                 line_note_head[b->index] = line;
2322             }
2323         }
2324     }
2325
2326   /* ??? Add a NOTE after the last insn of the last basic block.  It is not
2327      known why this is done.  */
2328
2329   insn = BB_END (EXIT_BLOCK_PTR->prev_bb);
2330   if (NEXT_INSN (insn) == 0
2331       || (!NOTE_P (insn)
2332           && !LABEL_P (insn)
2333           /* Don't emit a NOTE if it would end up before a BARRIER.  */
2334           && !BARRIER_P (NEXT_INSN (insn))))
2335     {
2336       emit_note_after (NOTE_INSN_DELETED, BB_END (EXIT_BLOCK_PTR->prev_bb));
2337       /* Make insn to appear outside BB.  */
2338       BB_END (EXIT_BLOCK_PTR->prev_bb) = PREV_INSN (BB_END (EXIT_BLOCK_PTR->prev_bb));
2339     }
2340
2341   /* Compute INSN_REG_WEIGHT for all blocks.  We must do this before
2342      removing death notes.  */
2343   FOR_EACH_BB_REVERSE (b)
2344     find_insn_reg_weight (b->index);
2345
2346   if (targetm.sched.md_init_global)
2347       targetm.sched.md_init_global (sched_dump, sched_verbose, old_max_uid);
2348 }
2349
2350 /* Free global data used during insn scheduling.  */
2351
2352 void
2353 sched_finish (void)
2354 {
2355   free (h_i_d);
2356   free (curr_state);
2357   dfa_finish ();
2358   free_dependency_caches ();
2359   end_alias_analysis ();
2360   if (write_symbols != NO_DEBUG)
2361     free (line_note_head);
2362
2363   if (targetm.sched.md_finish_global)
2364       targetm.sched.md_finish_global (sched_dump, sched_verbose);
2365 }
2366 #endif /* INSN_SCHEDULING */