gcc/haifa-sched.c

   1 /* Instruction scheduling pass.
   2    Copyright (C) 1992, 93-98, 1999 Free Software Foundation, Inc.
   3    Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
   4    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 it
   9    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, but
  14    WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16    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 the Free
  20    the Free Software Foundation, 59 Temple Place - Suite 330,
  21    Boston, MA 02111-1307, USA.  */
  22
  23
  24 /* Instruction scheduling pass.
  25
  26    This pass implements list scheduling within basic blocks.  It is
  27    run twice: (1) after flow analysis, but before register allocation,
  28    and (2) after register allocation.
  29
  30    The first run performs interblock scheduling, moving insns between
  31    different blocks in the same "region", and the second runs only
  32    basic block scheduling.
  33
  34    Interblock motions performed are useful motions and speculative
  35    motions, including speculative loads.  Motions requiring code
  36    duplication are not supported.  The identification of motion type
  37    and the check for validity of speculative motions requires
  38    construction and analysis of the function's control flow graph.
  39    The scheduler works as follows:
  40
  41    We compute insn priorities based on data dependencies.  Flow
  42    analysis only creates a fraction of the data-dependencies we must
  43    observe: namely, only those dependencies which the combiner can be
  44    expected to use.  For this pass, we must therefore create the
  45    remaining dependencies we need to observe: register dependencies,
  46    memory dependencies, dependencies to keep function calls in order,
  47    and the dependence between a conditional branch and the setting of
  48    condition codes are all dealt with here.
  49
  50    The scheduler first traverses the data flow graph, starting with
  51    the last instruction, and proceeding to the first, assigning values
  52    to insn_priority as it goes.  This sorts the instructions
  53    topologically by data dependence.
  54
  55    Once priorities have been established, we order the insns using
  56    list scheduling.  This works as follows: starting with a list of
  57    all the ready insns, and sorted according to priority number, we
  58    schedule the insn from the end of the list by placing its
  59    predecessors in the list according to their priority order.  We
  60    consider this insn scheduled by setting the pointer to the "end" of
  61    the list to point to the previous insn.  When an insn has no
  62    predecessors, we either queue it until sufficient time has elapsed
  63    or add it to the ready list.  As the instructions are scheduled or
  64    when stalls are introduced, the queue advances and dumps insns into
  65    the ready list.  When all insns down to the lowest priority have
  66    been scheduled, the critical path of the basic block has been made
  67    as short as possible.  The remaining insns are then scheduled in
  68    remaining slots.
  69
  70    Function unit conflicts are resolved during forward list scheduling
  71    by tracking the time when each insn is committed to the schedule
  72    and from that, the time the function units it uses must be free.
  73    As insns on the ready list are considered for scheduling, those
  74    that would result in a blockage of the already committed insns are
  75    queued until no blockage will result.
  76
  77    The following list shows the order in which we want to break ties
  78    among insns in the ready list:
  79
  80    1.  choose insn with the longest path to end of bb, ties
  81    broken by
  82    2.  choose insn with least contribution to register pressure,
  83    ties broken by
  84    3.  prefer in-block upon interblock motion, ties broken by
  85    4.  prefer useful upon speculative motion, ties broken by
  86    5.  choose insn with largest control flow probability, ties
  87    broken by
  88    6.  choose insn with the least dependences upon the previously
  89    scheduled insn, or finally
  90    7   choose the insn which has the most insns dependent on it.
  91    8.  choose insn with lowest UID.
  92
  93    Memory references complicate matters.  Only if we can be certain
  94    that memory references are not part of the data dependency graph
  95    (via true, anti, or output dependence), can we move operations past
  96    memory references.  To first approximation, reads can be done
  97    independently, while writes introduce dependencies.  Better
  98    approximations will yield fewer dependencies.
  99
 100    Before reload, an extended analysis of interblock data dependences
 101    is required for interblock scheduling.  This is performed in
 102    compute_block_backward_dependences ().
 103
 104    Dependencies set up by memory references are treated in exactly the
 105    same way as other dependencies, by using LOG_LINKS backward
 106    dependences.  LOG_LINKS are translated into INSN_DEPEND forward
 107    dependences for the purpose of forward list scheduling.
 108
 109    Having optimized the critical path, we may have also unduly
 110    extended the lifetimes of some registers.  If an operation requires
 111    that constants be loaded into registers, it is certainly desirable
 112    to load those constants as early as necessary, but no earlier.
 113    I.e., it will not do to load up a bunch of registers at the
 114    beginning of a basic block only to use them at the end, if they
 115    could be loaded later, since this may result in excessive register
 116    utilization.
 117
 118    Note that since branches are never in basic blocks, but only end
 119    basic blocks, this pass will not move branches.  But that is ok,
 120    since we can use GNU's delayed branch scheduling pass to take care
 121    of this case.
 122
 123    Also note that no further optimizations based on algebraic
 124    identities are performed, so this pass would be a good one to
 125    perform instruction splitting, such as breaking up a multiply
 126    instruction into shifts and adds where that is profitable.
 127
 128    Given the memory aliasing analysis that this pass should perform,
 129    it should be possible to remove redundant stores to memory, and to
 130    load values from registers instead of hitting memory.
 131
 132    Before reload, speculative insns are moved only if a 'proof' exists
 133    that no exception will be caused by this, and if no live registers
 134    exist that inhibit the motion (live registers constraints are not
 135    represented by data dependence edges).
 136
 137    This pass must update information that subsequent passes expect to
 138    be correct.  Namely: reg_n_refs, reg_n_sets, reg_n_deaths,
 139    reg_n_calls_crossed, and reg_live_length.  Also, BLOCK_HEAD,
 140    BLOCK_END.
 141
 142    The information in the line number notes is carefully retained by
 143    this pass.  Notes that refer to the starting and ending of
 144    exception regions are also carefully retained by this pass.  All
 145    other NOTE insns are grouped in their same relative order at the
 146    beginning of basic blocks and regions that have been scheduled.
 147
 148    The main entry point for this pass is schedule_insns(), called for
 149    each function.  The work of the scheduler is organized in three
 150    levels: (1) function level: insns are subject to splitting,
 151    control-flow-graph is constructed, regions are computed (after
 152    reload, each region is of one block), (2) region level: control
 153    flow graph attributes required for interblock scheduling are
 154    computed (dominators, reachability, etc.), data dependences and
 155    priorities are computed, and (3) block level: insns in the block
 156    are actually scheduled.  */
 157 \f
 158 #include "config.h"
 159 #include "system.h"
 160 #include "toplev.h"
 161 #include "rtl.h"
 162 #include "tm_p.h"
 163 #include "basic-block.h"
 164 #include "regs.h"
 165 #include "function.h"
 166 #include "hard-reg-set.h"
 167 #include "flags.h"
 168 #include "insn-config.h"
 169 #include "insn-attr.h"
 170 #include "except.h"
 171 #include "toplev.h"
 172 #include "recog.h"
 173
 174 extern char *reg_known_equiv_p;
 175 extern rtx *reg_known_value;
 176
 177 #ifdef INSN_SCHEDULING
 178
 179 /* target_units bitmask has 1 for each unit in the cpu.  It should be
 180    possible to compute this variable from the machine description.
 181    But currently it is computed by examining the insn list.  Since
 182    this is only needed for visualization, it seems an acceptable
 183    solution.  (For understanding the mapping of bits to units, see
 184    definition of function_units[] in "insn-attrtab.c".)  */
 185
 186 static int target_units = 0;
 187
 188 /* issue_rate is the number of insns that can be scheduled in the same
 189    machine cycle.  It can be defined in the config/mach/mach.h file,
 190    otherwise we set it to 1.  */
 191
 192 static int issue_rate;
 193
 194 #ifndef ISSUE_RATE
 195 #define ISSUE_RATE 1
 196 #endif
 197
 198 /* sched-verbose controls the amount of debugging output the
 199    scheduler prints.  It is controlled by -fsched-verbose-N:
 200    N>0 and no -DSR : the output is directed to stderr.
 201    N>=10 will direct the printouts to stderr (regardless of -dSR).
 202    N=1: same as -dSR.
 203    N=2: bb's probabilities, detailed ready list info, unit/insn info.
 204    N=3: rtl at abort point, control-flow, regions info.
 205    N=5: dependences info.  */
 206
 207 #define MAX_RGN_BLOCKS 10
 208 #define MAX_RGN_INSNS 100
 209
 210 static int sched_verbose_param = 0;
 211 static int sched_verbose = 0;
 212
 213 /* nr_inter/spec counts interblock/speculative motion for the function.  */
 214 static int nr_inter, nr_spec;
 215
 216
 217 /* Debugging file.  All printouts are sent to dump, which is always set,
 218    either to stderr, or to the dump listing file (-dRS).  */
 219 static FILE *dump = 0;
 220
 221 /* fix_sched_param() is called from toplev.c upon detection
 222    of the -fsched-***-N options.  */
 223
 224 void
 225 fix_sched_param (param, val)
 226      const char *param, *val;
 227 {
 228   if (!strcmp (param, "verbose"))
 229     sched_verbose_param = atoi (val);
 230   else
 231     warning ("fix_sched_param: unknown param: %s", param);
 232 }
 233
 234
 235 /* Element N is the next insn that sets (hard or pseudo) register
 236    N within the current basic block; or zero, if there is no
 237    such insn.  Needed for new registers which may be introduced
 238    by splitting insns.  */
 239 static rtx *reg_last_uses;
 240 static rtx *reg_last_sets;
 241 static rtx *reg_last_clobbers;
 242 static regset reg_pending_sets;
 243 static regset reg_pending_clobbers;
 244 static int reg_pending_sets_all;
 245
 246 /* Vector indexed by INSN_UID giving the original ordering of the insns.  */
 247 static int *insn_luid;
 248 #define INSN_LUID(INSN) (insn_luid[INSN_UID (INSN)])
 249
 250 /* Vector indexed by INSN_UID giving each instruction a priority.  */
 251 static int *insn_priority;
 252 #define INSN_PRIORITY(INSN) (insn_priority[INSN_UID (INSN)])
 253
 254 static short *insn_costs;
 255 #define INSN_COST(INSN) insn_costs[INSN_UID (INSN)]
 256
 257 /* Vector indexed by INSN_UID giving an encoding of the function units
 258    used.  */
 259 static short *insn_units;
 260 #define INSN_UNIT(INSN) insn_units[INSN_UID (INSN)]
 261
 262 /* Vector indexed by INSN_UID giving each instruction a
 263    register-weight.  This weight is an estimation of the insn
 264    contribution to registers pressure.  */
 265 static int *insn_reg_weight;
 266 #define INSN_REG_WEIGHT(INSN) (insn_reg_weight[INSN_UID (INSN)])
 267
 268 /* Vector indexed by INSN_UID giving list of insns which
 269    depend upon INSN.  Unlike LOG_LINKS, it represents forward dependences.  */
 270 static rtx *insn_depend;
 271 #define INSN_DEPEND(INSN) insn_depend[INSN_UID (INSN)]
 272
 273 /* Vector indexed by INSN_UID. Initialized to the number of incoming
 274    edges in forward dependence graph (= number of LOG_LINKS).  As
 275    scheduling procedes, dependence counts are decreased.  An
 276    instruction moves to the ready list when its counter is zero.  */
 277 static int *insn_dep_count;
 278 #define INSN_DEP_COUNT(INSN) (insn_dep_count[INSN_UID (INSN)])
 279
 280 /* Vector indexed by INSN_UID giving an encoding of the blockage range
 281    function.  The unit and the range are encoded.  */
 282 static unsigned int *insn_blockage;
 283 #define INSN_BLOCKAGE(INSN) insn_blockage[INSN_UID (INSN)]
 284 #define UNIT_BITS 5
 285 #define BLOCKAGE_MASK ((1 << BLOCKAGE_BITS) - 1)
 286 #define ENCODE_BLOCKAGE(U, R)                           \
 287 (((U) << BLOCKAGE_BITS                                  \
 288   | MIN_BLOCKAGE_COST (R)) << BLOCKAGE_BITS             \
 289  | MAX_BLOCKAGE_COST (R))
 290 #define UNIT_BLOCKED(B) ((B) >> (2 * BLOCKAGE_BITS))
 291 #define BLOCKAGE_RANGE(B)                                                \
 292   (((((B) >> BLOCKAGE_BITS) & BLOCKAGE_MASK) << (HOST_BITS_PER_INT / 2)) \
 293    | ((B) & BLOCKAGE_MASK))
 294
 295 /* Encodings of the `<name>_unit_blockage_range' function.  */
 296 #define MIN_BLOCKAGE_COST(R) ((R) >> (HOST_BITS_PER_INT / 2))
 297 #define MAX_BLOCKAGE_COST(R) ((R) & ((1 << (HOST_BITS_PER_INT / 2)) - 1))
 298
 299 #define DONE_PRIORITY   -1
 300 #define MAX_PRIORITY    0x7fffffff
 301 #define TAIL_PRIORITY   0x7ffffffe
 302 #define LAUNCH_PRIORITY 0x7f000001
 303 #define DONE_PRIORITY_P(INSN) (INSN_PRIORITY (INSN) < 0)
 304 #define LOW_PRIORITY_P(INSN) ((INSN_PRIORITY (INSN) & 0x7f000000) == 0)
 305
 306 /* Vector indexed by INSN_UID giving number of insns referring to this
 307    insn.  */
 308 static int *insn_ref_count;
 309 #define INSN_REF_COUNT(INSN) (insn_ref_count[INSN_UID (INSN)])
 310
 311 /* Vector indexed by INSN_UID giving line-number note in effect for each
 312    insn.  For line-number notes, this indicates whether the note may be
 313    reused.  */
 314 static rtx *line_note;
 315 #define LINE_NOTE(INSN) (line_note[INSN_UID (INSN)])
 316
 317 /* Vector indexed by basic block number giving the starting line-number
 318    for each basic block.  */
 319 static rtx *line_note_head;
 320
 321 /* List of important notes we must keep around.  This is a pointer to the
 322    last element in the list.  */
 323 static rtx note_list;
 324
 325 /* Queues, etc.  */
 326
 327 /* An instruction is ready to be scheduled when all insns preceding it
 328    have already been scheduled.  It is important to ensure that all
 329    insns which use its result will not be executed until its result
 330    has been computed.  An insn is maintained in one of four structures:
 331
 332    (P) the "Pending" set of insns which cannot be scheduled until
 333    their dependencies have been satisfied.
 334    (Q) the "Queued" set of insns that can be scheduled when sufficient
 335    time has passed.
 336    (R) the "Ready" list of unscheduled, uncommitted insns.
 337    (S) the "Scheduled" list of insns.
 338
 339    Initially, all insns are either "Pending" or "Ready" depending on
 340    whether their dependencies are satisfied.
 341
 342    Insns move from the "Ready" list to the "Scheduled" list as they
 343    are committed to the schedule.  As this occurs, the insns in the
 344    "Pending" list have their dependencies satisfied and move to either
 345    the "Ready" list or the "Queued" set depending on whether
 346    sufficient time has passed to make them ready.  As time passes,
 347    insns move from the "Queued" set to the "Ready" list.  Insns may
 348    move from the "Ready" list to the "Queued" set if they are blocked
 349    due to a function unit conflict.
 350
 351    The "Pending" list (P) are the insns in the INSN_DEPEND of the unscheduled
 352    insns, i.e., those that are ready, queued, and pending.
 353    The "Queued" set (Q) is implemented by the variable `insn_queue'.
 354    The "Ready" list (R) is implemented by the variables `ready' and
 355    `n_ready'.
 356    The "Scheduled" list (S) is the new insn chain built by this pass.
 357
 358    The transition (R->S) is implemented in the scheduling loop in
 359    `schedule_block' when the best insn to schedule is chosen.
 360    The transition (R->Q) is implemented in `queue_insn' when an
 361    insn is found to have a function unit conflict with the already
 362    committed insns.
 363    The transitions (P->R and P->Q) are implemented in `schedule_insn' as
 364    insns move from the ready list to the scheduled list.
 365    The transition (Q->R) is implemented in 'queue_to_insn' as time
 366    passes or stalls are introduced.  */
 367
 368 /* Implement a circular buffer to delay instructions until sufficient
 369    time has passed.  INSN_QUEUE_SIZE is a power of two larger than
 370    MAX_BLOCKAGE and MAX_READY_COST computed by genattr.c.  This is the
 371    longest time an isnsn may be queued.  */
 372 static rtx insn_queue[INSN_QUEUE_SIZE];
 373 static int q_ptr = 0;
 374 static int q_size = 0;
 375 #define NEXT_Q(X) (((X)+1) & (INSN_QUEUE_SIZE-1))
 376 #define NEXT_Q_AFTER(X, C) (((X)+C) & (INSN_QUEUE_SIZE-1))
 377
 378 /* Vector indexed by INSN_UID giving the minimum clock tick at which
 379    the insn becomes ready.  This is used to note timing constraints for
 380    insns in the pending list.  */
 381 static int *insn_tick;
 382 #define INSN_TICK(INSN) (insn_tick[INSN_UID (INSN)])
 383
 384 /* Forward declarations.  */
 385 static void add_dependence PROTO ((rtx, rtx, enum reg_note));
 386 static void remove_dependence PROTO ((rtx, rtx));
 387 static rtx find_insn_list PROTO ((rtx, rtx));
 388 static int insn_unit PROTO ((rtx));
 389 static unsigned int blockage_range PROTO ((int, rtx));
 390 static void clear_units PROTO ((void));
 391 static int actual_hazard_this_instance PROTO ((int, int, rtx, int, int));
 392 static void schedule_unit PROTO ((int, rtx, int));
 393 static int actual_hazard PROTO ((int, rtx, int, int));
 394 static int potential_hazard PROTO ((int, rtx, int));
 395 static int insn_cost PROTO ((rtx, rtx, rtx));
 396 static int priority PROTO ((rtx));
 397 static void free_pending_lists PROTO ((void));
 398 static void add_insn_mem_dependence PROTO ((rtx *, rtx *, rtx, rtx));
 399 static void flush_pending_lists PROTO ((rtx, int));
 400 static void sched_analyze_1 PROTO ((rtx, rtx));
 401 static void sched_analyze_2 PROTO ((rtx, rtx));
 402 static void sched_analyze_insn PROTO ((rtx, rtx, rtx));
 403 static void sched_analyze PROTO ((rtx, rtx));
 404 static int rank_for_schedule PROTO ((const PTR, const PTR));
 405 static void swap_sort PROTO ((rtx *, int));
 406 static void queue_insn PROTO ((rtx, int));
 407 static int schedule_insn PROTO ((rtx, rtx *, int, int));
 408 static void find_insn_reg_weight PROTO ((int));
 409 static int schedule_block PROTO ((int, int));
 410 static char *safe_concat PROTO ((char *, char *, const char *));
 411 static int insn_issue_delay PROTO ((rtx));
 412 static void adjust_priority PROTO ((rtx));
 413
 414 /* Mapping of insns to their original block prior to scheduling.  */
 415 static int *insn_orig_block;
 416 #define INSN_BLOCK(insn) (insn_orig_block[INSN_UID (insn)])
 417
 418 /* Some insns (e.g. call) are not allowed to move across blocks.  */
 419 static char *cant_move;
 420 #define CANT_MOVE(insn) (cant_move[INSN_UID (insn)])
 421
 422 /* Control flow graph edges are kept in circular lists.  */
 423 typedef struct
 424   {
 425     int from_block;
 426     int to_block;
 427     int next_in;
 428     int next_out;
 429   }
 430 haifa_edge;
 431 static haifa_edge *edge_table;
 432
 433 #define NEXT_IN(edge) (edge_table[edge].next_in)
 434 #define NEXT_OUT(edge) (edge_table[edge].next_out)
 435 #define FROM_BLOCK(edge) (edge_table[edge].from_block)
 436 #define TO_BLOCK(edge) (edge_table[edge].to_block)
 437
 438 /* Number of edges in the control flow graph.  (In fact, larger than
 439    that by 1, since edge 0 is unused.)  */
 440 static int nr_edges;
 441
 442 /* Circular list of incoming/outgoing edges of a block.  */
 443 static int *in_edges;
 444 static int *out_edges;
 445
 446 #define IN_EDGES(block) (in_edges[block])
 447 #define OUT_EDGES(block) (out_edges[block])
 448
 449
 450
 451 static int is_cfg_nonregular PROTO ((void));
 452 static int build_control_flow PROTO ((int_list_ptr *, int_list_ptr *,
 453                                       int *, int *));
 454 static void new_edge PROTO ((int, int));
 455
 456
 457 /* A region is the main entity for interblock scheduling: insns
 458    are allowed to move between blocks in the same region, along
 459    control flow graph edges, in the 'up' direction.  */
 460 typedef struct
 461   {
 462     int rgn_nr_blocks;          /* Number of blocks in region.  */
 463     int rgn_blocks;             /* cblocks in the region (actually index in rgn_bb_table).  */
 464   }
 465 region;
 466
 467 /* Number of regions in the procedure.  */
 468 static int nr_regions;
 469
 470 /* Table of region descriptions.  */
 471 static region *rgn_table;
 472
 473 /* Array of lists of regions' blocks.  */
 474 static int *rgn_bb_table;
 475
 476 /* Topological order of blocks in the region (if b2 is reachable from
 477    b1, block_to_bb[b2] > block_to_bb[b1]).  Note: A basic block is
 478    always referred to by either block or b, while its topological
 479    order name (in the region) is refered to by bb.  */
 480 static int *block_to_bb;
 481
 482 /* The number of the region containing a block.  */
 483 static int *containing_rgn;
 484
 485 #define RGN_NR_BLOCKS(rgn) (rgn_table[rgn].rgn_nr_blocks)
 486 #define RGN_BLOCKS(rgn) (rgn_table[rgn].rgn_blocks)
 487 #define BLOCK_TO_BB(block) (block_to_bb[block])
 488 #define CONTAINING_RGN(block) (containing_rgn[block])
 489
 490 void debug_regions PROTO ((void));
 491 static void find_single_block_region PROTO ((void));
 492 static void find_rgns PROTO ((int_list_ptr *, int_list_ptr *,
 493                               int *, int *, sbitmap *));
 494 static int too_large PROTO ((int, int *, int *));
 495
 496 extern void debug_live PROTO ((int, int));
 497
 498 /* Blocks of the current region being scheduled.  */
 499 static int current_nr_blocks;
 500 static int current_blocks;
 501
 502 /* The mapping from bb to block.  */
 503 #define BB_TO_BLOCK(bb) (rgn_bb_table[current_blocks + (bb)])
 504
 505
 506 /* Bit vectors and bitset operations are needed for computations on
 507    the control flow graph.  */
 508
 509 typedef unsigned HOST_WIDE_INT *bitset;
 510 typedef struct
 511   {
 512     int *first_member;          /* Pointer to the list start in bitlst_table.  */
 513     int nr_members;             /* The number of members of the bit list.  */
 514   }
 515 bitlst;
 516
 517 static int bitlst_table_last;
 518 static int bitlst_table_size;
 519 static int *bitlst_table;
 520
 521 static char bitset_member PROTO ((bitset, int, int));
 522 static void extract_bitlst PROTO ((bitset, int, bitlst *));
 523
 524 /* Target info declarations.
 525
 526    The block currently being scheduled is referred to as the "target" block,
 527    while other blocks in the region from which insns can be moved to the
 528    target are called "source" blocks.  The candidate structure holds info
 529    about such sources: are they valid?  Speculative?  Etc.  */
 530 typedef bitlst bblst;
 531 typedef struct
 532   {
 533     char is_valid;
 534     char is_speculative;
 535     int src_prob;
 536     bblst split_bbs;
 537     bblst update_bbs;
 538   }
 539 candidate;
 540
 541 static candidate *candidate_table;
 542
 543 /* A speculative motion requires checking live information on the path
 544    from 'source' to 'target'.  The split blocks are those to be checked.
 545    After a speculative motion, live information should be modified in
 546    the 'update' blocks.
 547
 548    Lists of split and update blocks for each candidate of the current
 549    target are in array bblst_table.  */
 550 static int *bblst_table, bblst_size, bblst_last;
 551
 552 #define IS_VALID(src) ( candidate_table[src].is_valid )
 553 #define IS_SPECULATIVE(src) ( candidate_table[src].is_speculative )
 554 #define SRC_PROB(src) ( candidate_table[src].src_prob )
 555
 556 /* The bb being currently scheduled.  */
 557 static int target_bb;
 558
 559 /* List of edges.  */
 560 typedef bitlst edgelst;
 561
 562 /* Target info functions.  */
 563 static void split_edges PROTO ((int, int, edgelst *));
 564 static void compute_trg_info PROTO ((int));
 565 void debug_candidate PROTO ((int));
 566 void debug_candidates PROTO ((int));
 567
 568
 569 /* Bit-set of bbs, where bit 'i' stands for bb 'i'.  */
 570 typedef bitset bbset;
 571
 572 /* Number of words of the bbset.  */
 573 static int bbset_size;
 574
 575 /* Dominators array: dom[i] contains the bbset of dominators of
 576    bb i in the region.  */
 577 static bbset *dom;
 578
 579 /* bb 0 is the only region entry.  */
 580 #define IS_RGN_ENTRY(bb) (!bb)
 581
 582 /* Is bb_src dominated by bb_trg.  */
 583 #define IS_DOMINATED(bb_src, bb_trg)                                 \
 584 ( bitset_member (dom[bb_src], bb_trg, bbset_size) )
 585
 586 /* Probability: Prob[i] is a float in [0, 1] which is the probability
 587    of bb i relative to the region entry.  */
 588 static float *prob;
 589
 590 /* The probability of bb_src, relative to bb_trg.  Note, that while the
 591    'prob[bb]' is a float in [0, 1], this macro returns an integer
 592    in [0, 100].  */
 593 #define GET_SRC_PROB(bb_src, bb_trg) ((int) (100.0 * (prob[bb_src] / \
 594                                                       prob[bb_trg])))
 595
 596 /* Bit-set of edges, where bit i stands for edge i.  */
 597 typedef bitset edgeset;
 598
 599 /* Number of edges in the region.  */
 600 static int rgn_nr_edges;
 601
 602 /* Array of size rgn_nr_edges.  */
 603 static int *rgn_edges;
 604
 605 /* Number of words in an edgeset.  */
 606 static int edgeset_size;
 607
 608 /* Mapping from each edge in the graph to its number in the rgn.  */
 609 static int *edge_to_bit;
 610 #define EDGE_TO_BIT(edge) (edge_to_bit[edge])
 611
 612 /* The split edges of a source bb is different for each target
 613    bb.  In order to compute this efficiently, the 'potential-split edges'
 614    are computed for each bb prior to scheduling a region.  This is actually
 615    the split edges of each bb relative to the region entry.
 616
 617    pot_split[bb] is the set of potential split edges of bb.  */
 618 static edgeset *pot_split;
 619
 620 /* For every bb, a set of its ancestor edges.  */
 621 static edgeset *ancestor_edges;
 622
 623 static void compute_dom_prob_ps PROTO ((int));
 624
 625 #define ABS_VALUE(x) (((x)<0)?(-(x)):(x))
 626 #define INSN_PROBABILITY(INSN) (SRC_PROB (BLOCK_TO_BB (INSN_BLOCK (INSN))))
 627 #define IS_SPECULATIVE_INSN(INSN) (IS_SPECULATIVE (BLOCK_TO_BB (INSN_BLOCK (INSN))))
 628 #define INSN_BB(INSN) (BLOCK_TO_BB (INSN_BLOCK (INSN)))
 629
 630 /* Parameters affecting the decision of rank_for_schedule().  */
 631 #define MIN_DIFF_PRIORITY 2
 632 #define MIN_PROBABILITY 40
 633 #define MIN_PROB_DIFF 10
 634
 635 /* Speculative scheduling functions.  */
 636 static int check_live_1 PROTO ((int, rtx));
 637 static void update_live_1 PROTO ((int, rtx));
 638 static int check_live PROTO ((rtx, int));
 639 static void update_live PROTO ((rtx, int));
 640 static void set_spec_fed PROTO ((rtx));
 641 static int is_pfree PROTO ((rtx, int, int));
 642 static int find_conditional_protection PROTO ((rtx, int));
 643 static int is_conditionally_protected PROTO ((rtx, int, int));
 644 static int may_trap_exp PROTO ((rtx, int));
 645 static int haifa_classify_insn PROTO ((rtx));
 646 static int is_prisky PROTO ((rtx, int, int));
 647 static int is_exception_free PROTO ((rtx, int, int));
 648
 649 static char find_insn_mem_list PROTO ((rtx, rtx, rtx, rtx));
 650 static void compute_block_forward_dependences PROTO ((int));
 651 static void init_rgn_data_dependences PROTO ((int));
 652 static void add_branch_dependences PROTO ((rtx, rtx));
 653 static void compute_block_backward_dependences PROTO ((int));
 654 void debug_dependencies PROTO ((void));
 655
 656 /* Notes handling mechanism:
 657    =========================
 658    Generally, NOTES are saved before scheduling and restored after scheduling.
 659    The scheduler distinguishes between three types of notes:
 660
 661    (1) LINE_NUMBER notes, generated and used for debugging.  Here,
 662    before scheduling a region, a pointer to the LINE_NUMBER note is
 663    added to the insn following it (in save_line_notes()), and the note
 664    is removed (in rm_line_notes() and unlink_line_notes()).  After
 665    scheduling the region, this pointer is used for regeneration of
 666    the LINE_NUMBER note (in restore_line_notes()).
 667
 668    (2) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes:
 669    Before scheduling a region, a pointer to the note is added to the insn
 670    that follows or precedes it.  (This happens as part of the data dependence
 671    computation).  After scheduling an insn, the pointer contained in it is
 672    used for regenerating the corresponding note (in reemit_notes).
 673
 674    (3) All other notes (e.g. INSN_DELETED):  Before scheduling a block,
 675    these notes are put in a list (in rm_other_notes() and
 676    unlink_other_notes ()).  After scheduling the block, these notes are
 677    inserted at the beginning of the block (in schedule_block()).  */
 678
 679 static rtx unlink_other_notes PROTO ((rtx, rtx));
 680 static rtx unlink_line_notes PROTO ((rtx, rtx));
 681 static void rm_line_notes PROTO ((int));
 682 static void save_line_notes PROTO ((int));
 683 static void restore_line_notes PROTO ((int));
 684 static void rm_redundant_line_notes PROTO ((void));
 685 static void rm_other_notes PROTO ((rtx, rtx));
 686 static rtx reemit_notes PROTO ((rtx, rtx));
 687
 688 static void get_block_head_tail PROTO ((int, rtx *, rtx *));
 689
 690 static int queue_to_ready PROTO ((rtx [], int));
 691
 692 static void debug_ready_list PROTO ((rtx[], int));
 693 static void init_target_units PROTO ((void));
 694 static void insn_print_units PROTO ((rtx));
 695 static int get_visual_tbl_length PROTO ((void));
 696 static void init_block_visualization PROTO ((void));
 697 static void print_block_visualization PROTO ((int, const char *));
 698 static void visualize_scheduled_insns PROTO ((int, int));
 699 static void visualize_no_unit PROTO ((rtx));
 700 static void visualize_stall_cycles PROTO ((int, int));
 701 static void print_exp PROTO ((char *, rtx, int));
 702 static void print_value PROTO ((char *, rtx, int));
 703 static void print_pattern PROTO ((char *, rtx, int));
 704 static void print_insn PROTO ((char *, rtx, int));
 705 void debug_reg_vector PROTO ((regset));
 706
 707 static rtx move_insn1 PROTO ((rtx, rtx));
 708 static rtx move_insn PROTO ((rtx, rtx));
 709 static rtx group_leader PROTO ((rtx));
 710 static int set_priorities PROTO ((int));
 711 static void init_rtx_vector PROTO ((rtx **, rtx *, int, int));
 712 static void schedule_region PROTO ((int));
 713
 714 #endif /* INSN_SCHEDULING */
 715 \f
 716 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
 717
 718 /* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the
 719    LOG_LINKS of INSN, if not already there.  DEP_TYPE indicates the type
 720    of dependence that this link represents.  */
 721
 722 static void
 723 add_dependence (insn, elem, dep_type)
 724      rtx insn;
 725      rtx elem;
 726      enum reg_note dep_type;
 727 {
 728   rtx link, next;
 729
 730   /* Don't depend an insn on itself.  */
 731   if (insn == elem)
 732     return;
 733
 734   /* We can get a dependency on deleted insns due to optimizations in
 735      the register allocation and reloading or due to splitting.  Any
 736      such dependency is useless and can be ignored.  */
 737   if (GET_CODE (elem) == NOTE)
 738     return;
 739
 740   /* If elem is part of a sequence that must be scheduled together, then
 741      make the dependence point to the last insn of the sequence.
 742      When HAVE_cc0, it is possible for NOTEs to exist between users and
 743      setters of the condition codes, so we must skip past notes here.
 744      Otherwise, NOTEs are impossible here.  */
 745
 746   next = NEXT_INSN (elem);
 747
 748 #ifdef HAVE_cc0
 749   while (next && GET_CODE (next) == NOTE)
 750     next = NEXT_INSN (next);
 751 #endif
 752
 753   if (next && SCHED_GROUP_P (next)
 754       && GET_CODE (next) != CODE_LABEL)
 755     {
 756       /* Notes will never intervene here though, so don't bother checking
 757          for them.  */
 758       /* We must reject CODE_LABELs, so that we don't get confused by one
 759          that has LABEL_PRESERVE_P set, which is represented by the same
 760          bit in the rtl as SCHED_GROUP_P.  A CODE_LABEL can never be
 761          SCHED_GROUP_P.  */
 762       while (NEXT_INSN (next) && SCHED_GROUP_P (NEXT_INSN (next))
 763              && GET_CODE (NEXT_INSN (next)) != CODE_LABEL)
 764         next = NEXT_INSN (next);
 765
 766       /* Again, don't depend an insn on itself.  */
 767       if (insn == next)
 768         return;
 769
 770       /* Make the dependence to NEXT, the last insn of the group, instead
 771          of the original ELEM.  */
 772       elem = next;
 773     }
 774
 775 #ifdef INSN_SCHEDULING
 776   /* (This code is guarded by INSN_SCHEDULING, otherwise INSN_BB is undefined.)
 777      No need for interblock dependences with calls, since
 778      calls are not moved between blocks.   Note: the edge where
 779      elem is a CALL is still required.  */
 780   if (GET_CODE (insn) == CALL_INSN
 781       && (INSN_BB (elem) != INSN_BB (insn)))
 782     return;
 783
 784 #endif
 785
 786   /* Check that we don't already have this dependence.  */
 787   for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
 788     if (XEXP (link, 0) == elem)
 789       {
 790         /* If this is a more restrictive type of dependence than the existing
 791            one, then change the existing dependence to this type.  */
 792         if ((int) dep_type < (int) REG_NOTE_KIND (link))
 793           PUT_REG_NOTE_KIND (link, dep_type);
 794         return;
 795       }
 796   /* Might want to check one level of transitivity to save conses.  */
 797
 798   link = alloc_INSN_LIST (elem, LOG_LINKS (insn));
 799   LOG_LINKS (insn) = link;
 800
 801   /* Insn dependency, not data dependency.  */
 802   PUT_REG_NOTE_KIND (link, dep_type);
 803 }
 804
 805 /* Remove ELEM wrapped in an INSN_LIST from the LOG_LINKS
 806    of INSN.  Abort if not found.  */
 807
 808 static void
 809 remove_dependence (insn, elem)
 810      rtx insn;
 811      rtx elem;
 812 {
 813   rtx prev, link, next;
 814   int found = 0;
 815
 816   for (prev = 0, link = LOG_LINKS (insn); link; link = next)
 817     {
 818       next = XEXP (link, 1);
 819       if (XEXP (link, 0) == elem)
 820         {
 821           if (prev)
 822             XEXP (prev, 1) = next;
 823           else
 824             LOG_LINKS (insn) = next;
 825           free_INSN_LIST_node (link);
 826
 827           found = 1;
 828         }
 829       else
 830         prev = link;
 831     }
 832
 833   if (!found)
 834     abort ();
 835   return;
 836 }
 837 \f
 838 #ifndef INSN_SCHEDULING
 839 void
 840 schedule_insns (dump_file)
 841      FILE *dump_file;
 842 {
 843 }
 844 #else
 845 #ifndef __GNUC__
 846 #define __inline
 847 #endif
 848
 849 #ifndef HAIFA_INLINE
 850 #define HAIFA_INLINE __inline
 851 #endif
 852
 853 /* Computation of memory dependencies.  */
 854
 855 /* The *_insns and *_mems are paired lists.  Each pending memory operation
 856    will have a pointer to the MEM rtx on one list and a pointer to the
 857    containing insn on the other list in the same place in the list.  */
 858
 859 /* We can't use add_dependence like the old code did, because a single insn
 860    may have multiple memory accesses, and hence needs to be on the list
 861    once for each memory access.  Add_dependence won't let you add an insn
 862    to a list more than once.  */
 863
 864 /* An INSN_LIST containing all insns with pending read operations.  */
 865 static rtx pending_read_insns;
 866
 867 /* An EXPR_LIST containing all MEM rtx's which are pending reads.  */
 868 static rtx pending_read_mems;
 869
 870 /* An INSN_LIST containing all insns with pending write operations.  */
 871 static rtx pending_write_insns;
 872
 873 /* An EXPR_LIST containing all MEM rtx's which are pending writes.  */
 874 static rtx pending_write_mems;
 875
 876 /* Indicates the combined length of the two pending lists.  We must prevent
 877    these lists from ever growing too large since the number of dependencies
 878    produced is at least O(N*N), and execution time is at least O(4*N*N), as
 879    a function of the length of these pending lists.  */
 880
 881 static int pending_lists_length;
 882
 883 /* The last insn upon which all memory references must depend.
 884    This is an insn which flushed the pending lists, creating a dependency
 885    between it and all previously pending memory references.  This creates
 886    a barrier (or a checkpoint) which no memory reference is allowed to cross.
 887
 888    This includes all non constant CALL_INSNs.  When we do interprocedural
 889    alias analysis, this restriction can be relaxed.
 890    This may also be an INSN that writes memory if the pending lists grow
 891    too large.  */
 892
 893 static rtx last_pending_memory_flush;
 894
 895 /* The last function call we have seen.  All hard regs, and, of course,
 896    the last function call, must depend on this.  */
 897
 898 static rtx last_function_call;
 899
 900 /* The LOG_LINKS field of this is a list of insns which use a pseudo register
 901    that does not already cross a call.  We create dependencies between each
 902    of those insn and the next call insn, to ensure that they won't cross a call
 903    after scheduling is done.  */
 904
 905 static rtx sched_before_next_call;
 906
 907 /* Pointer to the last instruction scheduled.  Used by rank_for_schedule,
 908    so that insns independent of the last scheduled insn will be preferred
 909    over dependent instructions.  */
 910
 911 static rtx last_scheduled_insn;
 912
 913 /* Data structures for the computation of data dependences in a regions.  We
 914    keep one copy of each of the declared above variables for each bb in the
 915    region.  Before analyzing the data dependences for a bb, its variables
 916    are initialized as a function of the variables of its predecessors.  When
 917    the analysis for a bb completes, we save the contents of each variable X
 918    to a corresponding bb_X[bb] variable.  For example, pending_read_insns is
 919    copied to bb_pending_read_insns[bb].  Another change is that few
 920    variables are now a list of insns rather than a single insn:
 921    last_pending_memory_flash, last_function_call, reg_last_sets.  The
 922    manipulation of these variables was changed appropriately.  */
 923
 924 static rtx **bb_reg_last_uses;
 925 static rtx **bb_reg_last_sets;
 926 static rtx **bb_reg_last_clobbers;
 927
 928 static rtx *bb_pending_read_insns;
 929 static rtx *bb_pending_read_mems;
 930 static rtx *bb_pending_write_insns;
 931 static rtx *bb_pending_write_mems;
 932 static int *bb_pending_lists_length;
 933
 934 static rtx *bb_last_pending_memory_flush;
 935 static rtx *bb_last_function_call;
 936 static rtx *bb_sched_before_next_call;
 937
 938 /* Functions for construction of the control flow graph.  */
 939
 940 /* Return 1 if control flow graph should not be constructed, 0 otherwise.
 941
 942    We decide not to build the control flow graph if there is possibly more
 943    than one entry to the function, if computed branches exist, of if we
 944    have nonlocal gotos.  */
 945
 946 static int
 947 is_cfg_nonregular ()
 948 {
 949   int b;
 950   rtx insn;
 951   RTX_CODE code;
 952
 953   /* If we have a label that could be the target of a nonlocal goto, then
 954      the cfg is not well structured.  */
 955   if (nonlocal_goto_handler_labels)
 956     return 1;
 957
 958   /* If we have any forced labels, then the cfg is not well structured.  */
 959   if (forced_labels)
 960     return 1;
 961
 962   /* If this function has a computed jump, then we consider the cfg
 963      not well structured.  */
 964   if (current_function_has_computed_jump)
 965     return 1;
 966
 967   /* If we have exception handlers, then we consider the cfg not well
 968      structured.  ?!?  We should be able to handle this now that flow.c
 969      computes an accurate cfg for EH.  */
 970   if (exception_handler_labels)
 971     return 1;
 972
 973   /* If we have non-jumping insns which refer to labels, then we consider
 974      the cfg not well structured.  */
 975   /* Check for labels referred to other thn by jumps.  */
 976   for (b = 0; b < n_basic_blocks; b++)
 977     for (insn = BLOCK_HEAD (b);; insn = NEXT_INSN (insn))
 978       {
 979         code = GET_CODE (insn);
 980         if (GET_RTX_CLASS (code) == 'i')
 981           {
 982             rtx note;
 983
 984             for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
 985               if (REG_NOTE_KIND (note) == REG_LABEL)
 986                 return 1;
 987           }
 988
 989         if (insn == BLOCK_END (b))
 990           break;
 991       }
 992
 993   /* All the tests passed.  Consider the cfg well structured.  */
 994   return 0;
 995 }
 996
 997 /* Build the control flow graph and set nr_edges.
 998
 999    Instead of trying to build a cfg ourselves, we rely on flow to
1000    do it for us.  Stamp out useless code (and bug) duplication.
1001
1002    Return nonzero if an irregularity in the cfg is found which would
1003    prevent cross block scheduling.  */
1004
1005 static int
1006 build_control_flow (s_preds, s_succs, num_preds, num_succs)
1007      int_list_ptr *s_preds;
1008      int_list_ptr *s_succs;
1009      int *num_preds;
1010      int *num_succs;
1011 {
1012   int i;
1013   int_list_ptr succ;
1014   int unreachable;
1015
1016   /* Count the number of edges in the cfg.  */
1017   nr_edges = 0;
1018   unreachable = 0;
1019   for (i = 0; i < n_basic_blocks; i++)
1020     {
1021       nr_edges += num_succs[i];
1022
1023       /* Unreachable loops with more than one basic block are detected
1024          during the DFS traversal in find_rgns.
1025
1026          Unreachable loops with a single block are detected here.  This
1027          test is redundant with the one in find_rgns, but it's much
1028          cheaper to go ahead and catch the trivial case here.  */
1029       if (num_preds[i] == 0
1030           || (num_preds[i] == 1 && INT_LIST_VAL (s_preds[i]) == i))
1031         unreachable = 1;
1032     }
1033
1034   /* Account for entry/exit edges.  */
1035   nr_edges += 2;
1036
1037   in_edges = (int *) xcalloc (n_basic_blocks, sizeof (int));
1038   out_edges = (int *) xcalloc (n_basic_blocks, sizeof (int));
1039   edge_table = (haifa_edge *) xcalloc (nr_edges, sizeof (haifa_edge));
1040
1041   nr_edges = 0;
1042   for (i = 0; i < n_basic_blocks; i++)
1043     for (succ = s_succs[i]; succ; succ = succ->next)
1044       {
1045         if (INT_LIST_VAL (succ) != EXIT_BLOCK)
1046           new_edge (i, INT_LIST_VAL (succ));
1047       }
1048
1049   /* Increment by 1, since edge 0 is unused.  */
1050   nr_edges++;
1051
1052   return unreachable;
1053 }
1054
1055
1056 /* Record an edge in the control flow graph from SOURCE to TARGET.
1057
1058    In theory, this is redundant with the s_succs computed above, but
1059    we have not converted all of haifa to use information from the
1060    integer lists.  */
1061
1062 static void
1063 new_edge (source, target)
1064      int source, target;
1065 {
1066   int e, next_edge;
1067   int curr_edge, fst_edge;
1068
1069   /* Check for duplicates.  */
1070   fst_edge = curr_edge = OUT_EDGES (source);
1071   while (curr_edge)
1072     {
1073       if (FROM_BLOCK (curr_edge) == source
1074           && TO_BLOCK (curr_edge) == target)
1075         {
1076           return;
1077         }
1078
1079       curr_edge = NEXT_OUT (curr_edge);
1080
1081       if (fst_edge == curr_edge)
1082         break;
1083     }
1084
1085   e = ++nr_edges;
1086
1087   FROM_BLOCK (e) = source;
1088   TO_BLOCK (e) = target;
1089
1090   if (OUT_EDGES (source))
1091     {
1092       next_edge = NEXT_OUT (OUT_EDGES (source));
1093       NEXT_OUT (OUT_EDGES (source)) = e;
1094       NEXT_OUT (e) = next_edge;
1095     }
1096   else
1097     {
1098       OUT_EDGES (source) = e;
1099       NEXT_OUT (e) = e;
1100     }
1101
1102   if (IN_EDGES (target))
1103     {
1104       next_edge = NEXT_IN (IN_EDGES (target));
1105       NEXT_IN (IN_EDGES (target)) = e;
1106       NEXT_IN (e) = next_edge;
1107     }
1108   else
1109     {
1110       IN_EDGES (target) = e;
1111       NEXT_IN (e) = e;
1112     }
1113 }
1114
1115
1116 /* BITSET macros for operations on the control flow graph.  */
1117
1118 /* Compute bitwise union of two bitsets.  */
1119 #define BITSET_UNION(set1, set2, len)                                \
1120 do { register bitset tp = set1, sp = set2;                           \
1121      register int i;                                                 \
1122      for (i = 0; i < len; i++)                                       \
1123        *(tp++) |= *(sp++); } while (0)
1124
1125 /* Compute bitwise intersection of two bitsets.  */
1126 #define BITSET_INTER(set1, set2, len)                                \
1127 do { register bitset tp = set1, sp = set2;                           \
1128      register int i;                                                 \
1129      for (i = 0; i < len; i++)                                       \
1130        *(tp++) &= *(sp++); } while (0)
1131
1132 /* Compute bitwise difference of two bitsets.  */
1133 #define BITSET_DIFFER(set1, set2, len)                               \
1134 do { register bitset tp = set1, sp = set2;                           \
1135      register int i;                                                 \
1136      for (i = 0; i < len; i++)                                       \
1137        *(tp++) &= ~*(sp++); } while (0)
1138
1139 /* Inverts every bit of bitset 'set'.  */
1140 #define BITSET_INVERT(set, len)                                      \
1141 do { register bitset tmpset = set;                                   \
1142      register int i;                                                 \
1143      for (i = 0; i < len; i++, tmpset++)                             \
1144        *tmpset = ~*tmpset; } while (0)
1145
1146 /* Turn on the index'th bit in bitset set.  */
1147 #define BITSET_ADD(set, index, len)                                  \
1148 {                                                                    \
1149   if (index >= HOST_BITS_PER_WIDE_INT * len)                         \
1150     abort ();                                                        \
1151   else                                                               \
1152     set[index/HOST_BITS_PER_WIDE_INT] |=                             \
1153       1 << (index % HOST_BITS_PER_WIDE_INT);                         \
1154 }
1155
1156 /* Turn off the index'th bit in set.  */
1157 #define BITSET_REMOVE(set, index, len)                               \
1158 {                                                                    \
1159   if (index >= HOST_BITS_PER_WIDE_INT * len)                         \
1160     abort ();                                                        \
1161   else                                                               \
1162     set[index/HOST_BITS_PER_WIDE_INT] &=                             \
1163       ~(1 << (index%HOST_BITS_PER_WIDE_INT));                        \
1164 }
1165
1166
1167 /* Check if the index'th bit in bitset set is on.  */
1168
1169 static char
1170 bitset_member (set, index, len)
1171      bitset set;
1172      int index, len;
1173 {
1174   if (index >= HOST_BITS_PER_WIDE_INT * len)
1175     abort ();
1176   return (set[index / HOST_BITS_PER_WIDE_INT] &
1177           1 << (index % HOST_BITS_PER_WIDE_INT)) ? 1 : 0;
1178 }
1179
1180
1181 /* Translate a bit-set SET to a list BL of the bit-set members.  */
1182
1183 static void
1184 extract_bitlst (set, len, bl)
1185      bitset set;
1186      int len;
1187      bitlst *bl;
1188 {
1189   int i, j, offset;
1190   unsigned HOST_WIDE_INT word;
1191
1192   /* bblst table space is reused in each call to extract_bitlst.  */
1193   bitlst_table_last = 0;
1194
1195   bl->first_member = &bitlst_table[bitlst_table_last];
1196   bl->nr_members = 0;
1197
1198   for (i = 0; i < len; i++)
1199     {
1200       word = set[i];
1201       offset = i * HOST_BITS_PER_WIDE_INT;
1202       for (j = 0; word; j++)
1203         {
1204           if (word & 1)
1205             {
1206               bitlst_table[bitlst_table_last++] = offset;
1207               (bl->nr_members)++;
1208             }
1209           word >>= 1;
1210           ++offset;
1211         }
1212     }
1213
1214 }
1215
1216
1217 /* Functions for the construction of regions.  */
1218
1219 /* Print the regions, for debugging purposes.  Callable from debugger.  */
1220
1221 void
1222 debug_regions ()
1223 {
1224   int rgn, bb;
1225
1226   fprintf (dump, "\n;;   ------------ REGIONS ----------\n\n");
1227   for (rgn = 0; rgn < nr_regions; rgn++)
1228     {
1229       fprintf (dump, ";;\trgn %d nr_blocks %d:\n", rgn,
1230                rgn_table[rgn].rgn_nr_blocks);
1231       fprintf (dump, ";;\tbb/block: ");
1232
1233       for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++)
1234         {
1235           current_blocks = RGN_BLOCKS (rgn);
1236
1237           if (bb != BLOCK_TO_BB (BB_TO_BLOCK (bb)))
1238             abort ();
1239
1240           fprintf (dump, " %d/%d ", bb, BB_TO_BLOCK (bb));
1241         }
1242
1243       fprintf (dump, "\n\n");
1244     }
1245 }
1246
1247
1248 /* Build a single block region for each basic block in the function.
1249    This allows for using the same code for interblock and basic block
1250    scheduling.  */
1251
1252 static void
1253 find_single_block_region ()
1254 {
1255   int i;
1256
1257   for (i = 0; i < n_basic_blocks; i++)
1258     {
1259       rgn_bb_table[i] = i;
1260       RGN_NR_BLOCKS (i) = 1;
1261       RGN_BLOCKS (i) = i;
1262       CONTAINING_RGN (i) = i;
1263       BLOCK_TO_BB (i) = 0;
1264     }
1265   nr_regions = n_basic_blocks;
1266 }
1267
1268
1269 /* Update number of blocks and the estimate for number of insns
1270    in the region.  Return 1 if the region is "too large" for interblock
1271    scheduling (compile time considerations), otherwise return 0.  */
1272
1273 static int
1274 too_large (block, num_bbs, num_insns)
1275      int block, *num_bbs, *num_insns;
1276 {
1277   (*num_bbs)++;
1278   (*num_insns) += (INSN_LUID (BLOCK_END (block)) -
1279                    INSN_LUID (BLOCK_HEAD (block)));
1280   if ((*num_bbs > MAX_RGN_BLOCKS) || (*num_insns > MAX_RGN_INSNS))
1281     return 1;
1282   else
1283     return 0;
1284 }
1285
1286
1287 /* Update_loop_relations(blk, hdr): Check if the loop headed by max_hdr[blk]
1288    is still an inner loop.  Put in max_hdr[blk] the header of the most inner
1289    loop containing blk.  */
1290 #define UPDATE_LOOP_RELATIONS(blk, hdr)                              \
1291 {                                                                    \
1292   if (max_hdr[blk] == -1)                                            \
1293     max_hdr[blk] = hdr;                                              \
1294   else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr])                       \
1295          RESET_BIT (inner, hdr);                                     \
1296   else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr])                       \
1297          {                                                           \
1298             RESET_BIT (inner,max_hdr[blk]);                          \
1299             max_hdr[blk] = hdr;                                      \
1300          }                                                           \
1301 }
1302
1303
1304 /* Find regions for interblock scheduling.
1305
1306    A region for scheduling can be:
1307
1308      * A loop-free procedure, or
1309
1310      * A reducible inner loop, or
1311
1312      * A basic block not contained in any other region.
1313
1314
1315    ?!? In theory we could build other regions based on extended basic
1316    blocks or reverse extended basic blocks.  Is it worth the trouble?
1317
1318    Loop blocks that form a region are put into the region's block list
1319    in topological order.
1320
1321    This procedure stores its results into the following global (ick) variables
1322
1323      * rgn_nr
1324      * rgn_table
1325      * rgn_bb_table
1326      * block_to_bb
1327      * containing region
1328
1329
1330    We use dominator relationships to avoid making regions out of non-reducible
1331    loops.
1332
1333    This procedure needs to be converted to work on pred/succ lists instead
1334    of edge tables.  That would simplify it somewhat.  */
1335
1336 static void
1337 find_rgns (s_preds, s_succs, num_preds, num_succs, dom)
1338      int_list_ptr *s_preds;
1339      int_list_ptr *s_succs;
1340      int *num_preds;
1341      int *num_succs;
1342      sbitmap *dom;
1343 {
1344   int *max_hdr, *dfs_nr, *stack, *queue, *degree;
1345   char no_loops = 1;
1346   int node, child, loop_head, i, head, tail;
1347   int count = 0, sp, idx = 0, current_edge = out_edges[0];
1348   int num_bbs, num_insns, unreachable;
1349   int too_large_failure;
1350
1351   /* Note if an edge has been passed.  */
1352   sbitmap passed;
1353
1354   /* Note if a block is a natural loop header.  */
1355   sbitmap header;
1356
1357   /* Note if a block is an natural inner loop header.  */
1358   sbitmap inner;
1359
1360   /* Note if a block is in the block queue. */
1361   sbitmap in_queue;
1362
1363   /* Note if a block is in the block queue. */
1364   sbitmap in_stack;
1365
1366   /* Perform a DFS traversal of the cfg.  Identify loop headers, inner loops
1367      and a mapping from block to its loop header (if the block is contained
1368      in a loop, else -1).
1369
1370      Store results in HEADER, INNER, and MAX_HDR respectively, these will
1371      be used as inputs to the second traversal.
1372
1373      STACK, SP and DFS_NR are only used during the first traversal.  */
1374
1375   /* Allocate and initialize variables for the first traversal.  */
1376   max_hdr = (int *) alloca (n_basic_blocks * sizeof (int));
1377   dfs_nr = (int *) alloca (n_basic_blocks * sizeof (int));
1378   bzero ((char *) dfs_nr, n_basic_blocks * sizeof (int));
1379   stack = (int *) alloca (nr_edges * sizeof (int));
1380
1381   inner = sbitmap_alloc (n_basic_blocks);
1382   sbitmap_ones (inner);
1383
1384   header = sbitmap_alloc (n_basic_blocks);
1385   sbitmap_zero (header);
1386
1387   passed = sbitmap_alloc (nr_edges);
1388   sbitmap_zero (passed);
1389
1390   in_queue = sbitmap_alloc (n_basic_blocks);
1391   sbitmap_zero (in_queue);
1392
1393   in_stack = sbitmap_alloc (n_basic_blocks);
1394   sbitmap_zero (in_stack);
1395
1396   for (i = 0; i < n_basic_blocks; i++)
1397     max_hdr[i] = -1;
1398
1399   /* DFS traversal to find inner loops in the cfg.  */
1400
1401   sp = -1;
1402   while (1)
1403     {
1404       if (current_edge == 0 || TEST_BIT (passed, current_edge))
1405         {
1406           /* We have reached a leaf node or a node that was already
1407              processed.  Pop edges off the stack until we find
1408              an edge that has not yet been processed.  */
1409           while (sp >= 0
1410                  && (current_edge == 0 || TEST_BIT (passed, current_edge)))
1411             {
1412               /* Pop entry off the stack.  */
1413               current_edge = stack[sp--];
1414               node = FROM_BLOCK (current_edge);
1415               child = TO_BLOCK (current_edge);
1416               RESET_BIT (in_stack, child);
1417               if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child]))
1418                 UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
1419               current_edge = NEXT_OUT (current_edge);
1420             }
1421
1422           /* See if have finished the DFS tree traversal.  */
1423           if (sp < 0 && TEST_BIT (passed, current_edge))
1424             break;
1425
1426           /* Nope, continue the traversal with the popped node.  */
1427           continue;
1428         }
1429
1430       /* Process a node.  */
1431       node = FROM_BLOCK (current_edge);
1432       child = TO_BLOCK (current_edge);
1433       SET_BIT (in_stack, node);
1434       dfs_nr[node] = ++count;
1435
1436       /* If the successor is in the stack, then we've found a loop.
1437          Mark the loop, if it is not a natural loop, then it will
1438          be rejected during the second traversal.  */
1439       if (TEST_BIT (in_stack, child))
1440         {
1441           no_loops = 0;
1442           SET_BIT (header, child);
1443           UPDATE_LOOP_RELATIONS (node, child);
1444           SET_BIT (passed, current_edge);
1445           current_edge = NEXT_OUT (current_edge);
1446           continue;
1447         }
1448
1449       /* If the child was already visited, then there is no need to visit
1450          it again.  Just update the loop relationships and restart
1451          with a new edge.  */
1452       if (dfs_nr[child])
1453         {
1454           if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child]))
1455             UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
1456           SET_BIT (passed, current_edge);
1457           current_edge = NEXT_OUT (current_edge);
1458           continue;
1459         }
1460
1461       /* Push an entry on the stack and continue DFS traversal.  */
1462       stack[++sp] = current_edge;
1463       SET_BIT (passed, current_edge);
1464       current_edge = OUT_EDGES (child);
1465
1466       /* This is temporary until haifa is converted to use rth's new
1467          cfg routines which have true entry/exit blocks and the
1468          appropriate edges from/to those blocks.
1469
1470          Generally we update dfs_nr for a node when we process its
1471          out edge.  However, if the node has no out edge then we will
1472          not set dfs_nr for that node.  This can confuse the scheduler
1473          into thinking that we have unreachable blocks, which in turn
1474          disables cross block scheduling.
1475
1476          So, if we have a node with no out edges, go ahead and mark it
1477          as reachable now.  */
1478       if (current_edge == 0)
1479         dfs_nr[child] = ++count;
1480     }
1481
1482   /* Another check for unreachable blocks.  The earlier test in
1483      is_cfg_nonregular only finds unreachable blocks that do not
1484      form a loop.
1485
1486      The DFS traversal will mark every block that is reachable from
1487      the entry node by placing a nonzero value in dfs_nr.  Thus if
1488      dfs_nr is zero for any block, then it must be unreachable.  */
1489   unreachable = 0;
1490   for (i = 0; i < n_basic_blocks; i++)
1491     if (dfs_nr[i] == 0)
1492       {
1493         unreachable = 1;
1494         break;
1495       }
1496
1497   /* Gross.  To avoid wasting memory, the second pass uses the dfs_nr array
1498      to hold degree counts.  */
1499   degree = dfs_nr;
1500
1501   /* Compute the in-degree of every block in the graph.  */
1502   for (i = 0; i < n_basic_blocks; i++)
1503     degree[i] = num_preds[i];
1504
1505   /* Do not perform region scheduling if there are any unreachable
1506      blocks.  */
1507   if (!unreachable)
1508     {
1509       if (no_loops)
1510         SET_BIT (header, 0);
1511
1512       /* Second travsersal:find reducible inner loops and topologically sort
1513          block of each region.  */
1514
1515       queue = (int *) alloca (n_basic_blocks * sizeof (int));
1516
1517       /* Find blocks which are inner loop headers.  We still have non-reducible
1518          loops to consider at this point.  */
1519       for (i = 0; i < n_basic_blocks; i++)
1520         {
1521           if (TEST_BIT (header, i) && TEST_BIT (inner, i))
1522             {
1523               int_list_ptr ps;
1524               int j;
1525
1526               /* Now check that the loop is reducible.  We do this separate
1527                  from finding inner loops so that we do not find a reducible
1528                  loop which contains an inner non-reducible loop.
1529
1530                  A simple way to find reducible/natural loops is to verify
1531                  that each block in the loop is dominated by the loop
1532                  header.
1533
1534                  If there exists a block that is not dominated by the loop
1535                  header, then the block is reachable from outside the loop
1536                  and thus the loop is not a natural loop.  */
1537               for (j = 0; j < n_basic_blocks; j++)
1538                 {
1539                   /* First identify blocks in the loop, except for the loop
1540                      entry block.  */
1541                   if (i == max_hdr[j] && i != j)
1542                     {
1543                       /* Now verify that the block is dominated by the loop
1544                          header.  */
1545                       if (!TEST_BIT (dom[j], i))
1546                         break;
1547                     }
1548                 }
1549
1550               /* If we exited the loop early, then I is the header of
1551                  a non-reducible loop and we should quit processing it
1552                  now.  */
1553               if (j != n_basic_blocks)
1554                 continue;
1555
1556               /* I is a header of an inner loop, or block 0 in a subroutine
1557                  with no loops at all.  */
1558               head = tail = -1;
1559               too_large_failure = 0;
1560               loop_head = max_hdr[i];
1561
1562               /* Decrease degree of all I's successors for topological
1563                  ordering.  */
1564               for (ps = s_succs[i]; ps; ps = ps->next)
1565                 if (INT_LIST_VAL (ps) != EXIT_BLOCK
1566                     && INT_LIST_VAL (ps) != ENTRY_BLOCK)
1567                   --degree[INT_LIST_VAL(ps)];
1568
1569               /* Estimate # insns, and count # blocks in the region.  */
1570               num_bbs = 1;
1571               num_insns = (INSN_LUID (BLOCK_END (i))
1572                            - INSN_LUID (BLOCK_HEAD (i)));
1573
1574
1575               /* Find all loop latches (blocks with back edges to the loop
1576                  header) or all the leaf blocks in the cfg has no loops.
1577
1578                  Place those blocks into the queue.  */
1579               if (no_loops)
1580                 {
1581                   for (j = 0; j < n_basic_blocks; j++)
1582                     /* Leaf nodes have only a single successor which must
1583                        be EXIT_BLOCK.  */
1584                     if (num_succs[j] == 1
1585                         && INT_LIST_VAL (s_succs[j]) == EXIT_BLOCK)
1586                       {
1587                         queue[++tail] = j;
1588                         SET_BIT (in_queue, j);
1589
1590                         if (too_large (j, &num_bbs, &num_insns))
1591                           {
1592                             too_large_failure = 1;
1593                             break;
1594                           }
1595                       }
1596                 }
1597               else
1598                 {
1599                   int_list_ptr ps;
1600
1601                   for (ps = s_preds[i]; ps; ps = ps->next)
1602                     {
1603                       node = INT_LIST_VAL (ps);
1604
1605                       if (node == ENTRY_BLOCK || node == EXIT_BLOCK)
1606                         continue;
1607
1608                       if (max_hdr[node] == loop_head && node != i)
1609                         {
1610                           /* This is a loop latch.  */
1611                           queue[++tail] = node;
1612                           SET_BIT (in_queue, node);
1613
1614                           if (too_large (node, &num_bbs, &num_insns))
1615                             {
1616                               too_large_failure = 1;
1617                               break;
1618                             }
1619                         }
1620
1621                     }
1622                 }
1623
1624               /* Now add all the blocks in the loop to the queue.
1625
1626              We know the loop is a natural loop; however the algorithm
1627              above will not always mark certain blocks as being in the
1628              loop.  Consider:
1629                 node   children
1630                  a        b,c
1631                  b        c
1632                  c        a,d
1633                  d        b
1634
1635
1636              The algorithm in the DFS traversal may not mark B & D as part
1637              of the loop (ie they will not have max_hdr set to A).
1638
1639              We know they can not be loop latches (else they would have
1640              had max_hdr set since they'd have a backedge to a dominator
1641              block).  So we don't need them on the initial queue.
1642
1643              We know they are part of the loop because they are dominated
1644              by the loop header and can be reached by a backwards walk of
1645              the edges starting with nodes on the initial queue.
1646
1647              It is safe and desirable to include those nodes in the
1648              loop/scheduling region.  To do so we would need to decrease
1649              the degree of a node if it is the target of a backedge
1650              within the loop itself as the node is placed in the queue.
1651
1652              We do not do this because I'm not sure that the actual
1653              scheduling code will properly handle this case. ?!? */
1654
1655               while (head < tail && !too_large_failure)
1656                 {
1657                   int_list_ptr ps;
1658                   child = queue[++head];
1659
1660                   for (ps = s_preds[child]; ps; ps = ps->next)
1661                     {
1662                       node = INT_LIST_VAL (ps);
1663
1664                       /* See discussion above about nodes not marked as in
1665                          this loop during the initial DFS traversal.  */
1666                       if (node == ENTRY_BLOCK || node == EXIT_BLOCK
1667                           || max_hdr[node] != loop_head)
1668                         {
1669                           tail = -1;
1670                           break;
1671                         }
1672                       else if (!TEST_BIT (in_queue, node) && node != i)
1673                         {
1674                           queue[++tail] = node;
1675                           SET_BIT (in_queue, node);
1676
1677                           if (too_large (node, &num_bbs, &num_insns))
1678                             {
1679                               too_large_failure = 1;
1680                               break;
1681                             }
1682                         }
1683                     }
1684                 }
1685
1686               if (tail >= 0 && !too_large_failure)
1687                 {
1688                   /* Place the loop header into list of region blocks.  */
1689                   degree[i] = -1;
1690                   rgn_bb_table[idx] = i;
1691                   RGN_NR_BLOCKS (nr_regions) = num_bbs;
1692                   RGN_BLOCKS (nr_regions) = idx++;
1693                   CONTAINING_RGN (i) = nr_regions;
1694                   BLOCK_TO_BB (i) = count = 0;
1695
1696                   /* Remove blocks from queue[] when their in degree
1697                      becomes zero.  Repeat until no blocks are left on the
1698                      list.  This produces a topological list of blocks in
1699                      the region.  */
1700                   while (tail >= 0)
1701                     {
1702                       int_list_ptr ps;
1703
1704                       if (head < 0)
1705                         head = tail;
1706                       child = queue[head];
1707                       if (degree[child] == 0)
1708                         {
1709                           degree[child] = -1;
1710                           rgn_bb_table[idx++] = child;
1711                           BLOCK_TO_BB (child) = ++count;
1712                           CONTAINING_RGN (child) = nr_regions;
1713                           queue[head] = queue[tail--];
1714
1715                           for (ps = s_succs[child]; ps; ps = ps->next)
1716                             if (INT_LIST_VAL (ps) != ENTRY_BLOCK
1717                                 && INT_LIST_VAL (ps) != EXIT_BLOCK)
1718                               --degree[INT_LIST_VAL (ps)];
1719                         }
1720                       else
1721                         --head;
1722                     }
1723                   ++nr_regions;
1724                 }
1725             }
1726         }
1727     }
1728
1729   /* Any block that did not end up in a region is placed into a region
1730      by itself.  */
1731   for (i = 0; i < n_basic_blocks; i++)
1732     if (degree[i] >= 0)
1733       {
1734         rgn_bb_table[idx] = i;
1735         RGN_NR_BLOCKS (nr_regions) = 1;
1736         RGN_BLOCKS (nr_regions) = idx++;
1737         CONTAINING_RGN (i) = nr_regions++;
1738         BLOCK_TO_BB (i) = 0;
1739       }
1740
1741   free (passed);
1742   free (header);
1743   free (inner);
1744   free (in_queue);
1745   free (in_stack);
1746 }
1747
1748
1749 /* Functions for regions scheduling information.  */
1750
1751 /* Compute dominators, probability, and potential-split-edges of bb.
1752    Assume that these values were already computed for bb's predecessors.  */
1753
1754 static void
1755 compute_dom_prob_ps (bb)
1756      int bb;
1757 {
1758   int nxt_in_edge, fst_in_edge, pred;
1759   int fst_out_edge, nxt_out_edge, nr_out_edges, nr_rgn_out_edges;
1760
1761   prob[bb] = 0.0;
1762   if (IS_RGN_ENTRY (bb))
1763     {
1764       BITSET_ADD (dom[bb], 0, bbset_size);
1765       prob[bb] = 1.0;
1766       return;
1767     }
1768
1769   fst_in_edge = nxt_in_edge = IN_EDGES (BB_TO_BLOCK (bb));
1770
1771   /* Intialize dom[bb] to '111..1'.  */
1772   BITSET_INVERT (dom[bb], bbset_size);
1773
1774   do
1775     {
1776       pred = FROM_BLOCK (nxt_in_edge);
1777       BITSET_INTER (dom[bb], dom[BLOCK_TO_BB (pred)], bbset_size);
1778
1779       BITSET_UNION (ancestor_edges[bb], ancestor_edges[BLOCK_TO_BB (pred)],
1780                     edgeset_size);
1781
1782       BITSET_ADD (ancestor_edges[bb], EDGE_TO_BIT (nxt_in_edge), edgeset_size);
1783
1784       nr_out_edges = 1;
1785       nr_rgn_out_edges = 0;
1786       fst_out_edge = OUT_EDGES (pred);
1787       nxt_out_edge = NEXT_OUT (fst_out_edge);
1788       BITSET_UNION (pot_split[bb], pot_split[BLOCK_TO_BB (pred)],
1789                     edgeset_size);
1790
1791       BITSET_ADD (pot_split[bb], EDGE_TO_BIT (fst_out_edge), edgeset_size);
1792
1793       /* The successor doesn't belong in the region?  */
1794       if (CONTAINING_RGN (TO_BLOCK (fst_out_edge)) !=
1795           CONTAINING_RGN (BB_TO_BLOCK (bb)))
1796         ++nr_rgn_out_edges;
1797
1798       while (fst_out_edge != nxt_out_edge)
1799         {
1800           ++nr_out_edges;
1801           /* The successor doesn't belong in the region?  */
1802           if (CONTAINING_RGN (TO_BLOCK (nxt_out_edge)) !=
1803               CONTAINING_RGN (BB_TO_BLOCK (bb)))
1804             ++nr_rgn_out_edges;
1805           BITSET_ADD (pot_split[bb], EDGE_TO_BIT (nxt_out_edge), edgeset_size);
1806           nxt_out_edge = NEXT_OUT (nxt_out_edge);
1807
1808         }
1809
1810       /* Now nr_rgn_out_edges is the number of region-exit edges from
1811          pred, and nr_out_edges will be the number of pred out edges
1812          not leaving the region.  */
1813       nr_out_edges -= nr_rgn_out_edges;
1814       if (nr_rgn_out_edges > 0)
1815         prob[bb] += 0.9 * prob[BLOCK_TO_BB (pred)] / nr_out_edges;
1816       else
1817         prob[bb] += prob[BLOCK_TO_BB (pred)] / nr_out_edges;
1818       nxt_in_edge = NEXT_IN (nxt_in_edge);
1819     }
1820   while (fst_in_edge != nxt_in_edge);
1821
1822   BITSET_ADD (dom[bb], bb, bbset_size);
1823   BITSET_DIFFER (pot_split[bb], ancestor_edges[bb], edgeset_size);
1824
1825   if (sched_verbose >= 2)
1826     fprintf (dump, ";;  bb_prob(%d, %d) = %3d\n", bb, BB_TO_BLOCK (bb), (int) (100.0 * prob[bb]));
1827 }                               /* compute_dom_prob_ps */
1828
1829 /* Functions for target info.  */
1830
1831 /* Compute in BL the list of split-edges of bb_src relatively to bb_trg.
1832    Note that bb_trg dominates bb_src.  */
1833
1834 static void
1835 split_edges (bb_src, bb_trg, bl)
1836      int bb_src;
1837      int bb_trg;
1838      edgelst *bl;
1839 {
1840   int es = edgeset_size;
1841   edgeset src = (edgeset) alloca (es * sizeof (HOST_WIDE_INT));
1842
1843   while (es--)
1844     src[es] = (pot_split[bb_src])[es];
1845   BITSET_DIFFER (src, pot_split[bb_trg], edgeset_size);
1846   extract_bitlst (src, edgeset_size, bl);
1847 }
1848
1849
1850 /* Find the valid candidate-source-blocks for the target block TRG, compute
1851    their probability, and check if they are speculative or not.
1852    For speculative sources, compute their update-blocks and split-blocks.  */
1853
1854 static void
1855 compute_trg_info (trg)
1856      int trg;
1857 {
1858   register candidate *sp;
1859   edgelst el;
1860   int check_block, update_idx;
1861   int i, j, k, fst_edge, nxt_edge;
1862
1863   /* Define some of the fields for the target bb as well.  */
1864   sp = candidate_table + trg;
1865   sp->is_valid = 1;
1866   sp->is_speculative = 0;
1867   sp->src_prob = 100;
1868
1869   for (i = trg + 1; i < current_nr_blocks; i++)
1870     {
1871       sp = candidate_table + i;
1872
1873       sp->is_valid = IS_DOMINATED (i, trg);
1874       if (sp->is_valid)
1875         {
1876           sp->src_prob = GET_SRC_PROB (i, trg);
1877           sp->is_valid = (sp->src_prob >= MIN_PROBABILITY);
1878         }
1879
1880       if (sp->is_valid)
1881         {
1882           split_edges (i, trg, &el);
1883           sp->is_speculative = (el.nr_members) ? 1 : 0;
1884           if (sp->is_speculative && !flag_schedule_speculative)
1885             sp->is_valid = 0;
1886         }
1887
1888       if (sp->is_valid)
1889         {
1890           sp->split_bbs.first_member = &bblst_table[bblst_last];
1891           sp->split_bbs.nr_members = el.nr_members;
1892           for (j = 0; j < el.nr_members; bblst_last++, j++)
1893             bblst_table[bblst_last] =
1894               TO_BLOCK (rgn_edges[el.first_member[j]]);
1895           sp->update_bbs.first_member = &bblst_table[bblst_last];
1896           update_idx = 0;
1897           for (j = 0; j < el.nr_members; j++)
1898             {
1899               check_block = FROM_BLOCK (rgn_edges[el.first_member[j]]);
1900               fst_edge = nxt_edge = OUT_EDGES (check_block);
1901               do
1902                 {
1903                   for (k = 0; k < el.nr_members; k++)
1904                     if (EDGE_TO_BIT (nxt_edge) == el.first_member[k])
1905                       break;
1906
1907                   if (k >= el.nr_members)
1908                     {
1909                       bblst_table[bblst_last++] = TO_BLOCK (nxt_edge);
1910                       update_idx++;
1911                     }
1912
1913                   nxt_edge = NEXT_OUT (nxt_edge);
1914                 }
1915               while (fst_edge != nxt_edge);
1916             }
1917           sp->update_bbs.nr_members = update_idx;
1918
1919         }
1920       else
1921         {
1922           sp->split_bbs.nr_members = sp->update_bbs.nr_members = 0;
1923
1924           sp->is_speculative = 0;
1925           sp->src_prob = 0;
1926         }
1927     }
1928 }                               /* compute_trg_info */
1929
1930
1931 /* Print candidates info, for debugging purposes.  Callable from debugger.  */
1932
1933 void
1934 debug_candidate (i)
1935      int i;
1936 {
1937   if (!candidate_table[i].is_valid)
1938     return;
1939
1940   if (candidate_table[i].is_speculative)
1941     {
1942       int j;
1943       fprintf (dump, "src b %d bb %d speculative \n", BB_TO_BLOCK (i), i);
1944
1945       fprintf (dump, "split path: ");
1946       for (j = 0; j < candidate_table[i].split_bbs.nr_members; j++)
1947         {
1948           int b = candidate_table[i].split_bbs.first_member[j];
1949
1950           fprintf (dump, " %d ", b);
1951         }
1952       fprintf (dump, "\n");
1953
1954       fprintf (dump, "update path: ");
1955       for (j = 0; j < candidate_table[i].update_bbs.nr_members; j++)
1956         {
1957           int b = candidate_table[i].update_bbs.first_member[j];
1958
1959           fprintf (dump, " %d ", b);
1960         }
1961       fprintf (dump, "\n");
1962     }
1963   else
1964     {
1965       fprintf (dump, " src %d equivalent\n", BB_TO_BLOCK (i));
1966     }
1967 }
1968
1969
1970 /* Print candidates info, for debugging purposes.  Callable from debugger.  */
1971
1972 void
1973 debug_candidates (trg)
1974      int trg;
1975 {
1976   int i;
1977
1978   fprintf (dump, "----------- candidate table: target: b=%d bb=%d ---\n",
1979            BB_TO_BLOCK (trg), trg);
1980   for (i = trg + 1; i < current_nr_blocks; i++)
1981     debug_candidate (i);
1982 }
1983
1984
1985 /* Functions for speculative scheduing.  */
1986
1987 /* Return 0 if x is a set of a register alive in the beginning of one
1988    of the split-blocks of src, otherwise return 1.  */
1989
1990 static int
1991 check_live_1 (src, x)
1992      int src;
1993      rtx x;
1994 {
1995   register int i;
1996   register int regno;
1997   register rtx reg = SET_DEST (x);
1998
1999   if (reg == 0)
2000     return 1;
2001
2002   while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
2003          || GET_CODE (reg) == SIGN_EXTRACT
2004          || GET_CODE (reg) == STRICT_LOW_PART)
2005     reg = XEXP (reg, 0);
2006
2007   if (GET_CODE (reg) == PARALLEL
2008       && GET_MODE (reg) == BLKmode)
2009     {
2010       register int i;
2011       for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
2012         if (check_live_1 (src, XVECEXP (reg, 0, i)))
2013           return 1;
2014       return 0;
2015     }
2016
2017   if (GET_CODE (reg) != REG)
2018     return 1;
2019
2020   regno = REGNO (reg);
2021
2022   if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
2023     {
2024       /* Global registers are assumed live.  */
2025       return 0;
2026     }
2027   else
2028     {
2029       if (regno < FIRST_PSEUDO_REGISTER)
2030         {
2031           /* Check for hard registers.  */
2032           int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
2033           while (--j >= 0)
2034             {
2035               for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
2036                 {
2037                   int b = candidate_table[src].split_bbs.first_member[i];
2038
2039                   if (REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start,
2040                                        regno + j))
2041                     {
2042                       return 0;
2043                     }
2044                 }
2045             }
2046         }
2047       else
2048         {
2049           /* Check for psuedo registers.  */
2050           for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
2051             {
2052               int b = candidate_table[src].split_bbs.first_member[i];
2053
2054               if (REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start, regno))
2055                 {
2056                   return 0;
2057                 }
2058             }
2059         }
2060     }
2061
2062   return 1;
2063 }
2064
2065
2066 /* If x is a set of a register R, mark that R is alive in the beginning
2067    of every update-block of src.  */
2068
2069 static void
2070 update_live_1 (src, x)
2071      int src;
2072      rtx x;
2073 {
2074   register int i;
2075   register int regno;
2076   register rtx reg = SET_DEST (x);
2077
2078   if (reg == 0)
2079     return;
2080
2081   while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
2082          || GET_CODE (reg) == SIGN_EXTRACT
2083          || GET_CODE (reg) == STRICT_LOW_PART)
2084     reg = XEXP (reg, 0);
2085
2086   if (GET_CODE (reg) == PARALLEL
2087       && GET_MODE (reg) == BLKmode)
2088     {
2089       register int i;
2090       for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
2091         update_live_1 (src, XVECEXP (reg, 0, i));
2092       return;
2093     }
2094
2095   if (GET_CODE (reg) != REG)
2096     return;
2097
2098   /* Global registers are always live, so the code below does not apply
2099      to them.  */
2100
2101   regno = REGNO (reg);
2102
2103   if (regno >= FIRST_PSEUDO_REGISTER || !global_regs[regno])
2104     {
2105       if (regno < FIRST_PSEUDO_REGISTER)
2106         {
2107           int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
2108           while (--j >= 0)
2109             {
2110               for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
2111                 {
2112                   int b = candidate_table[src].update_bbs.first_member[i];
2113
2114                   SET_REGNO_REG_SET (BASIC_BLOCK (b)->global_live_at_start,
2115                                      regno + j);
2116                 }
2117             }
2118         }
2119       else
2120         {
2121           for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
2122             {
2123               int b = candidate_table[src].update_bbs.first_member[i];
2124
2125               SET_REGNO_REG_SET (BASIC_BLOCK (b)->global_live_at_start, regno);
2126             }
2127         }
2128     }
2129 }
2130
2131
2132 /* Return 1 if insn can be speculatively moved from block src to trg,
2133    otherwise return 0.  Called before first insertion of insn to
2134    ready-list or before the scheduling.  */
2135
2136 static int
2137 check_live (insn, src)
2138      rtx insn;
2139      int src;
2140 {
2141   /* Find the registers set by instruction.  */
2142   if (GET_CODE (PATTERN (insn)) == SET
2143       || GET_CODE (PATTERN (insn)) == CLOBBER)
2144     return check_live_1 (src, PATTERN (insn));
2145   else if (GET_CODE (PATTERN (insn)) == PARALLEL)
2146     {
2147       int j;
2148       for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
2149         if ((GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
2150              || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
2151             && !check_live_1 (src, XVECEXP (PATTERN (insn), 0, j)))
2152           return 0;
2153
2154       return 1;
2155     }
2156
2157   return 1;
2158 }
2159
2160
2161 /* Update the live registers info after insn was moved speculatively from
2162    block src to trg.  */
2163
2164 static void
2165 update_live (insn, src)
2166      rtx insn;
2167      int src;
2168 {
2169   /* Find the registers set by instruction.  */
2170   if (GET_CODE (PATTERN (insn)) == SET
2171       || GET_CODE (PATTERN (insn)) == CLOBBER)
2172     update_live_1 (src, PATTERN (insn));
2173   else if (GET_CODE (PATTERN (insn)) == PARALLEL)
2174     {
2175       int j;
2176       for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
2177         if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
2178             || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
2179           update_live_1 (src, XVECEXP (PATTERN (insn), 0, j));
2180     }
2181 }
2182
2183 /* Exception Free Loads:
2184
2185    We define five classes of speculative loads: IFREE, IRISKY,
2186    PFREE, PRISKY, and MFREE.
2187
2188    IFREE loads are loads that are proved to be exception-free, just
2189    by examining the load insn.  Examples for such loads are loads
2190    from TOC and loads of global data.
2191
2192    IRISKY loads are loads that are proved to be exception-risky,
2193    just by examining the load insn.  Examples for such loads are
2194    volatile loads and loads from shared memory.
2195
2196    PFREE loads are loads for which we can prove, by examining other
2197    insns, that they are exception-free.  Currently, this class consists
2198    of loads for which we are able to find a "similar load", either in
2199    the target block, or, if only one split-block exists, in that split
2200    block.  Load2 is similar to load1 if both have same single base
2201    register.  We identify only part of the similar loads, by finding
2202    an insn upon which both load1 and load2 have a DEF-USE dependence.
2203
2204    PRISKY loads are loads for which we can prove, by examining other
2205    insns, that they are exception-risky.  Currently we have two proofs for
2206    such loads.  The first proof detects loads that are probably guarded by a
2207    test on the memory address.  This proof is based on the
2208    backward and forward data dependence information for the region.
2209    Let load-insn be the examined load.
2210    Load-insn is PRISKY iff ALL the following hold:
2211
2212    - insn1 is not in the same block as load-insn
2213    - there is a DEF-USE dependence chain (insn1, ..., load-insn)
2214    - test-insn is either a compare or a branch, not in the same block
2215      as load-insn
2216    - load-insn is reachable from test-insn
2217    - there is a DEF-USE dependence chain (insn1, ..., test-insn)
2218
2219    This proof might fail when the compare and the load are fed
2220    by an insn not in the region.  To solve this, we will add to this
2221    group all loads that have no input DEF-USE dependence.
2222
2223    The second proof detects loads that are directly or indirectly
2224    fed by a speculative load.  This proof is affected by the
2225    scheduling process.  We will use the flag  fed_by_spec_load.
2226    Initially, all insns have this flag reset.  After a speculative
2227    motion of an insn, if insn is either a load, or marked as
2228    fed_by_spec_load, we will also mark as fed_by_spec_load every
2229    insn1 for which a DEF-USE dependence (insn, insn1) exists.  A
2230    load which is fed_by_spec_load is also PRISKY.
2231
2232    MFREE (maybe-free) loads are all the remaining loads. They may be
2233    exception-free, but we cannot prove it.
2234
2235    Now, all loads in IFREE and PFREE classes are considered
2236    exception-free, while all loads in IRISKY and PRISKY classes are
2237    considered exception-risky.  As for loads in the MFREE class,
2238    these are considered either exception-free or exception-risky,
2239    depending on whether we are pessimistic or optimistic.  We have
2240    to take the pessimistic approach to assure the safety of
2241    speculative scheduling, but we can take the optimistic approach
2242    by invoking the -fsched_spec_load_dangerous option.  */
2243
2244 enum INSN_TRAP_CLASS
2245 {
2246   TRAP_FREE = 0, IFREE = 1, PFREE_CANDIDATE = 2,
2247   PRISKY_CANDIDATE = 3, IRISKY = 4, TRAP_RISKY = 5
2248 };
2249
2250 #define WORST_CLASS(class1, class2) \
2251 ((class1 > class2) ? class1 : class2)
2252
2253 /* Indexed by INSN_UID, and set if there's DEF-USE dependence between
2254    some speculatively moved load insn and this one.  */
2255 char *fed_by_spec_load;
2256 char *is_load_insn;
2257
2258 /* Non-zero if block bb_to is equal to, or reachable from block bb_from.  */
2259 #define IS_REACHABLE(bb_from, bb_to)                                    \
2260 (bb_from == bb_to                                                       \
2261    || IS_RGN_ENTRY (bb_from)                                            \
2262    || (bitset_member (ancestor_edges[bb_to],                            \
2263                       EDGE_TO_BIT (IN_EDGES (BB_TO_BLOCK (bb_from))),   \
2264                       edgeset_size)))
2265 #define FED_BY_SPEC_LOAD(insn) (fed_by_spec_load[INSN_UID (insn)])
2266 #define IS_LOAD_INSN(insn) (is_load_insn[INSN_UID (insn)])
2267
2268 /* Non-zero iff the address is comprised from at most 1 register.  */
2269 #define CONST_BASED_ADDRESS_P(x)                        \
2270   (GET_CODE (x) == REG                                  \
2271    || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS   \
2272         || (GET_CODE (x) == LO_SUM))                    \
2273        && (GET_CODE (XEXP (x, 0)) == CONST_INT          \
2274            || GET_CODE (XEXP (x, 1)) == CONST_INT)))
2275
2276 /* Turns on the fed_by_spec_load flag for insns fed by load_insn.  */
2277
2278 static void
2279 set_spec_fed (load_insn)
2280      rtx load_insn;
2281 {
2282   rtx link;
2283
2284   for (link = INSN_DEPEND (load_insn); link; link = XEXP (link, 1))
2285     if (GET_MODE (link) == VOIDmode)
2286       FED_BY_SPEC_LOAD (XEXP (link, 0)) = 1;
2287 }                               /* set_spec_fed */
2288
2289 /* On the path from the insn to load_insn_bb, find a conditional
2290 branch depending on insn, that guards the speculative load.  */
2291
2292 static int
2293 find_conditional_protection (insn, load_insn_bb)
2294      rtx insn;
2295      int load_insn_bb;
2296 {
2297   rtx link;
2298
2299   /* Iterate through DEF-USE forward dependences.  */
2300   for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
2301     {
2302       rtx next = XEXP (link, 0);
2303       if ((CONTAINING_RGN (INSN_BLOCK (next)) ==
2304            CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb)))
2305           && IS_REACHABLE (INSN_BB (next), load_insn_bb)
2306           && load_insn_bb != INSN_BB (next)
2307           && GET_MODE (link) == VOIDmode
2308           && (GET_CODE (next) == JUMP_INSN
2309               || find_conditional_protection (next, load_insn_bb)))
2310         return 1;
2311     }
2312   return 0;
2313 }                               /* find_conditional_protection */
2314
2315 /* Returns 1 if the same insn1 that participates in the computation
2316    of load_insn's address is feeding a conditional branch that is
2317    guarding on load_insn. This is true if we find a the two DEF-USE
2318    chains:
2319    insn1 -> ... -> conditional-branch
2320    insn1 -> ... -> load_insn,
2321    and if a flow path exist:
2322    insn1 -> ... -> conditional-branch -> ... -> load_insn,
2323    and if insn1 is on the path
2324    region-entry -> ... -> bb_trg -> ... load_insn.
2325
2326    Locate insn1 by climbing on LOG_LINKS from load_insn.
2327    Locate the branch by following INSN_DEPEND from insn1.  */
2328
2329 static int
2330 is_conditionally_protected (load_insn, bb_src, bb_trg)
2331      rtx load_insn;
2332      int bb_src, bb_trg;
2333 {
2334   rtx link;
2335
2336   for (link = LOG_LINKS (load_insn); link; link = XEXP (link, 1))
2337     {
2338       rtx insn1 = XEXP (link, 0);
2339
2340       /* Must be a DEF-USE dependence upon non-branch.  */
2341       if (GET_MODE (link) != VOIDmode
2342           || GET_CODE (insn1) == JUMP_INSN)
2343         continue;
2344
2345       /* Must exist a path: region-entry -> ... -> bb_trg -> ... load_insn.  */
2346       if (INSN_BB (insn1) == bb_src
2347           || (CONTAINING_RGN (INSN_BLOCK (insn1))
2348               != CONTAINING_RGN (BB_TO_BLOCK (bb_src)))
2349           || (!IS_REACHABLE (bb_trg, INSN_BB (insn1))
2350               && !IS_REACHABLE (INSN_BB (insn1), bb_trg)))
2351         continue;
2352
2353       /* Now search for the conditional-branch.  */
2354       if (find_conditional_protection (insn1, bb_src))
2355         return 1;
2356
2357       /* Recursive step: search another insn1, "above" current insn1.  */
2358       return is_conditionally_protected (insn1, bb_src, bb_trg);
2359     }
2360
2361   /* The chain does not exist.  */
2362   return 0;
2363 }                               /* is_conditionally_protected */
2364
2365 /* Returns 1 if a clue for "similar load" 'insn2' is found, and hence
2366    load_insn can move speculatively from bb_src to bb_trg.  All the
2367    following must hold:
2368
2369    (1) both loads have 1 base register (PFREE_CANDIDATEs).
2370    (2) load_insn and load1 have a def-use dependence upon
2371    the same insn 'insn1'.
2372    (3) either load2 is in bb_trg, or:
2373    - there's only one split-block, and
2374    - load1 is on the escape path, and
2375
2376    From all these we can conclude that the two loads access memory
2377    addresses that differ at most by a constant, and hence if moving
2378    load_insn would cause an exception, it would have been caused by
2379    load2 anyhow.  */
2380
2381 static int
2382 is_pfree (load_insn, bb_src, bb_trg)
2383      rtx load_insn;
2384      int bb_src, bb_trg;
2385 {
2386   rtx back_link;
2387   register candidate *candp = candidate_table + bb_src;
2388
2389   if (candp->split_bbs.nr_members != 1)
2390     /* Must have exactly one escape block.  */
2391     return 0;
2392
2393   for (back_link = LOG_LINKS (load_insn);
2394        back_link; back_link = XEXP (back_link, 1))
2395     {
2396       rtx insn1 = XEXP (back_link, 0);
2397
2398       if (GET_MODE (back_link) == VOIDmode)
2399         {
2400           /* Found a DEF-USE dependence (insn1, load_insn).  */
2401           rtx fore_link;
2402
2403           for (fore_link = INSN_DEPEND (insn1);
2404                fore_link; fore_link = XEXP (fore_link, 1))
2405             {
2406               rtx insn2 = XEXP (fore_link, 0);
2407               if (GET_MODE (fore_link) == VOIDmode)
2408                 {
2409                   /* Found a DEF-USE dependence (insn1, insn2).  */
2410                   if (haifa_classify_insn (insn2) != PFREE_CANDIDATE)
2411                     /* insn2 not guaranteed to be a 1 base reg load.  */
2412                     continue;
2413
2414                   if (INSN_BB (insn2) == bb_trg)
2415                     /* insn2 is the similar load, in the target block.  */
2416                     return 1;
2417
2418                   if (*(candp->split_bbs.first_member) == INSN_BLOCK (insn2))
2419                     /* insn2 is a similar load, in a split-block.  */
2420                     return 1;
2421                 }
2422             }
2423         }
2424     }
2425
2426   /* Couldn't find a similar load.  */
2427   return 0;
2428 }                               /* is_pfree */
2429
2430 /* Returns a class that insn with GET_DEST(insn)=x may belong to,
2431    as found by analyzing insn's expression.  */
2432
2433 static int
2434 may_trap_exp (x, is_store)
2435      rtx x;
2436      int is_store;
2437 {
2438   enum rtx_code code;
2439
2440   if (x == 0)
2441     return TRAP_FREE;
2442   code = GET_CODE (x);
2443   if (is_store)
2444     {
2445       if (code == MEM)
2446         return TRAP_RISKY;
2447       else
2448         return TRAP_FREE;
2449     }
2450   if (code == MEM)
2451     {
2452       /* The insn uses memory:  a volatile load.  */
2453       if (MEM_VOLATILE_P (x))
2454         return IRISKY;
2455       /* An exception-free load.  */
2456       if (!may_trap_p (x))
2457         return IFREE;
2458       /* A load with 1 base register, to be further checked.  */
2459       if (CONST_BASED_ADDRESS_P (XEXP (x, 0)))
2460         return PFREE_CANDIDATE;
2461       /* No info on the load, to be further checked.  */
2462       return PRISKY_CANDIDATE;
2463     }
2464   else
2465     {
2466       const char *fmt;
2467       int i, insn_class = TRAP_FREE;
2468
2469       /* Neither store nor load, check if it may cause a trap.  */
2470       if (may_trap_p (x))
2471         return TRAP_RISKY;
2472       /* Recursive step: walk the insn...  */
2473       fmt = GET_RTX_FORMAT (code);
2474       for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2475         {
2476           if (fmt[i] == 'e')
2477             {
2478               int tmp_class = may_trap_exp (XEXP (x, i), is_store);
2479               insn_class = WORST_CLASS (insn_class, tmp_class);
2480             }
2481           else if (fmt[i] == 'E')
2482             {
2483               int j;
2484               for (j = 0; j < XVECLEN (x, i); j++)
2485                 {
2486                   int tmp_class = may_trap_exp (XVECEXP (x, i, j), is_store);
2487                   insn_class = WORST_CLASS (insn_class, tmp_class);
2488                   if (insn_class == TRAP_RISKY || insn_class == IRISKY)
2489                     break;
2490                 }
2491             }
2492           if (insn_class == TRAP_RISKY || insn_class == IRISKY)
2493             break;
2494         }
2495       return insn_class;
2496     }
2497 }                               /* may_trap_exp */
2498
2499
2500 /* Classifies insn for the purpose of verifying that it can be
2501    moved speculatively, by examining it's patterns, returning:
2502    TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
2503    TRAP_FREE: non-load insn.
2504    IFREE: load from a globaly safe location.
2505    IRISKY: volatile load.
2506    PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
2507    being either PFREE or PRISKY.  */
2508
2509 static int
2510 haifa_classify_insn (insn)
2511      rtx insn;
2512 {
2513   rtx pat = PATTERN (insn);
2514   int tmp_class = TRAP_FREE;
2515   int insn_class = TRAP_FREE;
2516   enum rtx_code code;
2517
2518   if (GET_CODE (pat) == PARALLEL)
2519     {
2520       int i, len = XVECLEN (pat, 0);
2521
2522       for (i = len - 1; i >= 0; i--)
2523         {
2524           code = GET_CODE (XVECEXP (pat, 0, i));
2525           switch (code)
2526             {
2527             case CLOBBER:
2528               /* Test if it is a 'store'.  */
2529               tmp_class = may_trap_exp (XEXP (XVECEXP (pat, 0, i), 0), 1);
2530               break;
2531             case SET:
2532               /* Test if it is a store.  */
2533               tmp_class = may_trap_exp (SET_DEST (XVECEXP (pat, 0, i)), 1);
2534               if (tmp_class == TRAP_RISKY)
2535                 break;
2536               /* Test if it is a load.  */
2537               tmp_class =
2538                 WORST_CLASS (tmp_class,
2539                            may_trap_exp (SET_SRC (XVECEXP (pat, 0, i)), 0));
2540               break;
2541             case TRAP_IF:
2542               tmp_class = TRAP_RISKY;
2543               break;
2544             default:;
2545             }
2546           insn_class = WORST_CLASS (insn_class, tmp_class);
2547           if (insn_class == TRAP_RISKY || insn_class == IRISKY)
2548             break;
2549         }
2550     }
2551   else
2552     {
2553       code = GET_CODE (pat);
2554       switch (code)
2555         {
2556         case CLOBBER:
2557           /* Test if it is a 'store'.  */
2558           tmp_class = may_trap_exp (XEXP (pat, 0), 1);
2559           break;
2560         case SET:
2561           /* Test if it is a store.  */
2562           tmp_class = may_trap_exp (SET_DEST (pat), 1);
2563           if (tmp_class == TRAP_RISKY)
2564             break;
2565           /* Test if it is a load.  */
2566           tmp_class =
2567             WORST_CLASS (tmp_class,
2568                          may_trap_exp (SET_SRC (pat), 0));
2569           break;
2570         case TRAP_IF:
2571           tmp_class = TRAP_RISKY;
2572           break;
2573         default:;
2574         }
2575       insn_class = tmp_class;
2576     }
2577
2578   return insn_class;
2579
2580 }                               /* haifa_classify_insn */
2581
2582 /* Return 1 if load_insn is prisky (i.e. if load_insn is fed by
2583    a load moved speculatively, or if load_insn is protected by
2584    a compare on load_insn's address).  */
2585
2586 static int
2587 is_prisky (load_insn, bb_src, bb_trg)
2588      rtx load_insn;
2589      int bb_src, bb_trg;
2590 {
2591   if (FED_BY_SPEC_LOAD (load_insn))
2592     return 1;
2593
2594   if (LOG_LINKS (load_insn) == NULL)
2595     /* Dependence may 'hide' out of the region.  */
2596     return 1;
2597
2598   if (is_conditionally_protected (load_insn, bb_src, bb_trg))
2599     return 1;
2600
2601   return 0;
2602 }                               /* is_prisky */
2603
2604 /* Insn is a candidate to be moved speculatively from bb_src to bb_trg.
2605    Return 1 if insn is exception-free (and the motion is valid)
2606    and 0 otherwise.  */
2607
2608 static int
2609 is_exception_free (insn, bb_src, bb_trg)
2610      rtx insn;
2611      int bb_src, bb_trg;
2612 {
2613   int insn_class = haifa_classify_insn (insn);
2614
2615   /* Handle non-load insns.  */
2616   switch (insn_class)
2617     {
2618     case TRAP_FREE:
2619       return 1;
2620     case TRAP_RISKY:
2621       return 0;
2622     default:;
2623     }
2624
2625   /* Handle loads.  */
2626   if (!flag_schedule_speculative_load)
2627     return 0;
2628   IS_LOAD_INSN (insn) = 1;
2629   switch (insn_class)
2630     {
2631     case IFREE:
2632       return (1);
2633     case IRISKY:
2634       return 0;
2635     case PFREE_CANDIDATE:
2636       if (is_pfree (insn, bb_src, bb_trg))
2637         return 1;
2638       /* Don't 'break' here: PFREE-candidate is also PRISKY-candidate.  */
2639     case PRISKY_CANDIDATE:
2640       if (!flag_schedule_speculative_load_dangerous
2641           || is_prisky (insn, bb_src, bb_trg))
2642         return 0;
2643       break;
2644     default:;
2645     }
2646
2647   return flag_schedule_speculative_load_dangerous;
2648 }                               /* is_exception_free */
2649
2650
2651 /* Process an insn's memory dependencies.  There are four kinds of
2652    dependencies:
2653
2654    (0) read dependence: read follows read
2655    (1) true dependence: read follows write
2656    (2) anti dependence: write follows read
2657    (3) output dependence: write follows write
2658
2659    We are careful to build only dependencies which actually exist, and
2660    use transitivity to avoid building too many links.  */
2661 \f
2662 /* Return the INSN_LIST containing INSN in LIST, or NULL
2663    if LIST does not contain INSN.  */
2664
2665 HAIFA_INLINE static rtx
2666 find_insn_list (insn, list)
2667      rtx insn;
2668      rtx list;
2669 {
2670   while (list)
2671     {
2672       if (XEXP (list, 0) == insn)
2673         return list;
2674       list = XEXP (list, 1);
2675     }
2676   return 0;
2677 }
2678
2679
2680 /* Return 1 if the pair (insn, x) is found in (LIST, LIST1), or 0
2681    otherwise.  */
2682
2683 HAIFA_INLINE static char
2684 find_insn_mem_list (insn, x, list, list1)
2685      rtx insn, x;
2686      rtx list, list1;
2687 {
2688   while (list)
2689     {
2690       if (XEXP (list, 0) == insn
2691           && XEXP (list1, 0) == x)
2692         return 1;
2693       list = XEXP (list, 1);
2694       list1 = XEXP (list1, 1);
2695     }
2696   return 0;
2697 }
2698
2699
2700 /* Compute the function units used by INSN.  This caches the value
2701    returned by function_units_used.  A function unit is encoded as the
2702    unit number if the value is non-negative and the compliment of a
2703    mask if the value is negative.  A function unit index is the
2704    non-negative encoding.  */
2705
2706 HAIFA_INLINE static int
2707 insn_unit (insn)
2708      rtx insn;
2709 {
2710   register int unit = INSN_UNIT (insn);
2711
2712   if (unit == 0)
2713     {
2714       recog_memoized (insn);
2715
2716       /* A USE insn, or something else we don't need to understand.
2717          We can't pass these directly to function_units_used because it will
2718          trigger a fatal error for unrecognizable insns.  */
2719       if (INSN_CODE (insn) < 0)
2720         unit = -1;
2721       else
2722         {
2723           unit = function_units_used (insn);
2724           /* Increment non-negative values so we can cache zero.  */
2725           if (unit >= 0)
2726             unit++;
2727         }
2728       /* We only cache 16 bits of the result, so if the value is out of
2729          range, don't cache it.  */
2730       if (FUNCTION_UNITS_SIZE < HOST_BITS_PER_SHORT
2731           || unit >= 0
2732           || (unit & ~((1 << (HOST_BITS_PER_SHORT - 1)) - 1)) == 0)
2733         INSN_UNIT (insn) = unit;
2734     }
2735   return (unit > 0 ? unit - 1 : unit);
2736 }
2737
2738 /* Compute the blockage range for executing INSN on UNIT.  This caches
2739    the value returned by the blockage_range_function for the unit.
2740    These values are encoded in an int where the upper half gives the
2741    minimum value and the lower half gives the maximum value.  */
2742
2743 HAIFA_INLINE static unsigned int
2744 blockage_range (unit, insn)
2745      int unit;
2746      rtx insn;
2747 {
2748   unsigned int blockage = INSN_BLOCKAGE (insn);
2749   unsigned int range;
2750
2751   if ((int) UNIT_BLOCKED (blockage) != unit + 1)
2752     {
2753       range = function_units[unit].blockage_range_function (insn);
2754       /* We only cache the blockage range for one unit and then only if
2755          the values fit.  */
2756       if (HOST_BITS_PER_INT >= UNIT_BITS + 2 * BLOCKAGE_BITS)
2757         INSN_BLOCKAGE (insn) = ENCODE_BLOCKAGE (unit + 1, range);
2758     }
2759   else
2760     range = BLOCKAGE_RANGE (blockage);
2761
2762   return range;
2763 }
2764
2765 /* A vector indexed by function unit instance giving the last insn to use
2766    the unit.  The value of the function unit instance index for unit U
2767    instance I is (U + I * FUNCTION_UNITS_SIZE).  */
2768 static rtx unit_last_insn[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY];
2769
2770 /* A vector indexed by function unit instance giving the minimum time when
2771    the unit will unblock based on the maximum blockage cost.  */
2772 static int unit_tick[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY];
2773
2774 /* A vector indexed by function unit number giving the number of insns
2775    that remain to use the unit.  */
2776 static int unit_n_insns[FUNCTION_UNITS_SIZE];
2777
2778 /* Reset the function unit state to the null state.  */
2779
2780 static void
2781 clear_units ()
2782 {
2783   bzero ((char *) unit_last_insn, sizeof (unit_last_insn));
2784   bzero ((char *) unit_tick, sizeof (unit_tick));
2785   bzero ((char *) unit_n_insns, sizeof (unit_n_insns));
2786 }
2787
2788 /* Return the issue-delay of an insn.  */
2789
2790 HAIFA_INLINE static int
2791 insn_issue_delay (insn)
2792      rtx insn;
2793 {
2794   int i, delay = 0;
2795   int unit = insn_unit (insn);
2796
2797   /* Efficiency note: in fact, we are working 'hard' to compute a
2798      value that was available in md file, and is not available in
2799      function_units[] structure.  It would be nice to have this
2800      value there, too.  */
2801   if (unit >= 0)
2802     {
2803       if (function_units[unit].blockage_range_function &&
2804           function_units[unit].blockage_function)
2805         delay = function_units[unit].blockage_function (insn, insn);
2806     }
2807   else
2808     for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
2809       if ((unit & 1) != 0 && function_units[i].blockage_range_function
2810           && function_units[i].blockage_function)
2811         delay = MAX (delay, function_units[i].blockage_function (insn, insn));
2812
2813   return delay;
2814 }
2815
2816 /* Return the actual hazard cost of executing INSN on the unit UNIT,
2817    instance INSTANCE at time CLOCK if the previous actual hazard cost
2818    was COST.  */
2819
2820 HAIFA_INLINE static int
2821 actual_hazard_this_instance (unit, instance, insn, clock, cost)
2822      int unit, instance, clock, cost;
2823      rtx insn;
2824 {
2825   int tick = unit_tick[instance]; /* Issue time of the last issued insn.  */
2826
2827   if (tick - clock > cost)
2828     {
2829       /* The scheduler is operating forward, so unit's last insn is the
2830          executing insn and INSN is the candidate insn.  We want a
2831          more exact measure of the blockage if we execute INSN at CLOCK
2832          given when we committed the execution of the unit's last insn.
2833
2834          The blockage value is given by either the unit's max blockage
2835          constant, blockage range function, or blockage function.  Use
2836          the most exact form for the given unit.  */
2837
2838       if (function_units[unit].blockage_range_function)
2839         {
2840           if (function_units[unit].blockage_function)
2841             tick += (function_units[unit].blockage_function
2842                      (unit_last_insn[instance], insn)
2843                      - function_units[unit].max_blockage);
2844           else
2845             tick += ((int) MAX_BLOCKAGE_COST (blockage_range (unit, insn))
2846                      - function_units[unit].max_blockage);
2847         }
2848       if (tick - clock > cost)
2849         cost = tick - clock;
2850     }
2851   return cost;
2852 }
2853
2854 /* Record INSN as having begun execution on the units encoded by UNIT at
2855    time CLOCK.  */
2856
2857 HAIFA_INLINE static void
2858 schedule_unit (unit, insn, clock)
2859      int unit, clock;
2860      rtx insn;
2861 {
2862   int i;
2863
2864   if (unit >= 0)
2865     {
2866       int instance = unit;
2867 #if MAX_MULTIPLICITY > 1
2868       /* Find the first free instance of the function unit and use that
2869          one.  We assume that one is free.  */
2870       for (i = function_units[unit].multiplicity - 1; i > 0; i--)
2871         {
2872           if (!actual_hazard_this_instance (unit, instance, insn, clock, 0))
2873             break;
2874           instance += FUNCTION_UNITS_SIZE;
2875         }
2876 #endif
2877       unit_last_insn[instance] = insn;
2878       unit_tick[instance] = (clock + function_units[unit].max_blockage);
2879     }
2880   else
2881     for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
2882       if ((unit & 1) != 0)
2883         schedule_unit (i, insn, clock);
2884 }
2885
2886 /* Return the actual hazard cost of executing INSN on the units encoded by
2887    UNIT at time CLOCK if the previous actual hazard cost was COST.  */
2888
2889 HAIFA_INLINE static int
2890 actual_hazard (unit, insn, clock, cost)
2891      int unit, clock, cost;
2892      rtx insn;
2893 {
2894   int i;
2895
2896   if (unit >= 0)
2897     {
2898       /* Find the instance of the function unit with the minimum hazard.  */
2899       int instance = unit;
2900       int best_cost = actual_hazard_this_instance (unit, instance, insn,
2901                                                    clock, cost);
2902 #if MAX_MULTIPLICITY > 1
2903       int this_cost;
2904
2905       if (best_cost > cost)
2906         {
2907           for (i = function_units[unit].multiplicity - 1; i > 0; i--)
2908             {
2909               instance += FUNCTION_UNITS_SIZE;
2910               this_cost = actual_hazard_this_instance (unit, instance, insn,
2911                                                        clock, cost);
2912               if (this_cost < best_cost)
2913                 {
2914                   best_cost = this_cost;
2915                   if (this_cost <= cost)
2916                     break;
2917                 }
2918             }
2919         }
2920 #endif
2921       cost = MAX (cost, best_cost);
2922     }
2923   else
2924     for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
2925       if ((unit & 1) != 0)
2926         cost = actual_hazard (i, insn, clock, cost);
2927
2928   return cost;
2929 }
2930
2931 /* Return the potential hazard cost of executing an instruction on the
2932    units encoded by UNIT if the previous potential hazard cost was COST.
2933    An insn with a large blockage time is chosen in preference to one
2934    with a smaller time; an insn that uses a unit that is more likely
2935    to be used is chosen in preference to one with a unit that is less
2936    used.  We are trying to minimize a subsequent actual hazard.  */
2937
2938 HAIFA_INLINE static int
2939 potential_hazard (unit, insn, cost)
2940      int unit, cost;
2941      rtx insn;
2942 {
2943   int i, ncost;
2944   unsigned int minb, maxb;
2945
2946   if (unit >= 0)
2947     {
2948       minb = maxb = function_units[unit].max_blockage;
2949       if (maxb > 1)
2950         {
2951           if (function_units[unit].blockage_range_function)
2952             {
2953               maxb = minb = blockage_range (unit, insn);
2954               maxb = MAX_BLOCKAGE_COST (maxb);
2955               minb = MIN_BLOCKAGE_COST (minb);
2956             }
2957
2958           if (maxb > 1)
2959             {
2960               /* Make the number of instructions left dominate.  Make the
2961                  minimum delay dominate the maximum delay.  If all these
2962                  are the same, use the unit number to add an arbitrary
2963                  ordering.  Other terms can be added.  */
2964               ncost = minb * 0x40 + maxb;
2965               ncost *= (unit_n_insns[unit] - 1) * 0x1000 + unit;
2966               if (ncost > cost)
2967                 cost = ncost;
2968             }
2969         }
2970     }
2971   else
2972     for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
2973       if ((unit & 1) != 0)
2974         cost = potential_hazard (i, insn, cost);
2975
2976   return cost;
2977 }
2978
2979 /* Compute cost of executing INSN given the dependence LINK on the insn USED.
2980    This is the number of cycles between instruction issue and
2981    instruction results.  */
2982
2983 HAIFA_INLINE static int
2984 insn_cost (insn, link, used)
2985      rtx insn, link, used;
2986 {
2987   register int cost = INSN_COST (insn);
2988
2989   if (cost == 0)
2990     {
2991       recog_memoized (insn);
2992
2993       /* A USE insn, or something else we don't need to understand.
2994          We can't pass these directly to result_ready_cost because it will
2995          trigger a fatal error for unrecognizable insns.  */
2996       if (INSN_CODE (insn) < 0)
2997         {
2998           INSN_COST (insn) = 1;
2999           return 1;
3000         }
3001       else
3002         {
3003           cost = result_ready_cost (insn);
3004
3005           if (cost < 1)
3006             cost = 1;
3007
3008           INSN_COST (insn) = cost;
3009         }
3010     }
3011
3012   /* In this case estimate cost without caring how insn is used.  */
3013   if (link == 0 && used == 0)
3014     return cost;
3015
3016   /* A USE insn should never require the value used to be computed.  This
3017      allows the computation of a function's result and parameter values to
3018      overlap the return and call.  */
3019   recog_memoized (used);
3020   if (INSN_CODE (used) < 0)
3021     LINK_COST_FREE (link) = 1;
3022
3023   /* If some dependencies vary the cost, compute the adjustment.  Most
3024      commonly, the adjustment is complete: either the cost is ignored
3025      (in the case of an output- or anti-dependence), or the cost is
3026      unchanged.  These values are cached in the link as LINK_COST_FREE
3027      and LINK_COST_ZERO.  */
3028
3029   if (LINK_COST_FREE (link))
3030     cost = 0;
3031 #ifdef ADJUST_COST
3032   else if (!LINK_COST_ZERO (link))
3033     {
3034       int ncost = cost;
3035
3036       ADJUST_COST (used, link, insn, ncost);
3037       if (ncost < 1)
3038         {
3039           LINK_COST_FREE (link) = 1;
3040           ncost = 0;
3041         }
3042       if (cost == ncost)
3043         LINK_COST_ZERO (link) = 1;
3044       cost = ncost;
3045     }
3046 #endif
3047   return cost;
3048 }
3049
3050 /* Compute the priority number for INSN.  */
3051
3052 static int
3053 priority (insn)
3054      rtx insn;
3055 {
3056   int this_priority;
3057   rtx link;
3058
3059   if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
3060     return 0;
3061
3062   if ((this_priority = INSN_PRIORITY (insn)) == 0)
3063     {
3064       if (INSN_DEPEND (insn) == 0)
3065         this_priority = insn_cost (insn, 0, 0);
3066       else
3067         for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
3068           {
3069             rtx next;
3070             int next_priority;
3071
3072             if (RTX_INTEGRATED_P (link))
3073               continue;
3074
3075             next = XEXP (link, 0);
3076
3077             /* Critical path is meaningful in block boundaries only.  */
3078             if (INSN_BLOCK (next) != INSN_BLOCK (insn))
3079               continue;
3080
3081             next_priority = insn_cost (insn, link, next) + priority (next);
3082             if (next_priority > this_priority)
3083               this_priority = next_priority;
3084           }
3085       INSN_PRIORITY (insn) = this_priority;
3086     }
3087   return this_priority;
3088 }
3089 \f
3090
3091 /* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
3092    them to the unused_*_list variables, so that they can be reused.  */
3093
3094 static void
3095 free_pending_lists ()
3096 {
3097   if (current_nr_blocks <= 1)
3098     {
3099       free_INSN_LIST_list (&pending_read_insns);
3100       free_INSN_LIST_list (&pending_write_insns);
3101       free_EXPR_LIST_list (&pending_read_mems);
3102       free_EXPR_LIST_list (&pending_write_mems);
3103     }
3104   else
3105     {
3106       /* Interblock scheduling.  */
3107       int bb;
3108
3109       for (bb = 0; bb < current_nr_blocks; bb++)
3110         {
3111           free_INSN_LIST_list (&bb_pending_read_insns[bb]);
3112           free_INSN_LIST_list (&bb_pending_write_insns[bb]);
3113           free_EXPR_LIST_list (&bb_pending_read_mems[bb]);
3114           free_EXPR_LIST_list (&bb_pending_write_mems[bb]);
3115         }
3116     }
3117 }
3118
3119 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
3120    The MEM is a memory reference contained within INSN, which we are saving
3121    so that we can do memory aliasing on it.  */
3122
3123 static void
3124 add_insn_mem_dependence (insn_list, mem_list, insn, mem)
3125      rtx *insn_list, *mem_list, insn, mem;
3126 {
3127   register rtx link;
3128
3129   link = alloc_INSN_LIST (insn, *insn_list);
3130   *insn_list = link;
3131
3132   link = alloc_EXPR_LIST (VOIDmode, mem, *mem_list);
3133   *mem_list = link;
3134
3135   pending_lists_length++;
3136 }
3137 \f
3138
3139 /* Make a dependency between every memory reference on the pending lists
3140    and INSN, thus flushing the pending lists.  If ONLY_WRITE, don't flush
3141    the read list.  */
3142
3143 static void
3144 flush_pending_lists (insn, only_write)
3145      rtx insn;
3146      int only_write;
3147 {
3148   rtx u;
3149   rtx link;
3150
3151   while (pending_read_insns && ! only_write)
3152     {
3153       add_dependence (insn, XEXP (pending_read_insns, 0), REG_DEP_ANTI);
3154
3155       link = pending_read_insns;
3156       pending_read_insns = XEXP (pending_read_insns, 1);
3157       free_INSN_LIST_node (link);
3158
3159       link = pending_read_mems;
3160       pending_read_mems = XEXP (pending_read_mems, 1);
3161       free_EXPR_LIST_node (link);
3162     }
3163   while (pending_write_insns)
3164     {
3165       add_dependence (insn, XEXP (pending_write_insns, 0), REG_DEP_ANTI);
3166
3167       link = pending_write_insns;
3168       pending_write_insns = XEXP (pending_write_insns, 1);
3169       free_INSN_LIST_node (link);
3170
3171       link = pending_write_mems;
3172       pending_write_mems = XEXP (pending_write_mems, 1);
3173       free_EXPR_LIST_node (link);
3174     }
3175   pending_lists_length = 0;
3176
3177   /* last_pending_memory_flush is now a list of insns.  */
3178   for (u = last_pending_memory_flush; u; u = XEXP (u, 1))
3179     add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3180
3181   free_INSN_LIST_list (&last_pending_memory_flush);
3182   last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX);
3183 }
3184
3185 /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
3186    rtx, X, creating all dependencies generated by the write to the
3187    destination of X, and reads of everything mentioned.  */
3188
3189 static void
3190 sched_analyze_1 (x, insn)
3191      rtx x;
3192      rtx insn;
3193 {
3194   register int regno;
3195   register rtx dest = XEXP (x, 0);
3196   enum rtx_code code = GET_CODE (x);
3197
3198   if (dest == 0)
3199     return;
3200
3201   if (GET_CODE (dest) == PARALLEL
3202       && GET_MODE (dest) == BLKmode)
3203     {
3204       register int i;
3205       for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
3206         sched_analyze_1 (XVECEXP (dest, 0, i), insn);
3207       if (GET_CODE (x) == SET)
3208         sched_analyze_2 (SET_SRC (x), insn);
3209       return;
3210     }
3211
3212   while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
3213       || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
3214     {
3215       if (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
3216         {
3217           /* The second and third arguments are values read by this insn.  */
3218           sched_analyze_2 (XEXP (dest, 1), insn);
3219           sched_analyze_2 (XEXP (dest, 2), insn);
3220         }
3221       dest = XEXP (dest, 0);
3222     }
3223
3224   if (GET_CODE (dest) == REG)
3225     {
3226       register int i;
3227
3228       regno = REGNO (dest);
3229
3230       /* A hard reg in a wide mode may really be multiple registers.
3231          If so, mark all of them just like the first.  */
3232       if (regno < FIRST_PSEUDO_REGISTER)
3233         {
3234           i = HARD_REGNO_NREGS (regno, GET_MODE (dest));
3235           while (--i >= 0)
3236             {
3237               rtx u;
3238
3239               for (u = reg_last_uses[regno + i]; u; u = XEXP (u, 1))
3240                 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3241
3242               for (u = reg_last_sets[regno + i]; u; u = XEXP (u, 1))
3243                 add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
3244
3245               /* Clobbers need not be ordered with respect to one
3246                  another, but sets must be ordered with respect to a
3247                  pending clobber.  */
3248               if (code == SET)
3249                 {
3250                   free_INSN_LIST_list (&reg_last_uses[regno + i]);
3251                   for (u = reg_last_clobbers[regno + i]; u; u = XEXP (u, 1))
3252                     add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
3253                   SET_REGNO_REG_SET (reg_pending_sets, regno + i);
3254                 }
3255               else
3256                 SET_REGNO_REG_SET (reg_pending_clobbers, regno + i);
3257
3258               /* Function calls clobber all call_used regs.  */
3259               if (global_regs[regno + i]
3260                   || (code == SET && call_used_regs[regno + i]))
3261                 for (u = last_function_call; u; u = XEXP (u, 1))
3262                   add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3263             }
3264         }
3265       else
3266         {
3267           rtx u;
3268
3269           for (u = reg_last_uses[regno]; u; u = XEXP (u, 1))
3270             add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3271
3272           for (u = reg_last_sets[regno]; u; u = XEXP (u, 1))
3273             add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
3274
3275           if (code == SET)
3276             {
3277               free_INSN_LIST_list (&reg_last_uses[regno]);
3278               for (u = reg_last_clobbers[regno]; u; u = XEXP (u, 1))
3279                 add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
3280               SET_REGNO_REG_SET (reg_pending_sets, regno);
3281             }
3282           else
3283             SET_REGNO_REG_SET (reg_pending_clobbers, regno);
3284
3285           /* Pseudos that are REG_EQUIV to something may be replaced
3286              by that during reloading.  We need only add dependencies for
3287              the address in the REG_EQUIV note.  */
3288           if (!reload_completed
3289               && reg_known_equiv_p[regno]
3290               && GET_CODE (reg_known_value[regno]) == MEM)
3291             sched_analyze_2 (XEXP (reg_known_value[regno], 0), insn);
3292
3293           /* Don't let it cross a call after scheduling if it doesn't
3294              already cross one.  */
3295
3296           if (REG_N_CALLS_CROSSED (regno) == 0)
3297             for (u = last_function_call; u; u = XEXP (u, 1))
3298               add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3299         }
3300     }
3301   else if (GET_CODE (dest) == MEM)
3302     {
3303       /* Writing memory.  */
3304
3305       if (pending_lists_length > 32)
3306         {
3307           /* Flush all pending reads and writes to prevent the pending lists
3308              from getting any larger.  Insn scheduling runs too slowly when
3309              these lists get long.  The number 32 was chosen because it
3310              seems like a reasonable number.  When compiling GCC with itself,
3311              this flush occurs 8 times for sparc, and 10 times for m88k using
3312              the number 32.  */
3313           flush_pending_lists (insn, 0);
3314         }
3315       else
3316         {
3317           rtx u;
3318           rtx pending, pending_mem;
3319
3320           pending = pending_read_insns;
3321           pending_mem = pending_read_mems;
3322           while (pending)
3323             {
3324               if (anti_dependence (XEXP (pending_mem, 0), dest))
3325                 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
3326
3327               pending = XEXP (pending, 1);
3328               pending_mem = XEXP (pending_mem, 1);
3329             }
3330
3331           pending = pending_write_insns;
3332           pending_mem = pending_write_mems;
3333           while (pending)
3334             {
3335               if (output_dependence (XEXP (pending_mem, 0), dest))
3336                 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
3337
3338               pending = XEXP (pending, 1);
3339               pending_mem = XEXP (pending_mem, 1);
3340             }
3341
3342           for (u = last_pending_memory_flush; u; u = XEXP (u, 1))
3343             add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3344
3345           add_insn_mem_dependence (&pending_write_insns, &pending_write_mems,
3346                                    insn, dest);
3347         }
3348       sched_analyze_2 (XEXP (dest, 0), insn);
3349     }
3350
3351   /* Analyze reads.  */
3352   if (GET_CODE (x) == SET)
3353     sched_analyze_2 (SET_SRC (x), insn);
3354 }
3355
3356 /* Analyze the uses of memory and registers in rtx X in INSN.  */
3357
3358 static void
3359 sched_analyze_2 (x, insn)
3360      rtx x;
3361      rtx insn;
3362 {
3363   register int i;
3364   register int j;
3365   register enum rtx_code code;
3366   register const char *fmt;
3367
3368   if (x == 0)
3369     return;
3370
3371   code = GET_CODE (x);
3372
3373   switch (code)
3374     {
3375     case CONST_INT:
3376     case CONST_DOUBLE:
3377     case SYMBOL_REF:
3378     case CONST:
3379     case LABEL_REF:
3380       /* Ignore constants.  Note that we must handle CONST_DOUBLE here
3381          because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but
3382          this does not mean that this insn is using cc0.  */
3383       return;
3384
3385 #ifdef HAVE_cc0
3386     case CC0:
3387       {
3388         rtx link, prev;
3389
3390         /* User of CC0 depends on immediately preceding insn.  */
3391         SCHED_GROUP_P (insn) = 1;
3392
3393         /* There may be a note before this insn now, but all notes will
3394            be removed before we actually try to schedule the insns, so
3395            it won't cause a problem later.  We must avoid it here though.  */
3396         prev = prev_nonnote_insn (insn);
3397
3398         /* Make a copy of all dependencies on the immediately previous insn,
3399            and add to this insn.  This is so that all the dependencies will
3400            apply to the group.  Remove an explicit dependence on this insn
3401            as SCHED_GROUP_P now represents it.  */
3402
3403         if (find_insn_list (prev, LOG_LINKS (insn)))
3404           remove_dependence (insn, prev);
3405
3406         for (link = LOG_LINKS (prev); link; link = XEXP (link, 1))
3407           add_dependence (insn, XEXP (link, 0), REG_NOTE_KIND (link));
3408
3409         return;
3410       }
3411 #endif
3412
3413     case REG:
3414       {
3415         rtx u;
3416         int regno = REGNO (x);
3417         if (regno < FIRST_PSEUDO_REGISTER)
3418           {
3419             int i;
3420
3421             i = HARD_REGNO_NREGS (regno, GET_MODE (x));
3422             while (--i >= 0)
3423               {
3424                 reg_last_uses[regno + i]
3425                   = alloc_INSN_LIST (insn, reg_last_uses[regno + i]);
3426
3427                 for (u = reg_last_sets[regno + i]; u; u = XEXP (u, 1))
3428                   add_dependence (insn, XEXP (u, 0), 0);
3429
3430                 /* ??? This should never happen.  */
3431                 for (u = reg_last_clobbers[regno + i]; u; u = XEXP (u, 1))
3432                   add_dependence (insn, XEXP (u, 0), 0);
3433
3434                 if ((call_used_regs[regno + i] || global_regs[regno + i]))
3435                   /* Function calls clobber all call_used regs.  */
3436                   for (u = last_function_call; u; u = XEXP (u, 1))
3437                     add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3438               }
3439           }
3440         else
3441           {
3442             reg_last_uses[regno] = alloc_INSN_LIST (insn,
3443                                                     reg_last_uses[regno]);
3444
3445             for (u = reg_last_sets[regno]; u; u = XEXP (u, 1))
3446               add_dependence (insn, XEXP (u, 0), 0);
3447
3448             /* ??? This should never happen.  */
3449             for (u = reg_last_clobbers[regno]; u; u = XEXP (u, 1))
3450               add_dependence (insn, XEXP (u, 0), 0);
3451
3452             /* Pseudos that are REG_EQUIV to something may be replaced
3453                by that during reloading.  We need only add dependencies for
3454                the address in the REG_EQUIV note.  */
3455             if (!reload_completed
3456                 && reg_known_equiv_p[regno]
3457                 && GET_CODE (reg_known_value[regno]) == MEM)
3458               sched_analyze_2 (XEXP (reg_known_value[regno], 0), insn);
3459
3460             /* If the register does not already cross any calls, then add this
3461                insn to the sched_before_next_call list so that it will still
3462                not cross calls after scheduling.  */
3463             if (REG_N_CALLS_CROSSED (regno) == 0)
3464               add_dependence (sched_before_next_call, insn, REG_DEP_ANTI);
3465           }
3466         return;
3467       }
3468
3469     case MEM:
3470       {
3471         /* Reading memory.  */
3472         rtx u;
3473         rtx pending, pending_mem;
3474
3475         pending = pending_read_insns;
3476         pending_mem = pending_read_mems;
3477         while (pending)
3478           {
3479             if (read_dependence (XEXP (pending_mem, 0), x))
3480               add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
3481
3482             pending = XEXP (pending, 1);
3483             pending_mem = XEXP (pending_mem, 1);
3484           }
3485
3486         pending = pending_write_insns;
3487         pending_mem = pending_write_mems;
3488         while (pending)
3489           {
3490             if (true_dependence (XEXP (pending_mem, 0), VOIDmode,
3491                 x, rtx_varies_p))
3492               add_dependence (insn, XEXP (pending, 0), 0);
3493
3494             pending = XEXP (pending, 1);
3495             pending_mem = XEXP (pending_mem, 1);
3496           }
3497
3498         for (u = last_pending_memory_flush; u; u = XEXP (u, 1))
3499           add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3500
3501         /* Always add these dependencies to pending_reads, since
3502            this insn may be followed by a write.  */
3503         add_insn_mem_dependence (&pending_read_insns, &pending_read_mems,
3504                                  insn, x);
3505
3506         /* Take advantage of tail recursion here.  */
3507         sched_analyze_2 (XEXP (x, 0), insn);
3508         return;
3509       }
3510
3511     /* Force pending stores to memory in case a trap handler needs them.  */
3512     case TRAP_IF:
3513       flush_pending_lists (insn, 1);
3514       break;
3515
3516     case ASM_OPERANDS:
3517     case ASM_INPUT:
3518     case UNSPEC_VOLATILE:
3519       {
3520         rtx u;
3521
3522         /* Traditional and volatile asm instructions must be considered to use
3523            and clobber all hard registers, all pseudo-registers and all of
3524            memory.  So must TRAP_IF and UNSPEC_VOLATILE operations.
3525
3526            Consider for instance a volatile asm that changes the fpu rounding
3527            mode.  An insn should not be moved across this even if it only uses
3528            pseudo-regs because it might give an incorrectly rounded result.  */
3529         if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
3530           {
3531             int max_reg = max_reg_num ();
3532             for (i = 0; i < max_reg; i++)
3533               {
3534                 for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
3535                   add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3536                 free_INSN_LIST_list (&reg_last_uses[i]);
3537
3538                 for (u = reg_last_sets[i]; u; u = XEXP (u, 1))
3539                   add_dependence (insn, XEXP (u, 0), 0);
3540
3541                 for (u = reg_last_clobbers[i]; u; u = XEXP (u, 1))
3542                   add_dependence (insn, XEXP (u, 0), 0);
3543               }
3544             reg_pending_sets_all = 1;
3545
3546             flush_pending_lists (insn, 0);
3547           }
3548
3549         /* For all ASM_OPERANDS, we must traverse the vector of input operands.
3550            We can not just fall through here since then we would be confused
3551            by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
3552            traditional asms unlike their normal usage.  */
3553
3554         if (code == ASM_OPERANDS)
3555           {
3556             for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
3557               sched_analyze_2 (ASM_OPERANDS_INPUT (x, j), insn);
3558             return;
3559           }
3560         break;
3561       }
3562
3563     case PRE_DEC:
3564     case POST_DEC:
3565     case PRE_INC:
3566     case POST_INC:
3567       /* These both read and modify the result.  We must handle them as writes
3568          to get proper dependencies for following instructions.  We must handle
3569          them as reads to get proper dependencies from this to previous
3570          instructions.  Thus we need to pass them to both sched_analyze_1
3571          and sched_analyze_2.  We must call sched_analyze_2 first in order
3572          to get the proper antecedent for the read.  */
3573       sched_analyze_2 (XEXP (x, 0), insn);
3574       sched_analyze_1 (x, insn);
3575       return;
3576
3577     default:
3578       break;
3579     }
3580
3581   /* Other cases: walk the insn.  */
3582   fmt = GET_RTX_FORMAT (code);
3583   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3584     {
3585       if (fmt[i] == 'e')
3586         sched_analyze_2 (XEXP (x, i), insn);
3587       else if (fmt[i] == 'E')
3588         for (j = 0; j < XVECLEN (x, i); j++)
3589           sched_analyze_2 (XVECEXP (x, i, j), insn);
3590     }
3591 }
3592
3593 /* Analyze an INSN with pattern X to find all dependencies.  */
3594
3595 static void
3596 sched_analyze_insn (x, insn, loop_notes)
3597      rtx x, insn;
3598      rtx loop_notes;
3599 {
3600   register RTX_CODE code = GET_CODE (x);
3601   rtx link;
3602   int maxreg = max_reg_num ();
3603   int i;
3604
3605   if (code == SET || code == CLOBBER)
3606     sched_analyze_1 (x, insn);
3607   else if (code == PARALLEL)
3608     {
3609       register int i;
3610       for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
3611         {
3612           code = GET_CODE (XVECEXP (x, 0, i));
3613           if (code == SET || code == CLOBBER)
3614             sched_analyze_1 (XVECEXP (x, 0, i), insn);
3615           else
3616             sched_analyze_2 (XVECEXP (x, 0, i), insn);
3617         }
3618     }
3619   else
3620     sched_analyze_2 (x, insn);
3621
3622   /* Mark registers CLOBBERED or used by called function.  */
3623   if (GET_CODE (insn) == CALL_INSN)
3624     for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
3625       {
3626         if (GET_CODE (XEXP (link, 0)) == CLOBBER)
3627           sched_analyze_1 (XEXP (link, 0), insn);
3628         else
3629           sched_analyze_2 (XEXP (link, 0), insn);
3630       }
3631
3632   /* If there is a {LOOP,EHREGION}_{BEG,END} note in the middle of a basic
3633      block, then we must be sure that no instructions are scheduled across it.
3634      Otherwise, the reg_n_refs info (which depends on loop_depth) would
3635      become incorrect.  */
3636
3637   if (loop_notes)
3638     {
3639       int max_reg = max_reg_num ();
3640       int schedule_barrier_found = 0;
3641       rtx link;
3642
3643       /* Update loop_notes with any notes from this insn.  Also determine
3644          if any of the notes on the list correspond to instruction scheduling
3645          barriers (loop, eh & setjmp notes, but not range notes.  */
3646       link = loop_notes;
3647       while (XEXP (link, 1))
3648         {
3649           if (INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_BEG
3650               || INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_END
3651               || INTVAL (XEXP (link, 0)) == NOTE_INSN_EH_REGION_BEG
3652               || INTVAL (XEXP (link, 0)) == NOTE_INSN_EH_REGION_END
3653               || INTVAL (XEXP (link, 0)) == NOTE_INSN_SETJMP)
3654             schedule_barrier_found = 1;
3655
3656           link = XEXP (link, 1);
3657         }
3658       XEXP (link, 1) = REG_NOTES (insn);
3659       REG_NOTES (insn) = loop_notes;
3660
3661       /* Add dependencies if a scheduling barrier was found.  */
3662       if (schedule_barrier_found)
3663         {
3664           for (i = 0; i < max_reg; i++)
3665             {
3666               rtx u;
3667               for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
3668                 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3669               free_INSN_LIST_list (&reg_last_uses[i]);
3670
3671               for (u = reg_last_sets[i]; u; u = XEXP (u, 1))
3672                 add_dependence (insn, XEXP (u, 0), 0);
3673
3674               for (u = reg_last_clobbers[i]; u; u = XEXP (u, 1))
3675                 add_dependence (insn, XEXP (u, 0), 0);
3676             }
3677           reg_pending_sets_all = 1;
3678
3679           flush_pending_lists (insn, 0);
3680         }
3681
3682     }
3683
3684   /* Accumulate clobbers until the next set so that it will be output dependent
3685      on all of them.  At the next set we can clear the clobber list, since
3686      subsequent sets will be output dependent on it.  */
3687   EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i,
3688                              {
3689                                free_INSN_LIST_list (&reg_last_sets[i]);
3690                                free_INSN_LIST_list (&reg_last_clobbers[i]);
3691                                reg_last_sets[i]
3692                                  = alloc_INSN_LIST (insn, NULL_RTX);
3693                              });
3694   EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i,
3695                              {
3696                                reg_last_clobbers[i]
3697                                  = alloc_INSN_LIST (insn,
3698                                                     reg_last_clobbers[i]);
3699                              });
3700   CLEAR_REG_SET (reg_pending_sets);
3701   CLEAR_REG_SET (reg_pending_clobbers);
3702
3703   if (reg_pending_sets_all)
3704     {
3705       for (i = 0; i < maxreg; i++)
3706         {
3707           free_INSN_LIST_list (&reg_last_sets[i]);
3708           reg_last_sets[i] = alloc_INSN_LIST (insn, NULL_RTX);
3709         }
3710
3711       reg_pending_sets_all = 0;
3712     }
3713
3714   /* Handle function calls and function returns created by the epilogue
3715      threading code.  */
3716   if (GET_CODE (insn) == CALL_INSN || GET_CODE (insn) == JUMP_INSN)
3717     {
3718       rtx dep_insn;
3719       rtx prev_dep_insn;
3720
3721       /* When scheduling instructions, we make sure calls don't lose their
3722          accompanying USE insns by depending them one on another in order.
3723
3724          Also, we must do the same thing for returns created by the epilogue
3725          threading code.  Note this code works only in this special case,
3726          because other passes make no guarantee that they will never emit
3727          an instruction between a USE and a RETURN.  There is such a guarantee
3728          for USE instructions immediately before a call.  */
3729
3730       prev_dep_insn = insn;
3731       dep_insn = PREV_INSN (insn);
3732       while (GET_CODE (dep_insn) == INSN
3733              && GET_CODE (PATTERN (dep_insn)) == USE
3734              && GET_CODE (XEXP (PATTERN (dep_insn), 0)) == REG)
3735         {
3736           SCHED_GROUP_P (prev_dep_insn) = 1;
3737
3738           /* Make a copy of all dependencies on dep_insn, and add to insn.
3739              This is so that all of the dependencies will apply to the
3740              group.  */
3741
3742           for (link = LOG_LINKS (dep_insn); link; link = XEXP (link, 1))
3743             add_dependence (insn, XEXP (link, 0), REG_NOTE_KIND (link));
3744
3745           prev_dep_insn = dep_insn;
3746           dep_insn = PREV_INSN (dep_insn);
3747         }
3748     }
3749 }
3750
3751 /* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
3752    for every dependency.  */
3753
3754 static void
3755 sched_analyze (head, tail)
3756      rtx head, tail;
3757 {
3758   register rtx insn;
3759   register rtx u;
3760   rtx loop_notes = 0;
3761
3762   for (insn = head;; insn = NEXT_INSN (insn))
3763     {
3764       if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
3765         {
3766           /* Clear out the stale LOG_LINKS from flow.  */
3767           free_INSN_LIST_list (&LOG_LINKS (insn));
3768
3769           /* Make each JUMP_INSN a scheduling barrier for memory
3770              references.  */
3771           if (GET_CODE (insn) == JUMP_INSN)
3772             last_pending_memory_flush
3773               = alloc_INSN_LIST (insn, last_pending_memory_flush);
3774           sched_analyze_insn (PATTERN (insn), insn, loop_notes);
3775           loop_notes = 0;
3776         }
3777       else if (GET_CODE (insn) == CALL_INSN)
3778         {
3779           rtx x;
3780           register int i;
3781
3782           CANT_MOVE (insn) = 1;
3783
3784           /* Clear out the stale LOG_LINKS from flow.  */
3785           free_INSN_LIST_list (&LOG_LINKS (insn));
3786
3787           /* Any instruction using a hard register which may get clobbered
3788              by a call needs to be marked as dependent on this call.
3789              This prevents a use of a hard return reg from being moved
3790              past a void call (i.e. it does not explicitly set the hard
3791              return reg).  */
3792
3793           /* If this call is followed by a NOTE_INSN_SETJMP, then assume that
3794              all registers, not just hard registers, may be clobbered by this
3795              call.  */
3796
3797           /* Insn, being a CALL_INSN, magically depends on
3798              `last_function_call' already.  */
3799
3800           if (NEXT_INSN (insn) && GET_CODE (NEXT_INSN (insn)) == NOTE
3801               && NOTE_LINE_NUMBER (NEXT_INSN (insn)) == NOTE_INSN_SETJMP)
3802             {
3803               int max_reg = max_reg_num ();
3804               for (i = 0; i < max_reg; i++)
3805                 {
3806                   for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
3807                     add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3808                   free_INSN_LIST_list (&reg_last_uses[i]);
3809
3810                   for (u = reg_last_sets[i]; u; u = XEXP (u, 1))
3811                     add_dependence (insn, XEXP (u, 0), 0);
3812
3813                   for (u = reg_last_clobbers[i]; u; u = XEXP (u, 1))
3814                     add_dependence (insn, XEXP (u, 0), 0);
3815                 }
3816               reg_pending_sets_all = 1;
3817
3818               /* Add a pair of REG_SAVE_NOTEs which we will later
3819                  convert back into a NOTE_INSN_SETJMP note.  See
3820                  reemit_notes for why we use a pair of NOTEs.  */
3821               REG_NOTES (insn) = alloc_EXPR_LIST (REG_SAVE_NOTE,
3822                                                   GEN_INT (0),
3823                                                   REG_NOTES (insn));
3824               REG_NOTES (insn) = alloc_EXPR_LIST (REG_SAVE_NOTE,
3825                                                   GEN_INT (NOTE_INSN_SETJMP),
3826                                                   REG_NOTES (insn));
3827             }
3828           else
3829             {
3830               for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3831                 if (call_used_regs[i] || global_regs[i])
3832                   {
3833                     for (u = reg_last_uses[i]; u; u = XEXP (u, 1))
3834                       add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3835
3836                     for (u = reg_last_sets[i]; u; u = XEXP (u, 1))
3837                       add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
3838
3839                     SET_REGNO_REG_SET (reg_pending_clobbers, i);
3840                   }
3841             }
3842
3843           /* For each insn which shouldn't cross a call, add a dependence
3844              between that insn and this call insn.  */
3845           x = LOG_LINKS (sched_before_next_call);
3846           while (x)
3847             {
3848               add_dependence (insn, XEXP (x, 0), REG_DEP_ANTI);
3849               x = XEXP (x, 1);
3850             }
3851           free_INSN_LIST_list (&LOG_LINKS (sched_before_next_call));
3852
3853           sched_analyze_insn (PATTERN (insn), insn, loop_notes);
3854           loop_notes = 0;
3855
3856           /* In the absence of interprocedural alias analysis, we must flush
3857              all pending reads and writes, and start new dependencies starting
3858              from here.  But only flush writes for constant calls (which may
3859              be passed a pointer to something we haven't written yet).  */
3860           flush_pending_lists (insn, CONST_CALL_P (insn));
3861
3862           /* Depend this function call (actually, the user of this
3863              function call) on all hard register clobberage.  */
3864
3865           /* last_function_call is now a list of insns.  */
3866           free_INSN_LIST_list(&last_function_call);
3867           last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
3868         }
3869
3870       /* See comments on reemit_notes as to why we do this.
3871          ??? Actually, the reemit_notes just say what is done, not why.  */
3872
3873       else if (GET_CODE (insn) == NOTE
3874                && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_START
3875                    || NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_END))
3876         {
3877           loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE, NOTE_RANGE_INFO (insn),
3878                                         loop_notes);
3879           loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE,
3880                                         GEN_INT (NOTE_LINE_NUMBER (insn)),
3881                                         loop_notes);
3882         }
3883       else if (GET_CODE (insn) == NOTE
3884                && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
3885                    || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END
3886                    || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
3887                    || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END
3888                    || (NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP
3889                        && GET_CODE (PREV_INSN (insn)) != CALL_INSN)))
3890         {
3891           rtx rtx_region;
3892
3893           if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
3894               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END)
3895             rtx_region = GEN_INT (NOTE_EH_HANDLER (insn));
3896           else
3897             rtx_region = GEN_INT (0);
3898
3899           loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE,
3900                                         rtx_region,
3901                                         loop_notes);
3902           loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE,
3903                                         GEN_INT (NOTE_LINE_NUMBER (insn)),
3904                                         loop_notes);
3905           CONST_CALL_P (loop_notes) = CONST_CALL_P (insn);
3906         }
3907
3908       if (insn == tail)
3909         return;
3910     }
3911   abort ();
3912 }
3913 \f
3914 /* Macros and functions for keeping the priority queue sorted, and
3915    dealing with queueing and dequeueing of instructions.  */
3916
3917 #define SCHED_SORT(READY, N_READY)                                   \
3918 do { if ((N_READY) == 2)                                             \
3919        swap_sort (READY, N_READY);                                   \
3920      else if ((N_READY) > 2)                                         \
3921          qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); }  \
3922 while (0)
3923
3924 /* Returns a positive value if x is preferred; returns a negative value if
3925    y is preferred.  Should never return 0, since that will make the sort
3926    unstable.  */
3927
3928 static int
3929 rank_for_schedule (x, y)
3930      const PTR x;
3931      const PTR y;
3932 {
3933   rtx tmp = *(rtx *)y;
3934   rtx tmp2 = *(rtx *)x;
3935   rtx link;
3936   int tmp_class, tmp2_class, depend_count1, depend_count2;
3937   int val, priority_val, spec_val, prob_val, weight_val;
3938
3939
3940   /* Prefer insn with higher priority.  */
3941   priority_val = INSN_PRIORITY (tmp2) - INSN_PRIORITY (tmp);
3942   if (priority_val)
3943     return priority_val;
3944
3945   /* Prefer an insn with smaller contribution to registers-pressure.  */
3946   if (!reload_completed &&
3947       (weight_val = INSN_REG_WEIGHT (tmp) - INSN_REG_WEIGHT (tmp2)))
3948     return (weight_val);
3949
3950   /* Some comparison make sense in interblock scheduling only.  */
3951   if (INSN_BB (tmp) != INSN_BB (tmp2))
3952     {
3953       /* Prefer an inblock motion on an interblock motion.  */
3954       if ((INSN_BB (tmp2) == target_bb) && (INSN_BB (tmp) != target_bb))
3955         return 1;
3956       if ((INSN_BB (tmp) == target_bb) && (INSN_BB (tmp2) != target_bb))
3957         return -1;
3958
3959       /* Prefer a useful motion on a speculative one.  */
3960       if ((spec_val = IS_SPECULATIVE_INSN (tmp) - IS_SPECULATIVE_INSN (tmp2)))
3961         return (spec_val);
3962
3963       /* Prefer a more probable (speculative) insn.  */
3964       prob_val = INSN_PROBABILITY (tmp2) - INSN_PROBABILITY (tmp);
3965       if (prob_val)
3966         return (prob_val);
3967     }
3968
3969   /* Compare insns based on their relation to the last-scheduled-insn.  */
3970   if (last_scheduled_insn)
3971     {
3972       /* Classify the instructions into three classes:
3973          1) Data dependent on last schedule insn.
3974          2) Anti/Output dependent on last scheduled insn.
3975          3) Independent of last scheduled insn, or has latency of one.
3976          Choose the insn from the highest numbered class if different.  */
3977       link = find_insn_list (tmp, INSN_DEPEND (last_scheduled_insn));
3978       if (link == 0 || insn_cost (last_scheduled_insn, link, tmp) == 1)
3979         tmp_class = 3;
3980       else if (REG_NOTE_KIND (link) == 0)       /* Data dependence.  */
3981         tmp_class = 1;
3982       else
3983         tmp_class = 2;
3984
3985       link = find_insn_list (tmp2, INSN_DEPEND (last_scheduled_insn));
3986       if (link == 0 || insn_cost (last_scheduled_insn, link, tmp2) == 1)
3987         tmp2_class = 3;
3988       else if (REG_NOTE_KIND (link) == 0)       /* Data dependence.  */
3989         tmp2_class = 1;
3990       else
3991         tmp2_class = 2;
3992
3993       if ((val = tmp2_class - tmp_class))
3994         return val;
3995     }
3996
3997   /* Prefer the insn which has more later insns that depend on it.
3998      This gives the scheduler more freedom when scheduling later
3999      instructions at the expense of added register pressure.  */
4000   depend_count1 = 0;
4001   for (link = INSN_DEPEND (tmp); link; link = XEXP (link, 1))
4002     depend_count1++;
4003
4004   depend_count2 = 0;
4005   for (link = INSN_DEPEND (tmp2); link; link = XEXP (link, 1))
4006     depend_count2++;
4007
4008   val = depend_count2 - depend_count1;
4009   if (val)
4010     return val;
4011
4012   /* If insns are equally good, sort by INSN_LUID (original insn order),
4013      so that we make the sort stable.  This minimizes instruction movement,
4014      thus minimizing sched's effect on debugging and cross-jumping.  */
4015   return INSN_LUID (tmp) - INSN_LUID (tmp2);
4016 }
4017
4018 /* Resort the array A in which only element at index N may be out of order.  */
4019
4020 HAIFA_INLINE static void
4021 swap_sort (a, n)
4022      rtx *a;
4023      int n;
4024 {
4025   rtx insn = a[n - 1];
4026   int i = n - 2;
4027
4028   while (i >= 0 && rank_for_schedule (a + i, &insn) >= 0)
4029     {
4030       a[i + 1] = a[i];
4031       i -= 1;
4032     }
4033   a[i + 1] = insn;
4034 }
4035
4036 static int max_priority;
4037
4038 /* Add INSN to the insn queue so that it can be executed at least
4039    N_CYCLES after the currently executing insn.  Preserve insns
4040    chain for debugging purposes.  */
4041
4042 HAIFA_INLINE static void
4043 queue_insn (insn, n_cycles)
4044      rtx insn;
4045      int n_cycles;
4046 {
4047   int next_q = NEXT_Q_AFTER (q_ptr, n_cycles);
4048   rtx link = alloc_INSN_LIST (insn, insn_queue[next_q]);
4049   insn_queue[next_q] = link;
4050   q_size += 1;
4051
4052   if (sched_verbose >= 2)
4053     {
4054       fprintf (dump, ";;\t\tReady-->Q: insn %d: ", INSN_UID (insn));
4055
4056       if (INSN_BB (insn) != target_bb)
4057         fprintf (dump, "(b%d) ", INSN_BLOCK (insn));
4058
4059       fprintf (dump, "queued for %d cycles.\n", n_cycles);
4060     }
4061
4062 }
4063
4064 /* PREV is an insn that is ready to execute.  Adjust its priority if that
4065    will help shorten or lengthen register lifetimes as appropriate.  Also
4066    provide a hook for the target to tweek itself.  */
4067
4068 HAIFA_INLINE static void
4069 adjust_priority (prev)
4070      rtx prev ATTRIBUTE_UNUSED;
4071 {
4072   /* ??? There used to be code here to try and estimate how an insn
4073      affected register lifetimes, but it did it by looking at REG_DEAD
4074      notes, which we removed in schedule_region.  Nor did it try to
4075      take into account register pressure or anything useful like that.
4076
4077      Revisit when we have a machine model to work with and not before.  */
4078
4079 #ifdef ADJUST_PRIORITY
4080   ADJUST_PRIORITY (prev);
4081 #endif
4082 }
4083
4084 /* Clock at which the previous instruction was issued.  */
4085 static int last_clock_var;
4086
4087 /* INSN is the "currently executing insn".  Launch each insn which was
4088    waiting on INSN.  READY is a vector of insns which are ready to fire.
4089    N_READY is the number of elements in READY.  CLOCK is the current
4090    cycle.  */
4091
4092 static int
4093 schedule_insn (insn, ready, n_ready, clock)
4094      rtx insn;
4095      rtx *ready;
4096      int n_ready;
4097      int clock;
4098 {
4099   rtx link;
4100   int unit;
4101
4102   unit = insn_unit (insn);
4103
4104   if (sched_verbose >= 2)
4105     {
4106       fprintf (dump, ";;\t\t--> scheduling insn <<<%d>>> on unit ",
4107                INSN_UID (insn));
4108       insn_print_units (insn);
4109       fprintf (dump, "\n");
4110     }
4111
4112   if (sched_verbose && unit == -1)
4113     visualize_no_unit (insn);
4114
4115   if (MAX_BLOCKAGE > 1 || issue_rate > 1 || sched_verbose)
4116     schedule_unit (unit, insn, clock);
4117
4118   if (INSN_DEPEND (insn) == 0)
4119     return n_ready;
4120
4121   /* This is used by the function adjust_priority above.  */
4122   if (n_ready > 0)
4123     max_priority = MAX (INSN_PRIORITY (ready[0]), INSN_PRIORITY (insn));
4124   else
4125     max_priority = INSN_PRIORITY (insn);
4126
4127   for (link = INSN_DEPEND (insn); link != 0; link = XEXP (link, 1))
4128     {
4129       rtx next = XEXP (link, 0);
4130       int cost = insn_cost (insn, link, next);
4131
4132       INSN_TICK (next) = MAX (INSN_TICK (next), clock + cost);
4133
4134       if ((INSN_DEP_COUNT (next) -= 1) == 0)
4135         {
4136           int effective_cost = INSN_TICK (next) - clock;
4137
4138           /* For speculative insns, before inserting to ready/queue,
4139              check live, exception-free, and issue-delay.  */
4140           if (INSN_BB (next) != target_bb
4141               && (!IS_VALID (INSN_BB (next))
4142                   || CANT_MOVE (next)
4143                   || (IS_SPECULATIVE_INSN (next)
4144                       && (insn_issue_delay (next) > 3
4145                           || !check_live (next, INSN_BB (next))
4146                  || !is_exception_free (next, INSN_BB (next), target_bb)))))
4147             continue;
4148
4149           if (sched_verbose >= 2)
4150             {
4151               fprintf (dump, ";;\t\tdependences resolved: insn %d ",
4152                        INSN_UID (next));
4153
4154               if (current_nr_blocks > 1 && INSN_BB (next) != target_bb)
4155                 fprintf (dump, "/b%d ", INSN_BLOCK (next));
4156
4157               if (effective_cost < 1)
4158                 fprintf (dump, "into ready\n");
4159               else
4160                 fprintf (dump, "into queue with cost=%d\n", effective_cost);
4161             }
4162
4163           /* Adjust the priority of NEXT and either put it on the ready
4164              list or queue it.  */
4165           adjust_priority (next);
4166           if (effective_cost < 1)
4167             ready[n_ready++] = next;
4168           else
4169             queue_insn (next, effective_cost);
4170         }
4171     }
4172
4173   /* Annotate the instruction with issue information -- TImode
4174      indicates that the instruction is expected not to be able
4175      to issue on the same cycle as the previous insn.  A machine
4176      may use this information to decide how the instruction should
4177      be aligned.  */
4178   if (reload_completed && issue_rate > 1)
4179     {
4180       PUT_MODE (insn, clock > last_clock_var ? TImode : VOIDmode);
4181       last_clock_var = clock;
4182     }
4183
4184   return n_ready;
4185 }
4186
4187 /* Functions for handling of notes.  */
4188
4189 /* Delete notes beginning with INSN and put them in the chain
4190    of notes ended by NOTE_LIST.
4191    Returns the insn following the notes.  */
4192
4193 static rtx
4194 unlink_other_notes (insn, tail)
4195      rtx insn, tail;
4196 {
4197   rtx prev = PREV_INSN (insn);
4198
4199   while (insn != tail && GET_CODE (insn) == NOTE)
4200     {
4201       rtx next = NEXT_INSN (insn);
4202       /* Delete the note from its current position.  */
4203       if (prev)
4204         NEXT_INSN (prev) = next;
4205       if (next)
4206         PREV_INSN (next) = prev;
4207
4208       /* See sched_analyze to see how these are handled.  */
4209       if (NOTE_LINE_NUMBER (insn) != NOTE_INSN_SETJMP
4210           && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG
4211           && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_END
4212           && NOTE_LINE_NUMBER (insn) != NOTE_INSN_RANGE_START
4213           && NOTE_LINE_NUMBER (insn) != NOTE_INSN_RANGE_END
4214           && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_BEG
4215           && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_END)
4216         {
4217           /* Insert the note at the end of the notes list.  */
4218           PREV_INSN (insn) = note_list;
4219           if (note_list)
4220             NEXT_INSN (note_list) = insn;
4221           note_list = insn;
4222         }
4223
4224       insn = next;
4225     }
4226   return insn;
4227 }
4228
4229 /* Delete line notes beginning with INSN. Record line-number notes so
4230    they can be reused.  Returns the insn following the notes.  */
4231
4232 static rtx
4233 unlink_line_notes (insn, tail)
4234      rtx insn, tail;
4235 {
4236   rtx prev = PREV_INSN (insn);
4237
4238   while (insn != tail && GET_CODE (insn) == NOTE)
4239     {
4240       rtx next = NEXT_INSN (insn);
4241
4242       if (write_symbols != NO_DEBUG && NOTE_LINE_NUMBER (insn) > 0)
4243         {
4244           /* Delete the note from its current position.  */
4245           if (prev)
4246             NEXT_INSN (prev) = next;
4247           if (next)
4248             PREV_INSN (next) = prev;
4249
4250           /* Record line-number notes so they can be reused.  */
4251           LINE_NOTE (insn) = insn;
4252         }
4253       else
4254         prev = insn;
4255
4256       insn = next;
4257     }
4258   return insn;
4259 }
4260
4261 /* Return the head and tail pointers of BB.  */
4262
4263 HAIFA_INLINE static void
4264 get_block_head_tail (bb, headp, tailp)
4265      int bb;
4266      rtx *headp;
4267      rtx *tailp;
4268 {
4269
4270   rtx head;
4271   rtx tail;
4272   int b;
4273
4274   b = BB_TO_BLOCK (bb);
4275
4276   /* HEAD and TAIL delimit the basic block being scheduled.  */
4277   head = BLOCK_HEAD (b);
4278   tail = BLOCK_END (b);
4279
4280   /* Don't include any notes or labels at the beginning of the
4281      basic block, or notes at the ends of basic blocks.  */
4282   while (head != tail)
4283     {
4284       if (GET_CODE (head) == NOTE)
4285         head = NEXT_INSN (head);
4286       else if (GET_CODE (tail) == NOTE)
4287         tail = PREV_INSN (tail);
4288       else if (GET_CODE (head) == CODE_LABEL)
4289         head = NEXT_INSN (head);
4290       else
4291         break;
4292     }
4293
4294   *headp = head;
4295   *tailp = tail;
4296 }
4297
4298 /* Delete line notes from bb. Save them so they can be later restored
4299    (in restore_line_notes ()).  */
4300
4301 static void
4302 rm_line_notes (bb)
4303      int bb;
4304 {
4305   rtx next_tail;
4306   rtx tail;
4307   rtx head;
4308   rtx insn;
4309
4310   get_block_head_tail (bb, &head, &tail);
4311
4312   if (head == tail
4313       && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
4314     return;
4315
4316   next_tail = NEXT_INSN (tail);
4317   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
4318     {
4319       rtx prev;
4320
4321       /* Farm out notes, and maybe save them in NOTE_LIST.
4322          This is needed to keep the debugger from
4323          getting completely deranged.  */
4324       if (GET_CODE (insn) == NOTE)
4325         {
4326           prev = insn;
4327           insn = unlink_line_notes (insn, next_tail);
4328
4329           if (prev == tail)
4330             abort ();
4331           if (prev == head)
4332             abort ();
4333           if (insn == next_tail)
4334             abort ();
4335         }
4336     }
4337 }
4338
4339 /* Save line number notes for each insn in bb.  */
4340
4341 static void
4342 save_line_notes (bb)
4343      int bb;
4344 {
4345   rtx head, tail;
4346   rtx next_tail;
4347
4348   /* We must use the true line number for the first insn in the block
4349      that was computed and saved at the start of this pass.  We can't
4350      use the current line number, because scheduling of the previous
4351      block may have changed the current line number.  */
4352
4353   rtx line = line_note_head[BB_TO_BLOCK (bb)];
4354   rtx insn;
4355
4356   get_block_head_tail (bb, &head, &tail);
4357   next_tail = NEXT_INSN (tail);
4358
4359   for (insn = BLOCK_HEAD (BB_TO_BLOCK (bb));
4360        insn != next_tail;
4361        insn = NEXT_INSN (insn))
4362     if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
4363       line = insn;
4364     else
4365       LINE_NOTE (insn) = line;
4366 }
4367
4368
4369 /* After bb was scheduled, insert line notes into the insns list.  */
4370
4371 static void
4372 restore_line_notes (bb)
4373      int bb;
4374 {
4375   rtx line, note, prev, new;
4376   int added_notes = 0;
4377   int b;
4378   rtx head, next_tail, insn;
4379
4380   b = BB_TO_BLOCK (bb);
4381
4382   head = BLOCK_HEAD (b);
4383   next_tail = NEXT_INSN (BLOCK_END (b));
4384
4385   /* Determine the current line-number.  We want to know the current
4386      line number of the first insn of the block here, in case it is
4387      different from the true line number that was saved earlier.  If
4388      different, then we need a line number note before the first insn
4389      of this block.  If it happens to be the same, then we don't want to
4390      emit another line number note here.  */
4391   for (line = head; line; line = PREV_INSN (line))
4392     if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
4393       break;
4394
4395   /* Walk the insns keeping track of the current line-number and inserting
4396      the line-number notes as needed.  */
4397   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
4398     if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
4399       line = insn;
4400   /* This used to emit line number notes before every non-deleted note.
4401      However, this confuses a debugger, because line notes not separated
4402      by real instructions all end up at the same address.  I can find no
4403      use for line number notes before other notes, so none are emitted.  */
4404     else if (GET_CODE (insn) != NOTE
4405              && (note = LINE_NOTE (insn)) != 0
4406              && note != line
4407              && (line == 0
4408                  || NOTE_LINE_NUMBER (note) != NOTE_LINE_NUMBER (line)
4409                  || NOTE_SOURCE_FILE (note) != NOTE_SOURCE_FILE (line)))
4410       {
4411         line = note;
4412         prev = PREV_INSN (insn);
4413         if (LINE_NOTE (note))
4414           {
4415             /* Re-use the original line-number note.  */
4416             LINE_NOTE (note) = 0;
4417             PREV_INSN (note) = prev;
4418             NEXT_INSN (prev) = note;
4419             PREV_INSN (insn) = note;
4420             NEXT_INSN (note) = insn;
4421           }
4422         else
4423           {
4424             added_notes++;
4425             new = emit_note_after (NOTE_LINE_NUMBER (note), prev);
4426             NOTE_SOURCE_FILE (new) = NOTE_SOURCE_FILE (note);
4427             RTX_INTEGRATED_P (new) = RTX_INTEGRATED_P (note);
4428           }
4429       }
4430   if (sched_verbose && added_notes)
4431     fprintf (dump, ";; added %d line-number notes\n", added_notes);
4432 }
4433
4434 /* After scheduling the function, delete redundant line notes from the
4435    insns list.  */
4436
4437 static void
4438 rm_redundant_line_notes ()
4439 {
4440   rtx line = 0;
4441   rtx insn = get_insns ();
4442   int active_insn = 0;
4443   int notes = 0;
4444
4445   /* Walk the insns deleting redundant line-number notes.  Many of these
4446      are already present.  The remainder tend to occur at basic
4447      block boundaries.  */
4448   for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
4449     if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
4450       {
4451         /* If there are no active insns following, INSN is redundant.  */
4452         if (active_insn == 0)
4453           {
4454             notes++;
4455             NOTE_SOURCE_FILE (insn) = 0;
4456             NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
4457           }
4458         /* If the line number is unchanged, LINE is redundant.  */
4459         else if (line
4460                  && NOTE_LINE_NUMBER (line) == NOTE_LINE_NUMBER (insn)
4461                  && NOTE_SOURCE_FILE (line) == NOTE_SOURCE_FILE (insn))
4462           {
4463             notes++;
4464             NOTE_SOURCE_FILE (line) = 0;
4465             NOTE_LINE_NUMBER (line) = NOTE_INSN_DELETED;
4466             line = insn;
4467           }
4468         else
4469           line = insn;
4470         active_insn = 0;
4471       }
4472     else if (!((GET_CODE (insn) == NOTE
4473                 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED)
4474                || (GET_CODE (insn) == INSN
4475                    && (GET_CODE (PATTERN (insn)) == USE
4476                        || GET_CODE (PATTERN (insn)) == CLOBBER))))
4477       active_insn++;
4478
4479   if (sched_verbose && notes)
4480     fprintf (dump, ";; deleted %d line-number notes\n", notes);
4481 }
4482
4483 /* Delete notes between head and tail and put them in the chain
4484    of notes ended by NOTE_LIST.  */
4485
4486 static void
4487 rm_other_notes (head, tail)
4488      rtx head;
4489      rtx tail;
4490 {
4491   rtx next_tail;
4492   rtx insn;
4493
4494   if (head == tail
4495       && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
4496     return;
4497
4498   next_tail = NEXT_INSN (tail);
4499   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
4500     {
4501       rtx prev;
4502
4503       /* Farm out notes, and maybe save them in NOTE_LIST.
4504          This is needed to keep the debugger from
4505          getting completely deranged.  */
4506       if (GET_CODE (insn) == NOTE)
4507         {
4508           prev = insn;
4509
4510           insn = unlink_other_notes (insn, next_tail);
4511
4512           if (prev == tail)
4513             abort ();
4514           if (prev == head)
4515             abort ();
4516           if (insn == next_tail)
4517             abort ();
4518         }
4519     }
4520 }
4521
4522 /* Functions for computation of registers live/usage info.  */
4523
4524 /* Calculate INSN_REG_WEIGHT for all insns of a block.  */
4525
4526 static void
4527 find_insn_reg_weight (bb)
4528     int bb;
4529 {
4530   rtx insn, next_tail, head, tail;
4531
4532   get_block_head_tail (bb, &head, &tail);
4533   next_tail = NEXT_INSN (tail);
4534
4535   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
4536     {
4537       int reg_weight = 0;
4538       rtx x;
4539
4540       /* Handle register life information.  */
4541       if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
4542         continue;
4543
4544       /* Increment weight for each register born here.  */
4545       x = PATTERN (insn);
4546       if ((GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
4547           && register_operand (SET_DEST (x), VOIDmode))
4548         reg_weight++;
4549       else if (GET_CODE (x) == PARALLEL)
4550         {
4551           int j;
4552           for (j = XVECLEN (x, 0) - 1; j >= 0; j--)
4553             {
4554               x = XVECEXP (PATTERN (insn), 0, j);
4555               if ((GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
4556                   && register_operand (SET_DEST (x), VOIDmode))
4557                 reg_weight++;
4558             }
4559         }
4560
4561       /* Decrement weight for each register that dies here.  */
4562       for (x = REG_NOTES (insn); x; x = XEXP (x, 1))
4563         {
4564           if (REG_NOTE_KIND (x) == REG_DEAD
4565               || REG_NOTE_KIND (x) == REG_UNUSED)
4566             reg_weight--;
4567         }
4568
4569       INSN_REG_WEIGHT (insn) = reg_weight;
4570     }
4571 }
4572
4573 /* Scheduling clock, modified in schedule_block() and queue_to_ready ().  */
4574 static int clock_var;
4575
4576 /* Move insns that became ready to fire from queue to ready list.  */
4577
4578 static int
4579 queue_to_ready (ready, n_ready)
4580      rtx ready[];
4581      int n_ready;
4582 {
4583   rtx insn;
4584   rtx link;
4585
4586   q_ptr = NEXT_Q (q_ptr);
4587
4588   /* Add all pending insns that can be scheduled without stalls to the
4589      ready list.  */
4590   for (link = insn_queue[q_ptr]; link; link = XEXP (link, 1))
4591     {
4592
4593       insn = XEXP (link, 0);
4594       q_size -= 1;
4595
4596       if (sched_verbose >= 2)
4597         fprintf (dump, ";;\t\tQ-->Ready: insn %d: ", INSN_UID (insn));
4598
4599       if (sched_verbose >= 2 && INSN_BB (insn) != target_bb)
4600         fprintf (dump, "(b%d) ", INSN_BLOCK (insn));
4601
4602       ready[n_ready++] = insn;
4603       if (sched_verbose >= 2)
4604         fprintf (dump, "moving to ready without stalls\n");
4605     }
4606   insn_queue[q_ptr] = 0;
4607
4608   /* If there are no ready insns, stall until one is ready and add all
4609      of the pending insns at that point to the ready list.  */
4610   if (n_ready == 0)
4611     {
4612       register int stalls;
4613
4614       for (stalls = 1; stalls < INSN_QUEUE_SIZE; stalls++)
4615         {
4616           if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
4617             {
4618               for (; link; link = XEXP (link, 1))
4619                 {
4620                   insn = XEXP (link, 0);
4621                   q_size -= 1;
4622
4623                   if (sched_verbose >= 2)
4624                     fprintf (dump, ";;\t\tQ-->Ready: insn %d: ", INSN_UID (insn));
4625
4626                   if (sched_verbose >= 2 && INSN_BB (insn) != target_bb)
4627                     fprintf (dump, "(b%d) ", INSN_BLOCK (insn));
4628
4629                   ready[n_ready++] = insn;
4630                   if (sched_verbose >= 2)
4631                     fprintf (dump, "moving to ready with %d stalls\n", stalls);
4632                 }
4633               insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = 0;
4634
4635               if (n_ready)
4636                 break;
4637             }
4638         }
4639
4640       if (sched_verbose && stalls)
4641         visualize_stall_cycles (BB_TO_BLOCK (target_bb), stalls);
4642       q_ptr = NEXT_Q_AFTER (q_ptr, stalls);
4643       clock_var += stalls;
4644     }
4645   return n_ready;
4646 }
4647
4648 /* Print the ready list for debugging purposes.  Callable from debugger.  */
4649
4650 static void
4651 debug_ready_list (ready, n_ready)
4652      rtx ready[];
4653      int n_ready;
4654 {
4655   int i;
4656
4657   for (i = 0; i < n_ready; i++)
4658     {
4659       fprintf (dump, "  %d", INSN_UID (ready[i]));
4660       if (current_nr_blocks > 1 && INSN_BB (ready[i]) != target_bb)
4661         fprintf (dump, "/b%d", INSN_BLOCK (ready[i]));
4662     }
4663   fprintf (dump, "\n");
4664 }
4665
4666 /* Print names of units on which insn can/should execute, for debugging.  */
4667
4668 static void
4669 insn_print_units (insn)
4670      rtx insn;
4671 {
4672   int i;
4673   int unit = insn_unit (insn);
4674
4675   if (unit == -1)
4676     fprintf (dump, "none");
4677   else if (unit >= 0)
4678     fprintf (dump, "%s", function_units[unit].name);
4679   else
4680     {
4681       fprintf (dump, "[");
4682       for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
4683         if (unit & 1)
4684           {
4685             fprintf (dump, "%s", function_units[i].name);
4686             if (unit != 1)
4687               fprintf (dump, " ");
4688           }
4689       fprintf (dump, "]");
4690     }
4691 }
4692
4693 /* MAX_VISUAL_LINES is the maximum number of lines in visualization table
4694    of a basic block.  If more lines are needed, table is splitted to two.
4695    n_visual_lines is the number of lines printed so far for a block.
4696    visual_tbl contains the block visualization info.
4697    vis_no_unit holds insns in a cycle that are not mapped to any unit.  */
4698 #define MAX_VISUAL_LINES 100
4699 #define INSN_LEN 30
4700 int n_visual_lines;
4701 char *visual_tbl;
4702 int n_vis_no_unit;
4703 rtx vis_no_unit[10];
4704
4705 /* Finds units that are in use in this fuction.  Required only
4706    for visualization.  */
4707
4708 static void
4709 init_target_units ()
4710 {
4711   rtx insn;
4712   int unit;
4713
4714   for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
4715     {
4716       if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
4717         continue;
4718
4719       unit = insn_unit (insn);
4720
4721       if (unit < 0)
4722         target_units |= ~unit;
4723       else
4724         target_units |= (1 << unit);
4725     }
4726 }
4727
4728 /* Return the length of the visualization table.  */
4729
4730 static int
4731 get_visual_tbl_length ()
4732 {
4733   int unit, i;
4734   int n, n1;
4735   char *s;
4736
4737   /* Compute length of one field in line.  */
4738   s = (char *) alloca (INSN_LEN + 6);
4739   sprintf (s, "  %33s", "uname");
4740   n1 = strlen (s);
4741
4742   /* Compute length of one line.  */
4743   n = strlen (";; ");
4744   n += n1;
4745   for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
4746     if (function_units[unit].bitmask & target_units)
4747       for (i = 0; i < function_units[unit].multiplicity; i++)
4748         n += n1;
4749   n += n1;
4750   n += strlen ("\n") + 2;
4751
4752   /* Compute length of visualization string.  */
4753   return (MAX_VISUAL_LINES * n);
4754 }
4755
4756 /* Init block visualization debugging info.  */
4757
4758 static void
4759 init_block_visualization ()
4760 {
4761   strcpy (visual_tbl, "");
4762   n_visual_lines = 0;
4763   n_vis_no_unit = 0;
4764 }
4765
4766 #define BUF_LEN 256
4767
4768 static char *
4769 safe_concat (buf, cur, str)
4770      char *buf;
4771      char *cur;
4772      const char *str;
4773 {
4774   char *end = buf + BUF_LEN - 2;        /* Leave room for null.  */
4775   int c;
4776
4777   if (cur > end)
4778     {
4779       *end = '\0';
4780       return end;
4781     }
4782
4783   while (cur < end && (c = *str++) != '\0')
4784     *cur++ = c;
4785
4786   *cur = '\0';
4787   return cur;
4788 }
4789
4790 /* This recognizes rtx, I classified as expressions.  These are always
4791    represent some action on values or results of other expression, that
4792    may be stored in objects representing values.  */
4793
4794 static void
4795 print_exp (buf, x, verbose)
4796      char *buf;
4797      rtx x;
4798      int verbose;
4799 {
4800   char tmp[BUF_LEN];
4801   const char *st[4];
4802   char *cur = buf;
4803   const char *fun = (char *)0;
4804   const char *sep;
4805   rtx op[4];
4806   int i;
4807
4808   for (i = 0; i < 4; i++)
4809     {
4810       st[i] = (char *)0;
4811       op[i] = NULL_RTX;
4812     }
4813
4814   switch (GET_CODE (x))
4815     {
4816     case PLUS:
4817       op[0] = XEXP (x, 0);
4818       if (GET_CODE (XEXP (x, 1)) == CONST_INT
4819           && INTVAL (XEXP (x, 1)) < 0)
4820         {
4821           st[1] = "-";
4822           op[1] = GEN_INT (-INTVAL (XEXP (x, 1)));
4823         }
4824       else
4825         {
4826           st[1] = "+";
4827           op[1] = XEXP (x, 1);
4828         }
4829       break;
4830     case LO_SUM:
4831       op[0] = XEXP (x, 0);
4832       st[1] = "+low(";
4833       op[1] = XEXP (x, 1);
4834       st[2] = ")";
4835       break;
4836     case MINUS:
4837       op[0] = XEXP (x, 0);
4838       st[1] = "-";
4839       op[1] = XEXP (x, 1);
4840       break;
4841     case COMPARE:
4842       fun = "cmp";
4843       op[0] = XEXP (x, 0);
4844       op[1] = XEXP (x, 1);
4845       break;
4846     case NEG:
4847       st[0] = "-";
4848       op[0] = XEXP (x, 0);
4849       break;
4850     case MULT:
4851       op[0] = XEXP (x, 0);
4852       st[1] = "*";
4853       op[1] = XEXP (x, 1);
4854       break;
4855     case DIV:
4856       op[0] = XEXP (x, 0);
4857       st[1] = "/";
4858       op[1] = XEXP (x, 1);
4859       break;
4860     case UDIV:
4861       fun = "udiv";
4862       op[0] = XEXP (x, 0);
4863       op[1] = XEXP (x, 1);
4864       break;
4865     case MOD:
4866       op[0] = XEXP (x, 0);
4867       st[1] = "%";
4868       op[1] = XEXP (x, 1);
4869       break;
4870     case UMOD:
4871       fun = "umod";
4872       op[0] = XEXP (x, 0);
4873       op[1] = XEXP (x, 1);
4874       break;
4875     case SMIN:
4876       fun = "smin";
4877       op[0] = XEXP (x, 0);
4878       op[1] = XEXP (x, 1);
4879       break;
4880     case SMAX:
4881       fun = "smax";
4882       op[0] = XEXP (x, 0);
4883       op[1] = XEXP (x, 1);
4884       break;
4885     case UMIN:
4886       fun = "umin";
4887       op[0] = XEXP (x, 0);
4888       op[1] = XEXP (x, 1);
4889       break;
4890     case UMAX:
4891       fun = "umax";
4892       op[0] = XEXP (x, 0);
4893       op[1] = XEXP (x, 1);
4894       break;
4895     case NOT:
4896       st[0] = "!";
4897       op[0] = XEXP (x, 0);
4898       break;
4899     case AND:
4900       op[0] = XEXP (x, 0);
4901       st[1] = "&";
4902       op[1] = XEXP (x, 1);
4903       break;
4904     case IOR:
4905       op[0] = XEXP (x, 0);
4906       st[1] = "|";
4907       op[1] = XEXP (x, 1);
4908       break;
4909     case XOR:
4910       op[0] = XEXP (x, 0);
4911       st[1] = "^";
4912       op[1] = XEXP (x, 1);
4913       break;
4914     case ASHIFT:
4915       op[0] = XEXP (x, 0);
4916       st[1] = "<<";
4917       op[1] = XEXP (x, 1);
4918       break;
4919     case LSHIFTRT:
4920       op[0] = XEXP (x, 0);
4921       st[1] = " 0>>";
4922       op[1] = XEXP (x, 1);
4923       break;
4924     case ASHIFTRT:
4925       op[0] = XEXP (x, 0);
4926       st[1] = ">>";
4927       op[1] = XEXP (x, 1);
4928       break;
4929     case ROTATE:
4930       op[0] = XEXP (x, 0);
4931       st[1] = "<-<";
4932       op[1] = XEXP (x, 1);
4933       break;
4934     case ROTATERT:
4935       op[0] = XEXP (x, 0);
4936       st[1] = ">->";
4937       op[1] = XEXP (x, 1);
4938       break;
4939     case ABS:
4940       fun = "abs";
4941       op[0] = XEXP (x, 0);
4942       break;
4943     case SQRT:
4944       fun = "sqrt";
4945       op[0] = XEXP (x, 0);
4946       break;
4947     case FFS:
4948       fun = "ffs";
4949       op[0] = XEXP (x, 0);
4950       break;
4951     case EQ:
4952       op[0] = XEXP (x, 0);
4953       st[1] = "==";
4954       op[1] = XEXP (x, 1);
4955       break;
4956     case NE:
4957       op[0] = XEXP (x, 0);
4958       st[1] = "!=";
4959       op[1] = XEXP (x, 1);
4960       break;
4961     case GT:
4962       op[0] = XEXP (x, 0);
4963       st[1] = ">";
4964       op[1] = XEXP (x, 1);
4965       break;
4966     case GTU:
4967       fun = "gtu";
4968       op[0] = XEXP (x, 0);
4969       op[1] = XEXP (x, 1);
4970       break;
4971     case LT:
4972       op[0] = XEXP (x, 0);
4973       st[1] = "<";
4974       op[1] = XEXP (x, 1);
4975       break;
4976     case LTU:
4977       fun = "ltu";
4978       op[0] = XEXP (x, 0);
4979       op[1] = XEXP (x, 1);
4980       break;
4981     case GE:
4982       op[0] = XEXP (x, 0);
4983       st[1] = ">=";
4984       op[1] = XEXP (x, 1);
4985       break;
4986     case GEU:
4987       fun = "geu";
4988       op[0] = XEXP (x, 0);
4989       op[1] = XEXP (x, 1);
4990       break;
4991     case LE:
4992       op[0] = XEXP (x, 0);
4993       st[1] = "<=";
4994       op[1] = XEXP (x, 1);
4995       break;
4996     case LEU:
4997       fun = "leu";
4998       op[0] = XEXP (x, 0);
4999       op[1] = XEXP (x, 1);
5000       break;
5001     case SIGN_EXTRACT:
5002       fun = (verbose) ? "sign_extract" : "sxt";
5003       op[0] = XEXP (x, 0);
5004       op[1] = XEXP (x, 1);
5005       op[2] = XEXP (x, 2);
5006       break;
5007     case ZERO_EXTRACT:
5008       fun = (verbose) ? "zero_extract" : "zxt";
5009       op[0] = XEXP (x, 0);
5010       op[1] = XEXP (x, 1);
5011       op[2] = XEXP (x, 2);
5012       break;
5013     case SIGN_EXTEND:
5014       fun = (verbose) ? "sign_extend" : "sxn";
5015       op[0] = XEXP (x, 0);
5016       break;
5017     case ZERO_EXTEND:
5018       fun = (verbose) ? "zero_extend" : "zxn";
5019       op[0] = XEXP (x, 0);
5020       break;
5021     case FLOAT_EXTEND:
5022       fun = (verbose) ? "float_extend" : "fxn";
5023       op[0] = XEXP (x, 0);
5024       break;
5025     case TRUNCATE:
5026       fun = (verbose) ? "trunc" : "trn";
5027       op[0] = XEXP (x, 0);
5028       break;
5029     case FLOAT_TRUNCATE:
5030       fun = (verbose) ? "float_trunc" : "ftr";
5031       op[0] = XEXP (x, 0);
5032       break;
5033     case FLOAT:
5034       fun = (verbose) ? "float" : "flt";
5035       op[0] = XEXP (x, 0);
5036       break;
5037     case UNSIGNED_FLOAT:
5038       fun = (verbose) ? "uns_float" : "ufl";
5039       op[0] = XEXP (x, 0);
5040       break;
5041     case FIX:
5042       fun = "fix";
5043       op[0] = XEXP (x, 0);
5044       break;
5045     case UNSIGNED_FIX:
5046       fun = (verbose) ? "uns_fix" : "ufx";
5047       op[0] = XEXP (x, 0);
5048       break;
5049     case PRE_DEC:
5050       st[0] = "--";
5051       op[0] = XEXP (x, 0);
5052       break;
5053     case PRE_INC:
5054       st[0] = "++";
5055       op[0] = XEXP (x, 0);
5056       break;
5057     case POST_DEC:
5058       op[0] = XEXP (x, 0);
5059       st[1] = "--";
5060       break;
5061     case POST_INC:
5062       op[0] = XEXP (x, 0);
5063       st[1] = "++";
5064       break;
5065     case CALL:
5066       st[0] = "call ";
5067       op[0] = XEXP (x, 0);
5068       if (verbose)
5069         {
5070           st[1] = " argc:";
5071           op[1] = XEXP (x, 1);
5072         }
5073       break;
5074     case IF_THEN_ELSE:
5075       st[0] = "{(";
5076       op[0] = XEXP (x, 0);
5077       st[1] = ")?";
5078       op[1] = XEXP (x, 1);
5079       st[2] = ":";
5080       op[2] = XEXP (x, 2);
5081       st[3] = "}";
5082       break;
5083     case TRAP_IF:
5084       fun = "trap_if";
5085       op[0] = TRAP_CONDITION (x);
5086       break;
5087     case UNSPEC:
5088     case UNSPEC_VOLATILE:
5089       {
5090         cur = safe_concat (buf, cur, "unspec");
5091         if (GET_CODE (x) == UNSPEC_VOLATILE)
5092           cur = safe_concat (buf, cur, "/v");
5093         cur = safe_concat (buf, cur, "[");
5094         sep = "";
5095         for (i = 0; i < XVECLEN (x, 0); i++)
5096           {
5097             print_pattern (tmp, XVECEXP (x, 0, i), verbose);
5098             cur = safe_concat (buf, cur, sep);
5099             cur = safe_concat (buf, cur, tmp);
5100             sep = ",";
5101           }
5102         cur = safe_concat (buf, cur, "] ");
5103         sprintf (tmp, "%d", XINT (x, 1));
5104         cur = safe_concat (buf, cur, tmp);
5105       }
5106       break;
5107     default:
5108       /* If (verbose) debug_rtx (x);  */
5109       st[0] = GET_RTX_NAME (GET_CODE (x));
5110       break;
5111     }
5112
5113   /* Print this as a function?  */
5114   if (fun)
5115     {
5116       cur = safe_concat (buf, cur, fun);
5117       cur = safe_concat (buf, cur, "(");
5118     }
5119
5120   for (i = 0; i < 4; i++)
5121     {
5122       if (st[i])
5123         cur = safe_concat (buf, cur, st[i]);
5124
5125       if (op[i])
5126         {
5127           if (fun && i != 0)
5128             cur = safe_concat (buf, cur, ",");
5129
5130           print_value (tmp, op[i], verbose);
5131           cur = safe_concat (buf, cur, tmp);
5132         }
5133     }
5134
5135   if (fun)
5136     cur = safe_concat (buf, cur, ")");
5137 }               /* print_exp */
5138
5139 /* Prints rtxes, I customly classified as values.  They're constants,
5140    registers, labels, symbols and memory accesses.  */
5141
5142 static void
5143 print_value (buf, x, verbose)
5144      char *buf;
5145      rtx x;
5146      int verbose;
5147 {
5148   char t[BUF_LEN];
5149   char *cur = buf;
5150
5151   switch (GET_CODE (x))
5152     {
5153     case CONST_INT:
5154       sprintf (t, HOST_WIDE_INT_PRINT_HEX, INTVAL (x));
5155       cur = safe_concat (buf, cur, t);
5156       break;
5157     case CONST_DOUBLE:
5158       sprintf (t, "<0x%lx,0x%lx>", (long)XWINT (x, 2), (long)XWINT (x, 3));
5159       cur = safe_concat (buf, cur, t);
5160       break;
5161     case CONST_STRING:
5162       cur = safe_concat (buf, cur, "\"");
5163       cur = safe_concat (buf, cur, XSTR (x, 0));
5164       cur = safe_concat (buf, cur, "\"");
5165       break;
5166     case SYMBOL_REF:
5167       cur = safe_concat (buf, cur, "`");
5168       cur = safe_concat (buf, cur, XSTR (x, 0));
5169       cur = safe_concat (buf, cur, "'");
5170       break;
5171     case LABEL_REF:
5172       sprintf (t, "L%d", INSN_UID (XEXP (x, 0)));
5173       cur = safe_concat (buf, cur, t);
5174       break;
5175     case CONST:
5176       print_value (t, XEXP (x, 0), verbose);
5177       cur = safe_concat (buf, cur, "const(");
5178       cur = safe_concat (buf, cur, t);
5179       cur = safe_concat (buf, cur, ")");
5180       break;
5181     case HIGH:
5182       print_value (t, XEXP (x, 0), verbose);
5183       cur = safe_concat (buf, cur, "high(");
5184       cur = safe_concat (buf, cur, t);
5185       cur = safe_concat (buf, cur, ")");
5186       break;
5187     case REG:
5188       if (REGNO (x) < FIRST_PSEUDO_REGISTER)
5189         {
5190           int c = reg_names[ REGNO (x) ][0];
5191           if (c >= '0' && c <= '9')
5192             cur = safe_concat (buf, cur, "%");
5193
5194           cur = safe_concat (buf, cur, reg_names[ REGNO (x) ]);
5195         }
5196       else
5197         {
5198           sprintf (t, "r%d", REGNO (x));
5199           cur = safe_concat (buf, cur, t);
5200         }
5201       break;
5202     case SUBREG:
5203       print_value (t, SUBREG_REG (x), verbose);
5204       cur = safe_concat (buf, cur, t);
5205       sprintf (t, "#%d", SUBREG_WORD (x));
5206       cur = safe_concat (buf, cur, t);
5207       break;
5208     case SCRATCH:
5209       cur = safe_concat (buf, cur, "scratch");
5210       break;
5211     case CC0:
5212       cur = safe_concat (buf, cur, "cc0");
5213       break;
5214     case PC:
5215       cur = safe_concat (buf, cur, "pc");
5216       break;
5217     case MEM:
5218       print_value (t, XEXP (x, 0), verbose);
5219       cur = safe_concat (buf, cur, "[");
5220       cur = safe_concat (buf, cur, t);
5221       cur = safe_concat (buf, cur, "]");
5222       break;
5223     default:
5224       print_exp (t, x, verbose);
5225       cur = safe_concat (buf, cur, t);
5226       break;
5227     }
5228 }                               /* print_value */
5229
5230 /* The next step in insn detalization, its pattern recognition.  */
5231
5232 static void
5233 print_pattern (buf, x, verbose)
5234      char *buf;
5235      rtx x;
5236      int verbose;
5237 {
5238   char t1[BUF_LEN], t2[BUF_LEN], t3[BUF_LEN];
5239
5240   switch (GET_CODE (x))
5241     {
5242     case SET:
5243       print_value (t1, SET_DEST (x), verbose);
5244       print_value (t2, SET_SRC (x), verbose);
5245       sprintf (buf, "%s=%s", t1, t2);
5246       break;
5247     case RETURN:
5248       sprintf (buf, "return");
5249       break;
5250     case CALL:
5251       print_exp (buf, x, verbose);
5252       break;
5253     case CLOBBER:
5254       print_value (t1, XEXP (x, 0), verbose);
5255       sprintf (buf, "clobber %s", t1);
5256       break;
5257     case USE:
5258       print_value (t1, XEXP (x, 0), verbose);
5259       sprintf (buf, "use %s", t1);
5260       break;
5261     case PARALLEL:
5262       {
5263         int i;
5264
5265         sprintf (t1, "{");
5266         for (i = 0; i < XVECLEN (x, 0); i++)
5267           {
5268             print_pattern (t2, XVECEXP (x, 0, i), verbose);
5269             sprintf (t3, "%s%s;", t1, t2);
5270             strcpy (t1, t3);
5271           }
5272         sprintf (buf, "%s}", t1);
5273       }
5274       break;
5275     case SEQUENCE:
5276       {
5277         int i;
5278
5279         sprintf (t1, "%%{");
5280         for (i = 0; i < XVECLEN (x, 0); i++)
5281           {
5282             print_insn (t2, XVECEXP (x, 0, i), verbose);
5283             sprintf (t3, "%s%s;", t1, t2);
5284             strcpy (t1, t3);
5285           }
5286         sprintf (buf, "%s%%}", t1);
5287       }
5288       break;
5289     case ASM_INPUT:
5290       sprintf (buf, "asm {%s}", XSTR (x, 0));
5291       break;
5292     case ADDR_VEC:
5293       break;
5294     case ADDR_DIFF_VEC:
5295       print_value (buf, XEXP (x, 0), verbose);
5296       break;
5297     case TRAP_IF:
5298       print_value (t1, TRAP_CONDITION (x), verbose);
5299       sprintf (buf, "trap_if %s", t1);
5300       break;
5301     case UNSPEC:
5302       {
5303         int i;
5304
5305         sprintf (t1, "unspec{");
5306         for (i = 0; i < XVECLEN (x, 0); i++)
5307           {
5308             print_pattern (t2, XVECEXP (x, 0, i), verbose);
5309             sprintf (t3, "%s%s;", t1, t2);
5310             strcpy (t1, t3);
5311           }
5312         sprintf (buf, "%s}", t1);
5313       }
5314       break;
5315     case UNSPEC_VOLATILE:
5316       {
5317         int i;
5318
5319         sprintf (t1, "unspec/v{");
5320         for (i = 0; i < XVECLEN (x, 0); i++)
5321           {
5322             print_pattern (t2, XVECEXP (x, 0, i), verbose);
5323             sprintf (t3, "%s%s;", t1, t2);
5324             strcpy (t1, t3);
5325           }
5326         sprintf (buf, "%s}", t1);
5327       }
5328       break;
5329     default:
5330       print_value (buf, x, verbose);
5331     }
5332 }                               /* print_pattern */
5333
5334 /* This is the main function in rtl visualization mechanism. It
5335    accepts an rtx and tries to recognize it as an insn, then prints it
5336    properly in human readable form, resembling assembler mnemonics.
5337    For every insn it prints its UID and BB the insn belongs too.
5338    (Probably the last "option" should be extended somehow, since it
5339    depends now on sched.c inner variables ...)  */
5340
5341 static void
5342 print_insn (buf, x, verbose)
5343      char *buf;
5344      rtx x;
5345      int verbose;
5346 {
5347   char t[BUF_LEN];
5348   rtx insn = x;
5349
5350   switch (GET_CODE (x))
5351     {
5352     case INSN:
5353       print_pattern (t, PATTERN (x), verbose);
5354       if (verbose)
5355         sprintf (buf, "b%d: i% 4d: %s", INSN_BB (x),
5356                  INSN_UID (x), t);
5357       else
5358         sprintf (buf, "%-4d %s", INSN_UID (x), t);
5359       break;
5360     case JUMP_INSN:
5361       print_pattern (t, PATTERN (x), verbose);
5362       if (verbose)
5363         sprintf (buf, "b%d: i% 4d: jump %s", INSN_BB (x),
5364                  INSN_UID (x), t);
5365       else
5366         sprintf (buf, "%-4d %s", INSN_UID (x), t);
5367       break;
5368     case CALL_INSN:
5369       x = PATTERN (insn);
5370       if (GET_CODE (x) == PARALLEL)
5371         {
5372           x = XVECEXP (x, 0, 0);
5373           print_pattern (t, x, verbose);
5374         }
5375       else
5376         strcpy (t, "call <...>");
5377       if (verbose)
5378         sprintf (buf, "b%d: i% 4d: %s", INSN_BB (insn),
5379                  INSN_UID (insn), t);
5380       else
5381         sprintf (buf, "%-4d %s", INSN_UID (insn), t);
5382       break;
5383     case CODE_LABEL:
5384       sprintf (buf, "L%d:", INSN_UID (x));
5385       break;
5386     case BARRIER:
5387       sprintf (buf, "i% 4d: barrier", INSN_UID (x));
5388       break;
5389     case NOTE:
5390       if (NOTE_LINE_NUMBER (x) > 0)
5391         sprintf (buf, "%4d note \"%s\" %d", INSN_UID (x),
5392                  NOTE_SOURCE_FILE (x), NOTE_LINE_NUMBER (x));
5393       else
5394         sprintf (buf, "%4d %s", INSN_UID (x),
5395                  GET_NOTE_INSN_NAME (NOTE_LINE_NUMBER (x)));
5396       break;
5397     default:
5398       if (verbose)
5399         {
5400           sprintf (buf, "Not an INSN at all\n");
5401           debug_rtx (x);
5402         }
5403       else
5404         sprintf (buf, "i%-4d  <What?>", INSN_UID (x));
5405     }
5406 }                               /* print_insn */
5407
5408 /* Print visualization debugging info.  */
5409
5410 static void
5411 print_block_visualization (b, s)
5412      int b;
5413      const char *s;
5414 {
5415   int unit, i;
5416
5417   /* Print header.  */
5418   fprintf (dump, "\n;;   ==================== scheduling visualization for block %d %s \n", b, s);
5419
5420   /* Print names of units.  */
5421   fprintf (dump, ";;   %-8s", "clock");
5422   for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
5423     if (function_units[unit].bitmask & target_units)
5424       for (i = 0; i < function_units[unit].multiplicity; i++)
5425         fprintf (dump, "  %-33s", function_units[unit].name);
5426   fprintf (dump, "  %-8s\n", "no-unit");
5427
5428   fprintf (dump, ";;   %-8s", "=====");
5429   for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
5430     if (function_units[unit].bitmask & target_units)
5431       for (i = 0; i < function_units[unit].multiplicity; i++)
5432         fprintf (dump, "  %-33s", "==============================");
5433   fprintf (dump, "  %-8s\n", "=======");
5434
5435   /* Print insns in each cycle.  */
5436   fprintf (dump, "%s\n", visual_tbl);
5437 }
5438
5439 /* Print insns in the 'no_unit' column of visualization.  */
5440
5441 static void
5442 visualize_no_unit (insn)
5443      rtx insn;
5444 {
5445   vis_no_unit[n_vis_no_unit] = insn;
5446   n_vis_no_unit++;
5447 }
5448
5449 /* Print insns scheduled in clock, for visualization.  */
5450
5451 static void
5452 visualize_scheduled_insns (b, clock)
5453      int b, clock;
5454 {
5455   int i, unit;
5456
5457   /* If no more room, split table into two.  */
5458   if (n_visual_lines >= MAX_VISUAL_LINES)
5459     {
5460       print_block_visualization (b, "(incomplete)");
5461       init_block_visualization ();
5462     }
5463
5464   n_visual_lines++;
5465
5466   sprintf (visual_tbl + strlen (visual_tbl), ";;   %-8d", clock);
5467   for (unit = 0; unit < FUNCTION_UNITS_SIZE; unit++)
5468     if (function_units[unit].bitmask & target_units)
5469       for (i = 0; i < function_units[unit].multiplicity; i++)
5470         {
5471           int instance = unit + i * FUNCTION_UNITS_SIZE;
5472           rtx insn = unit_last_insn[instance];
5473
5474           /* Print insns that still keep the unit busy.  */
5475           if (insn &&
5476               actual_hazard_this_instance (unit, instance, insn, clock, 0))
5477             {
5478               char str[BUF_LEN];
5479               print_insn (str, insn, 0);
5480               str[INSN_LEN] = '\0';
5481               sprintf (visual_tbl + strlen (visual_tbl), "  %-33s", str);
5482             }
5483           else
5484             sprintf (visual_tbl + strlen (visual_tbl), "  %-33s", "------------------------------");
5485         }
5486
5487   /* Print insns that are not assigned to any unit.  */
5488   for (i = 0; i < n_vis_no_unit; i++)
5489     sprintf (visual_tbl + strlen (visual_tbl), "  %-8d",
5490              INSN_UID (vis_no_unit[i]));
5491   n_vis_no_unit = 0;
5492
5493   sprintf (visual_tbl + strlen (visual_tbl), "\n");
5494 }
5495
5496 /* Print stalled cycles.  */
5497
5498 static void
5499 visualize_stall_cycles (b, stalls)
5500      int b, stalls;
5501 {
5502   int i;
5503
5504   /* If no more room, split table into two.  */
5505   if (n_visual_lines >= MAX_VISUAL_LINES)
5506     {
5507       print_block_visualization (b, "(incomplete)");
5508       init_block_visualization ();
5509     }
5510
5511   n_visual_lines++;
5512
5513   sprintf (visual_tbl + strlen (visual_tbl), ";;       ");
5514   for (i = 0; i < stalls; i++)
5515     sprintf (visual_tbl + strlen (visual_tbl), ".");
5516   sprintf (visual_tbl + strlen (visual_tbl), "\n");
5517 }
5518
5519 /* move_insn1: Remove INSN from insn chain, and link it after LAST insn.  */
5520
5521 static rtx
5522 move_insn1 (insn, last)
5523      rtx insn, last;
5524 {
5525   NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
5526   PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
5527
5528   NEXT_INSN (insn) = NEXT_INSN (last);
5529   PREV_INSN (NEXT_INSN (last)) = insn;
5530
5531   NEXT_INSN (last) = insn;
5532   PREV_INSN (insn) = last;
5533
5534   return insn;
5535 }
5536
5537 /* Search INSN for REG_SAVE_NOTE note pairs for NOTE_INSN_SETJMP,
5538    NOTE_INSN_{LOOP,EHREGION}_{BEG,END}; and convert them back into
5539    NOTEs.  The REG_SAVE_NOTE note following first one is contains the
5540    saved value for NOTE_BLOCK_NUMBER which is useful for
5541    NOTE_INSN_EH_REGION_{BEG,END} NOTEs.  LAST is the last instruction
5542    output by the instruction scheduler.  Return the new value of LAST.  */
5543
5544 static rtx
5545 reemit_notes (insn, last)
5546      rtx insn;
5547      rtx last;
5548 {
5549   rtx note, retval;
5550
5551   retval = last;
5552   for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
5553     {
5554       if (REG_NOTE_KIND (note) == REG_SAVE_NOTE)
5555         {
5556           int note_type = INTVAL (XEXP (note, 0));
5557           if (note_type == NOTE_INSN_SETJMP)
5558             {
5559               retval = emit_note_after (NOTE_INSN_SETJMP, insn);
5560               CONST_CALL_P (retval) = CONST_CALL_P (note);
5561               remove_note (insn, note);
5562               note = XEXP (note, 1);
5563             }
5564           else if (note_type == NOTE_INSN_RANGE_START
5565                    || note_type == NOTE_INSN_RANGE_END)
5566             {
5567               last = emit_note_before (note_type, last);
5568               remove_note (insn, note);
5569               note = XEXP (note, 1);
5570               NOTE_RANGE_INFO (last) = XEXP (note, 0);
5571             }
5572           else
5573             {
5574               last = emit_note_before (note_type, last);
5575               remove_note (insn, note);
5576               note = XEXP (note, 1);
5577               if (note_type == NOTE_INSN_EH_REGION_BEG
5578                   || note_type == NOTE_INSN_EH_REGION_END)
5579                 NOTE_EH_HANDLER (last) = INTVAL (XEXP (note, 0));
5580             }
5581           remove_note (insn, note);
5582         }
5583     }
5584   return retval;
5585 }
5586
5587 /* Move INSN, and all insns which should be issued before it,
5588    due to SCHED_GROUP_P flag.  Reemit notes if needed.
5589
5590    Return the last insn emitted by the scheduler, which is the
5591    return value from the first call to reemit_notes.  */
5592
5593 static rtx
5594 move_insn (insn, last)
5595      rtx insn, last;
5596 {
5597   rtx retval = NULL;
5598
5599   /* If INSN has SCHED_GROUP_P set, then issue it and any other
5600      insns with SCHED_GROUP_P set first.  */
5601   while (SCHED_GROUP_P (insn))
5602     {
5603       rtx prev = PREV_INSN (insn);
5604
5605       /* Move a SCHED_GROUP_P insn.  */
5606       move_insn1 (insn, last);
5607       /* If this is the first call to reemit_notes, then record
5608          its return value.  */
5609       if (retval == NULL_RTX)
5610         retval = reemit_notes (insn, insn);
5611       else
5612         reemit_notes (insn, insn);
5613       insn = prev;
5614     }
5615
5616   /* Now move the first non SCHED_GROUP_P insn.  */
5617   move_insn1 (insn, last);
5618
5619   /* If this is the first call to reemit_notes, then record
5620      its return value.  */
5621   if (retval == NULL_RTX)
5622     retval = reemit_notes (insn, insn);
5623   else
5624     reemit_notes (insn, insn);
5625
5626   return retval;
5627 }
5628
5629 /* Return an insn which represents a SCHED_GROUP, which is
5630    the last insn in the group.  */
5631
5632 static rtx
5633 group_leader (insn)
5634      rtx insn;
5635 {
5636   rtx prev;
5637
5638   do
5639     {
5640       prev = insn;
5641       insn = next_nonnote_insn (insn);
5642     }
5643   while (insn && SCHED_GROUP_P (insn) && (GET_CODE (insn) != CODE_LABEL));
5644
5645   return prev;
5646 }
5647
5648 /* Use forward list scheduling to rearrange insns of block BB in region RGN,
5649    possibly bringing insns from subsequent blocks in the same region.
5650    Return number of insns scheduled.  */
5651
5652 static int
5653 schedule_block (bb, rgn_n_insns)
5654      int bb;
5655      int rgn_n_insns;
5656 {
5657   /* Local variables.  */
5658   rtx insn, last;
5659   rtx *ready;
5660   int n_ready = 0;
5661   int can_issue_more;
5662
5663   /* Flow block of this bb.  */
5664   int b = BB_TO_BLOCK (bb);
5665
5666   /* target_n_insns == number of insns in b before scheduling starts.
5667      sched_target_n_insns == how many of b's insns were scheduled.
5668      sched_n_insns == how many insns were scheduled in b.  */
5669   int target_n_insns = 0;
5670   int sched_target_n_insns = 0;
5671   int sched_n_insns = 0;
5672
5673 #define NEED_NOTHING    0
5674 #define NEED_HEAD       1
5675 #define NEED_TAIL       2
5676   int new_needs;
5677
5678   /* Head/tail info for this block.  */
5679   rtx prev_head;
5680   rtx next_tail;
5681   rtx head;
5682   rtx tail;
5683   int bb_src;
5684
5685   /* We used to have code to avoid getting parameters moved from hard
5686      argument registers into pseudos.
5687
5688      However, it was removed when it proved to be of marginal benefit
5689      and caused problems because schedule_block and compute_forward_dependences
5690      had different notions of what the "head" insn was.  */
5691   get_block_head_tail (bb, &head, &tail);
5692
5693   /* Interblock scheduling could have moved the original head insn from this
5694      block into a proceeding block.  This may also cause schedule_block and
5695      compute_forward_dependences to have different notions of what the
5696      "head" insn was.
5697
5698      If the interblock movement happened to make this block start with
5699      some notes (LOOP, EH or SETJMP) before the first real insn, then
5700      HEAD will have various special notes attached to it which must be
5701      removed so that we don't end up with extra copies of the notes.  */
5702   if (GET_RTX_CLASS (GET_CODE (head)) == 'i')
5703     {
5704       rtx note;
5705
5706       for (note = REG_NOTES (head); note; note = XEXP (note, 1))
5707         if (REG_NOTE_KIND (note) == REG_SAVE_NOTE)
5708           remove_note (head, note);
5709     }
5710
5711   next_tail = NEXT_INSN (tail);
5712   prev_head = PREV_INSN (head);
5713
5714   /* If the only insn left is a NOTE or a CODE_LABEL, then there is no need
5715      to schedule this block.  */
5716   if (head == tail
5717       && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
5718     return (sched_n_insns);
5719
5720   /* Debug info.  */
5721   if (sched_verbose)
5722     {
5723       fprintf (dump, ";;   ======================================================\n");
5724       fprintf (dump,
5725                ";;   -- basic block %d from %d to %d -- %s reload\n",
5726                b, INSN_UID (BLOCK_HEAD (b)), INSN_UID (BLOCK_END (b)),
5727                (reload_completed ? "after" : "before"));
5728       fprintf (dump, ";;   ======================================================\n");
5729       fprintf (dump, "\n");
5730
5731       visual_tbl = (char *) alloca (get_visual_tbl_length ());
5732       init_block_visualization ();
5733     }
5734
5735   /* Remove remaining note insns from the block, save them in
5736      note_list.  These notes are restored at the end of
5737      schedule_block ().  */
5738   note_list = 0;
5739   rm_other_notes (head, tail);
5740
5741   target_bb = bb;
5742
5743   /* Prepare current target block info.  */
5744   if (current_nr_blocks > 1)
5745     {
5746       candidate_table = (candidate *) alloca (current_nr_blocks
5747                                               * sizeof (candidate));
5748
5749       bblst_last = 0;
5750       /* ??? It is not clear why bblst_size is computed this way.  The original
5751          number was clearly too small as it resulted in compiler failures.
5752          Multiplying by the original number by 2 (to account for update_bbs
5753          members) seems to be a reasonable solution.  */
5754       /* ??? Or perhaps there is a bug somewhere else in this file?  */
5755       bblst_size = (current_nr_blocks - bb) * rgn_nr_edges * 2;
5756       bblst_table = (int *) alloca (bblst_size * sizeof (int));
5757
5758       bitlst_table_last = 0;
5759       bitlst_table_size = rgn_nr_edges;
5760       bitlst_table = (int *) alloca (rgn_nr_edges * sizeof (int));
5761
5762       compute_trg_info (bb);
5763     }
5764
5765   clear_units ();
5766
5767   /* Allocate the ready list.  */
5768   ready = (rtx *) alloca ((rgn_n_insns + 1) * sizeof (rtx));
5769
5770   /* Print debugging information.  */
5771   if (sched_verbose >= 5)
5772     debug_dependencies ();
5773
5774
5775   /* Initialize ready list with all 'ready' insns in target block.
5776      Count number of insns in the target block being scheduled.  */
5777   n_ready = 0;
5778   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
5779     {
5780       rtx next;
5781
5782       if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
5783         continue;
5784       next = NEXT_INSN (insn);
5785
5786       if (INSN_DEP_COUNT (insn) == 0
5787           && (SCHED_GROUP_P (next) == 0 || GET_RTX_CLASS (GET_CODE (next)) != 'i'))
5788         ready[n_ready++] = insn;
5789       if (!(SCHED_GROUP_P (insn)))
5790         target_n_insns++;
5791     }
5792
5793   /* Add to ready list all 'ready' insns in valid source blocks.
5794      For speculative insns, check-live, exception-free, and
5795      issue-delay.  */
5796   for (bb_src = bb + 1; bb_src < current_nr_blocks; bb_src++)
5797     if (IS_VALID (bb_src))
5798       {
5799         rtx src_head;
5800         rtx src_next_tail;
5801         rtx tail, head;
5802
5803         get_block_head_tail (bb_src, &head, &tail);
5804         src_next_tail = NEXT_INSN (tail);
5805         src_head = head;
5806
5807         if (head == tail
5808             && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
5809           continue;
5810
5811         for (insn = src_head; insn != src_next_tail; insn = NEXT_INSN (insn))
5812           {
5813             if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
5814               continue;
5815
5816             if (!CANT_MOVE (insn)
5817                 && (!IS_SPECULATIVE_INSN (insn)
5818                     || (insn_issue_delay (insn) <= 3
5819                         && check_live (insn, bb_src)
5820                         && is_exception_free (insn, bb_src, target_bb))))
5821
5822               {
5823                 rtx next;
5824
5825                 /* Note that we havn't squirrled away the notes for
5826                    blocks other than the current.  So if this is a
5827                    speculative insn, NEXT might otherwise be a note.  */
5828                 next = next_nonnote_insn (insn);
5829                 if (INSN_DEP_COUNT (insn) == 0
5830                     && (SCHED_GROUP_P (next) == 0
5831                         || GET_RTX_CLASS (GET_CODE (next)) != 'i'))
5832                   ready[n_ready++] = insn;
5833               }
5834           }
5835       }
5836
5837 #ifdef MD_SCHED_INIT
5838   MD_SCHED_INIT (dump, sched_verbose);
5839 #endif
5840
5841   /* No insns scheduled in this block yet.  */
5842   last_scheduled_insn = 0;
5843
5844   /* Q_SIZE is the total number of insns in the queue.  */
5845   q_ptr = 0;
5846   q_size = 0;
5847   last_clock_var = 0;
5848   bzero ((char *) insn_queue, sizeof (insn_queue));
5849
5850   /* Start just before the beginning of time.  */
5851   clock_var = -1;
5852
5853   /* We start inserting insns after PREV_HEAD.  */
5854   last = prev_head;
5855
5856   /* Initialize INSN_QUEUE, LIST and NEW_NEEDS.  */
5857   new_needs = (NEXT_INSN (prev_head) == BLOCK_HEAD (b)
5858                ? NEED_HEAD : NEED_NOTHING);
5859   if (PREV_INSN (next_tail) == BLOCK_END (b))
5860     new_needs |= NEED_TAIL;
5861
5862   /* Loop until all the insns in BB are scheduled.  */
5863   while (sched_target_n_insns < target_n_insns)
5864     {
5865       int b1;
5866
5867       clock_var++;
5868
5869       /* Add to the ready list all pending insns that can be issued now.
5870          If there are no ready insns, increment clock until one
5871          is ready and add all pending insns at that point to the ready
5872          list.  */
5873       n_ready = queue_to_ready (ready, n_ready);
5874
5875       if (n_ready == 0)
5876         abort ();
5877
5878       if (sched_verbose >= 2)
5879         {
5880           fprintf (dump, ";;\t\tReady list after queue_to_ready:  ");
5881           debug_ready_list (ready, n_ready);
5882         }
5883
5884       /* Sort the ready list based on priority.  */
5885       SCHED_SORT (ready, n_ready);
5886
5887       /* Allow the target to reorder the list, typically for
5888          better instruction bundling.  */
5889 #ifdef MD_SCHED_REORDER
5890       MD_SCHED_REORDER (dump, sched_verbose, ready, n_ready, clock_var,
5891                         can_issue_more);
5892 #else
5893       can_issue_more = issue_rate;
5894 #endif
5895
5896       if (sched_verbose)
5897         {
5898           fprintf (dump, "\n;;\tReady list (t =%3d):  ", clock_var);
5899           debug_ready_list (ready, n_ready);
5900         }
5901
5902       /* Issue insns from ready list.  */
5903       while (n_ready != 0 && can_issue_more)
5904         {
5905           /* Select and remove the insn from the ready list.  */
5906           rtx insn = ready[--n_ready];
5907           int cost = actual_hazard (insn_unit (insn), insn, clock_var, 0);
5908
5909           if (cost >= 1)
5910             {
5911               queue_insn (insn, cost);
5912               continue;
5913             }
5914
5915           /* An interblock motion?  */
5916           if (INSN_BB (insn) != target_bb)
5917             {
5918               rtx temp;
5919
5920               if (IS_SPECULATIVE_INSN (insn))
5921                 {
5922                   if (!check_live (insn, INSN_BB (insn)))
5923                     continue;
5924                   update_live (insn, INSN_BB (insn));
5925
5926                   /* For speculative load, mark insns fed by it.  */
5927                   if (IS_LOAD_INSN (insn) || FED_BY_SPEC_LOAD (insn))
5928                     set_spec_fed (insn);
5929
5930                   nr_spec++;
5931                 }
5932               nr_inter++;
5933
5934               temp = insn;
5935               while (SCHED_GROUP_P (temp))
5936                 temp = PREV_INSN (temp);
5937
5938               /* Update source block boundaries.   */
5939               b1 = INSN_BLOCK (temp);
5940               if (temp == BLOCK_HEAD (b1)
5941                   && insn == BLOCK_END (b1))
5942                 {
5943                   /* We moved all the insns in the basic block.
5944                      Emit a note after the last insn and update the
5945                      begin/end boundaries to point to the note.  */
5946                   emit_note_after (NOTE_INSN_DELETED, insn);
5947                   BLOCK_END (b1) = NEXT_INSN (insn);
5948                   BLOCK_HEAD (b1) = NEXT_INSN (insn);
5949                 }
5950               else if (insn == BLOCK_END (b1))
5951                 {
5952                   /* We took insns from the end of the basic block,
5953                      so update the end of block boundary so that it
5954                      points to the first insn we did not move.  */
5955                   BLOCK_END (b1) = PREV_INSN (temp);
5956                 }
5957               else if (temp == BLOCK_HEAD (b1))
5958                 {
5959                   /* We took insns from the start of the basic block,
5960                      so update the start of block boundary so that
5961                      it points to the first insn we did not move.  */
5962                   BLOCK_HEAD (b1) = NEXT_INSN (insn);
5963                 }
5964             }
5965           else
5966             {
5967               /* In block motion.  */
5968               sched_target_n_insns++;
5969             }
5970
5971           last_scheduled_insn = insn;
5972           last = move_insn (insn, last);
5973           sched_n_insns++;
5974
5975 #ifdef MD_SCHED_VARIABLE_ISSUE
5976           MD_SCHED_VARIABLE_ISSUE (dump, sched_verbose, insn,
5977                                    can_issue_more);
5978 #else
5979           can_issue_more--;
5980 #endif
5981
5982           n_ready = schedule_insn (insn, ready, n_ready, clock_var);
5983
5984           /* Close this block after scheduling its jump.  */
5985           if (GET_CODE (last_scheduled_insn) == JUMP_INSN)
5986             break;
5987         }
5988
5989       /* Debug info.  */
5990       if (sched_verbose)
5991         visualize_scheduled_insns (b, clock_var);
5992     }
5993
5994   /* Debug info.  */
5995   if (sched_verbose)
5996     {
5997       fprintf (dump, ";;\tReady list (final):  ");
5998       debug_ready_list (ready, n_ready);
5999       print_block_visualization (b, "");
6000     }
6001
6002   /* Sanity check -- queue must be empty now.  Meaningless if region has
6003      multiple bbs.  */
6004   if (current_nr_blocks > 1)
6005     if (!flag_schedule_interblock && q_size != 0)
6006       abort ();
6007
6008   /* Update head/tail boundaries.  */
6009   head = NEXT_INSN (prev_head);
6010   tail = last;
6011
6012   /* Restore-other-notes: NOTE_LIST is the end of a chain of notes
6013      previously found among the insns.  Insert them at the beginning
6014      of the insns.  */
6015   if (note_list != 0)
6016     {
6017       rtx note_head = note_list;
6018
6019       while (PREV_INSN (note_head))
6020         {
6021           note_head = PREV_INSN (note_head);
6022         }
6023
6024       PREV_INSN (note_head) = PREV_INSN (head);
6025       NEXT_INSN (PREV_INSN (head)) = note_head;
6026       PREV_INSN (head) = note_list;
6027       NEXT_INSN (note_list) = head;
6028       head = note_head;
6029     }
6030
6031   /* Update target block boundaries.  */
6032   if (new_needs & NEED_HEAD)
6033     BLOCK_HEAD (b) = head;
6034
6035   if (new_needs & NEED_TAIL)
6036     BLOCK_END (b) = tail;
6037
6038   /* Debugging.  */
6039   if (sched_verbose)
6040     {
6041       fprintf (dump, ";;   total time = %d\n;;   new basic block head = %d\n",
6042                clock_var, INSN_UID (BLOCK_HEAD (b)));
6043       fprintf (dump, ";;   new basic block end = %d\n\n",
6044                INSN_UID (BLOCK_END (b)));
6045     }
6046
6047   return (sched_n_insns);
6048 }                               /* schedule_block () */
6049 \f
6050
6051 /* Print the bit-set of registers, S, callable from debugger.  */
6052
6053 extern void
6054 debug_reg_vector (s)
6055      regset s;
6056 {
6057   int regno;
6058
6059   EXECUTE_IF_SET_IN_REG_SET (s, 0, regno,
6060                              {
6061                                fprintf (dump, " %d", regno);
6062                              });
6063
6064   fprintf (dump, "\n");
6065 }
6066
6067 /* Use the backward dependences from LOG_LINKS to build
6068    forward dependences in INSN_DEPEND.  */
6069
6070 static void
6071 compute_block_forward_dependences (bb)
6072      int bb;
6073 {
6074   rtx insn, link;
6075   rtx tail, head;
6076   rtx next_tail;
6077   enum reg_note dep_type;
6078
6079   get_block_head_tail (bb, &head, &tail);
6080   next_tail = NEXT_INSN (tail);
6081   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
6082     {
6083       if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
6084         continue;
6085
6086       insn = group_leader (insn);
6087
6088       for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
6089         {
6090           rtx x = group_leader (XEXP (link, 0));
6091           rtx new_link;
6092
6093           if (x != XEXP (link, 0))
6094             continue;
6095
6096 #ifdef ENABLE_CHECKING
6097           /* If add_dependence is working properly there should never
6098              be notes, deleted insns or duplicates in the backward
6099              links.  Thus we need not check for them here.
6100
6101              However, if we have enabled checking we might as well go
6102              ahead and verify that add_dependence worked properly.  */
6103           if (GET_CODE (x) == NOTE
6104               || INSN_DELETED_P (x)
6105               || find_insn_list (insn, INSN_DEPEND (x)))
6106             abort ();
6107 #endif
6108
6109           new_link = alloc_INSN_LIST (insn, INSN_DEPEND (x));
6110
6111           dep_type = REG_NOTE_KIND (link);
6112           PUT_REG_NOTE_KIND (new_link, dep_type);
6113
6114           INSN_DEPEND (x) = new_link;
6115           INSN_DEP_COUNT (insn) += 1;
6116         }
6117     }
6118 }
6119
6120 /* Initialize variables for region data dependence analysis.
6121    n_bbs is the number of region blocks.  */
6122
6123 __inline static void
6124 init_rgn_data_dependences (n_bbs)
6125      int n_bbs;
6126 {
6127   int bb;
6128
6129   /* Variables for which one copy exists for each block.  */
6130   bzero ((char *) bb_pending_read_insns, n_bbs * sizeof (rtx));
6131   bzero ((char *) bb_pending_read_mems, n_bbs * sizeof (rtx));
6132   bzero ((char *) bb_pending_write_insns, n_bbs * sizeof (rtx));
6133   bzero ((char *) bb_pending_write_mems, n_bbs * sizeof (rtx));
6134   bzero ((char *) bb_pending_lists_length, n_bbs * sizeof (rtx));
6135   bzero ((char *) bb_last_pending_memory_flush, n_bbs * sizeof (rtx));
6136   bzero ((char *) bb_last_function_call, n_bbs * sizeof (rtx));
6137   bzero ((char *) bb_sched_before_next_call, n_bbs * sizeof (rtx));
6138
6139   /* Create an insn here so that we can hang dependencies off of it later.  */
6140   for (bb = 0; bb < n_bbs; bb++)
6141     {
6142       bb_sched_before_next_call[bb] =
6143         gen_rtx_INSN (VOIDmode, 0, NULL_RTX, NULL_RTX,
6144                       NULL_RTX, 0, NULL_RTX, NULL_RTX);
6145       LOG_LINKS (bb_sched_before_next_call[bb]) = 0;
6146     }
6147 }
6148
6149 /* Add dependences so that branches are scheduled to run last in their
6150    block.  */
6151
6152 static void
6153 add_branch_dependences (head, tail)
6154      rtx head, tail;
6155 {
6156
6157   rtx insn, last;
6158
6159   /* For all branches, calls, uses, and cc0 setters, force them to remain
6160      in order at the end of the block by adding dependencies and giving
6161      the last a high priority.  There may be notes present, and prev_head
6162      may also be a note.
6163
6164      Branches must obviously remain at the end.  Calls should remain at the
6165      end since moving them results in worse register allocation.  Uses remain
6166      at the end to ensure proper register allocation.  cc0 setters remaim
6167      at the end because they can't be moved away from their cc0 user.  */
6168   insn = tail;
6169   last = 0;
6170   while (GET_CODE (insn) == CALL_INSN || GET_CODE (insn) == JUMP_INSN
6171          || (GET_CODE (insn) == INSN
6172              && (GET_CODE (PATTERN (insn)) == USE
6173 #ifdef HAVE_cc0
6174                  || sets_cc0_p (PATTERN (insn))
6175 #endif
6176              ))
6177          || GET_CODE (insn) == NOTE)
6178     {
6179       if (GET_CODE (insn) != NOTE)
6180         {
6181           if (last != 0
6182               && !find_insn_list (insn, LOG_LINKS (last)))
6183             {
6184               add_dependence (last, insn, REG_DEP_ANTI);
6185               INSN_REF_COUNT (insn)++;
6186             }
6187
6188           CANT_MOVE (insn) = 1;
6189
6190           last = insn;
6191           /* Skip over insns that are part of a group.
6192              Make each insn explicitly depend on the previous insn.
6193              This ensures that only the group header will ever enter
6194              the ready queue (and, when scheduled, will automatically
6195              schedule the SCHED_GROUP_P block).  */
6196           while (SCHED_GROUP_P (insn))
6197             {
6198               rtx temp = prev_nonnote_insn (insn);
6199               add_dependence (insn, temp, REG_DEP_ANTI);
6200               insn = temp;
6201             }
6202         }
6203
6204       /* Don't overrun the bounds of the basic block.  */
6205       if (insn == head)
6206         break;
6207
6208       insn = PREV_INSN (insn);
6209     }
6210
6211   /* Make sure these insns are scheduled last in their block.  */
6212   insn = last;
6213   if (insn != 0)
6214     while (insn != head)
6215       {
6216         insn = prev_nonnote_insn (insn);
6217
6218         if (INSN_REF_COUNT (insn) != 0)
6219           continue;
6220
6221         add_dependence (last, insn, REG_DEP_ANTI);
6222         INSN_REF_COUNT (insn) = 1;
6223
6224         /* Skip over insns that are part of a group.  */
6225         while (SCHED_GROUP_P (insn))
6226           insn = prev_nonnote_insn (insn);
6227       }
6228 }
6229
6230 /* Compute backward dependences inside bb.  In a multiple blocks region:
6231    (1) a bb is analyzed after its predecessors, and (2) the lists in
6232    effect at the end of bb (after analyzing for bb) are inherited by
6233    bb's successrs.
6234
6235    Specifically for reg-reg data dependences, the block insns are
6236    scanned by sched_analyze () top-to-bottom.  Two lists are
6237    maintained by sched_analyze (): reg_last_sets[] for register DEFs,
6238    and reg_last_uses[] for register USEs.
6239
6240    When analysis is completed for bb, we update for its successors:
6241    ;  - DEFS[succ] = Union (DEFS [succ], DEFS [bb])
6242    ;  - USES[succ] = Union (USES [succ], DEFS [bb])
6243
6244    The mechanism for computing mem-mem data dependence is very
6245    similar, and the result is interblock dependences in the region.  */
6246
6247 static void
6248 compute_block_backward_dependences (bb)
6249      int bb;
6250 {
6251   int b;
6252   rtx x;
6253   rtx head, tail;
6254   int max_reg = max_reg_num ();
6255
6256   b = BB_TO_BLOCK (bb);
6257
6258   if (current_nr_blocks == 1)
6259     {
6260       reg_last_uses = (rtx *) alloca (max_reg * sizeof (rtx));
6261       reg_last_sets = (rtx *) alloca (max_reg * sizeof (rtx));
6262       reg_last_clobbers = (rtx *) alloca (max_reg * sizeof (rtx));
6263
6264       bzero ((char *) reg_last_uses, max_reg * sizeof (rtx));
6265       bzero ((char *) reg_last_sets, max_reg * sizeof (rtx));
6266       bzero ((char *) reg_last_clobbers, max_reg * sizeof (rtx));
6267
6268       pending_read_insns = 0;
6269       pending_read_mems = 0;
6270       pending_write_insns = 0;
6271       pending_write_mems = 0;
6272       pending_lists_length = 0;
6273       last_function_call = 0;
6274       last_pending_memory_flush = 0;
6275       sched_before_next_call
6276         = gen_rtx_INSN (VOIDmode, 0, NULL_RTX, NULL_RTX,
6277                         NULL_RTX, 0, NULL_RTX, NULL_RTX);
6278       LOG_LINKS (sched_before_next_call) = 0;
6279     }
6280   else
6281     {
6282       reg_last_uses = bb_reg_last_uses[bb];
6283       reg_last_sets = bb_reg_last_sets[bb];
6284       reg_last_clobbers = bb_reg_last_clobbers[bb];
6285
6286       pending_read_insns = bb_pending_read_insns[bb];
6287       pending_read_mems = bb_pending_read_mems[bb];
6288       pending_write_insns = bb_pending_write_insns[bb];
6289       pending_write_mems = bb_pending_write_mems[bb];
6290       pending_lists_length = bb_pending_lists_length[bb];
6291       last_function_call = bb_last_function_call[bb];
6292       last_pending_memory_flush = bb_last_pending_memory_flush[bb];
6293
6294       sched_before_next_call = bb_sched_before_next_call[bb];
6295     }
6296
6297   /* Do the analysis for this block.  */
6298   get_block_head_tail (bb, &head, &tail);
6299   sched_analyze (head, tail);
6300   add_branch_dependences (head, tail);
6301
6302   if (current_nr_blocks > 1)
6303     {
6304       int e, first_edge;
6305       int b_succ, bb_succ;
6306       int reg;
6307       rtx link_insn, link_mem;
6308       rtx u;
6309
6310       /* These lists should point to the right place, for correct
6311          freeing later.  */
6312       bb_pending_read_insns[bb] = pending_read_insns;
6313       bb_pending_read_mems[bb] = pending_read_mems;
6314       bb_pending_write_insns[bb] = pending_write_insns;
6315       bb_pending_write_mems[bb] = pending_write_mems;
6316
6317       /* bb's structures are inherited by it's successors.  */
6318       first_edge = e = OUT_EDGES (b);
6319       if (e > 0)
6320         do
6321           {
6322             b_succ = TO_BLOCK (e);
6323             bb_succ = BLOCK_TO_BB (b_succ);
6324
6325             /* Only bbs "below" bb, in the same region, are interesting.  */
6326             if (CONTAINING_RGN (b) != CONTAINING_RGN (b_succ)
6327                 || bb_succ <= bb)
6328               {
6329                 e = NEXT_OUT (e);
6330                 continue;
6331               }
6332
6333             for (reg = 0; reg < max_reg; reg++)
6334               {
6335
6336                 /* reg-last-uses lists are inherited by bb_succ.  */
6337                 for (u = reg_last_uses[reg]; u; u = XEXP (u, 1))
6338                   {
6339                     if (find_insn_list (XEXP (u, 0),
6340                                         (bb_reg_last_uses[bb_succ])[reg]))
6341                       continue;
6342
6343                     (bb_reg_last_uses[bb_succ])[reg]
6344                       = alloc_INSN_LIST (XEXP (u, 0),
6345                                          (bb_reg_last_uses[bb_succ])[reg]);
6346                   }
6347
6348                 /* reg-last-defs lists are inherited by bb_succ.  */
6349                 for (u = reg_last_sets[reg]; u; u = XEXP (u, 1))
6350                   {
6351                     if (find_insn_list (XEXP (u, 0),
6352                                         (bb_reg_last_sets[bb_succ])[reg]))
6353                       continue;
6354
6355                     (bb_reg_last_sets[bb_succ])[reg]
6356                       = alloc_INSN_LIST (XEXP (u, 0),
6357                                          (bb_reg_last_sets[bb_succ])[reg]);
6358                   }
6359
6360                 for (u = reg_last_clobbers[reg]; u; u = XEXP (u, 1))
6361                   {
6362                     if (find_insn_list (XEXP (u, 0),
6363                                         (bb_reg_last_clobbers[bb_succ])[reg]))
6364                       continue;
6365
6366                     (bb_reg_last_clobbers[bb_succ])[reg]
6367                       = alloc_INSN_LIST (XEXP (u, 0),
6368                                          (bb_reg_last_clobbers[bb_succ])[reg]);
6369                   }
6370               }
6371
6372             /* Mem read/write lists are inherited by bb_succ.  */
6373             link_insn = pending_read_insns;
6374             link_mem = pending_read_mems;
6375             while (link_insn)
6376               {
6377                 if (!(find_insn_mem_list (XEXP (link_insn, 0),
6378                                           XEXP (link_mem, 0),
6379                                           bb_pending_read_insns[bb_succ],
6380                                           bb_pending_read_mems[bb_succ])))
6381                   add_insn_mem_dependence (&bb_pending_read_insns[bb_succ],
6382                                            &bb_pending_read_mems[bb_succ],
6383                                    XEXP (link_insn, 0), XEXP (link_mem, 0));
6384                 link_insn = XEXP (link_insn, 1);
6385                 link_mem = XEXP (link_mem, 1);
6386               }
6387
6388             link_insn = pending_write_insns;
6389             link_mem = pending_write_mems;
6390             while (link_insn)
6391               {
6392                 if (!(find_insn_mem_list (XEXP (link_insn, 0),
6393                                           XEXP (link_mem, 0),
6394                                           bb_pending_write_insns[bb_succ],
6395                                           bb_pending_write_mems[bb_succ])))
6396                   add_insn_mem_dependence (&bb_pending_write_insns[bb_succ],
6397                                            &bb_pending_write_mems[bb_succ],
6398                                    XEXP (link_insn, 0), XEXP (link_mem, 0));
6399
6400                 link_insn = XEXP (link_insn, 1);
6401                 link_mem = XEXP (link_mem, 1);
6402               }
6403
6404             /* last_function_call is inherited by bb_succ.  */
6405             for (u = last_function_call; u; u = XEXP (u, 1))
6406               {
6407                 if (find_insn_list (XEXP (u, 0),
6408                                     bb_last_function_call[bb_succ]))
6409                   continue;
6410
6411                 bb_last_function_call[bb_succ]
6412                   = alloc_INSN_LIST (XEXP (u, 0),
6413                                      bb_last_function_call[bb_succ]);
6414               }
6415
6416             /* last_pending_memory_flush is inherited by bb_succ.  */
6417             for (u = last_pending_memory_flush; u; u = XEXP (u, 1))
6418               {
6419                 if (find_insn_list (XEXP (u, 0),
6420                                     bb_last_pending_memory_flush[bb_succ]))
6421                   continue;
6422
6423                 bb_last_pending_memory_flush[bb_succ]
6424                   = alloc_INSN_LIST (XEXP (u, 0),
6425                                      bb_last_pending_memory_flush[bb_succ]);
6426               }
6427
6428             /* sched_before_next_call is inherited by bb_succ.  */
6429             x = LOG_LINKS (sched_before_next_call);
6430             for (; x; x = XEXP (x, 1))
6431               add_dependence (bb_sched_before_next_call[bb_succ],
6432                               XEXP (x, 0), REG_DEP_ANTI);
6433
6434             e = NEXT_OUT (e);
6435           }
6436         while (e != first_edge);
6437     }
6438
6439   /* Free up the INSN_LISTs.
6440
6441      Note this loop is executed max_reg * nr_regions times.  It's first
6442      implementation accounted for over 90% of the calls to free_INSN_LIST_list.
6443      The list was empty for the vast majority of those calls.  On the PA, not
6444      calling free_INSN_LIST_list in those cases improves -O2 compile times by
6445      3-5% on average.  */
6446   for (b = 0; b < max_reg; ++b)
6447     {
6448       if (reg_last_clobbers[b])
6449         free_INSN_LIST_list (&reg_last_clobbers[b]);
6450       if (reg_last_sets[b])
6451         free_INSN_LIST_list (&reg_last_sets[b]);
6452       if (reg_last_uses[b])
6453         free_INSN_LIST_list (&reg_last_uses[b]);
6454     }
6455
6456   /* Assert that we won't need bb_reg_last_* for this block anymore.  */
6457   if (current_nr_blocks > 1)
6458     {
6459       bb_reg_last_uses[bb] = (rtx *) NULL_RTX;
6460       bb_reg_last_sets[bb] = (rtx *) NULL_RTX;
6461       bb_reg_last_clobbers[bb] = (rtx *) NULL_RTX;
6462     }
6463 }
6464
6465 /* Print dependences for debugging, callable from debugger.  */
6466
6467 void
6468 debug_dependencies ()
6469 {
6470   int bb;
6471
6472   fprintf (dump, ";;   --------------- forward dependences: ------------ \n");
6473   for (bb = 0; bb < current_nr_blocks; bb++)
6474     {
6475       if (1)
6476         {
6477           rtx head, tail;
6478           rtx next_tail;
6479           rtx insn;
6480
6481           get_block_head_tail (bb, &head, &tail);
6482           next_tail = NEXT_INSN (tail);
6483           fprintf (dump, "\n;;   --- Region Dependences --- b %d bb %d \n",
6484                    BB_TO_BLOCK (bb), bb);
6485
6486           fprintf (dump, ";;   %7s%6s%6s%6s%6s%6s%11s%6s\n",
6487           "insn", "code", "bb", "dep", "prio", "cost", "blockage", "units");
6488           fprintf (dump, ";;   %7s%6s%6s%6s%6s%6s%11s%6s\n",
6489           "----", "----", "--", "---", "----", "----", "--------", "-----");
6490           for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
6491             {
6492               rtx link;
6493               int unit, range;
6494
6495               if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
6496                 {
6497                   int n;
6498                   fprintf (dump, ";;   %6d ", INSN_UID (insn));
6499                   if (GET_CODE (insn) == NOTE)
6500                     {
6501                       n = NOTE_LINE_NUMBER (insn);
6502                       if (n < 0)
6503                         fprintf (dump, "%s\n", GET_NOTE_INSN_NAME (n));
6504                       else
6505                         fprintf (dump, "line %d, file %s\n", n,
6506                                  NOTE_SOURCE_FILE (insn));
6507                     }
6508                   else
6509                     fprintf (dump, " {%s}\n", GET_RTX_NAME (GET_CODE (insn)));
6510                   continue;
6511                 }
6512
6513               unit = insn_unit (insn);
6514               range = (unit < 0
6515                  || function_units[unit].blockage_range_function == 0) ? 0 :
6516                 function_units[unit].blockage_range_function (insn);
6517               fprintf (dump,
6518                        ";;   %s%5d%6d%6d%6d%6d%6d  %3d -%3d   ",
6519                        (SCHED_GROUP_P (insn) ? "+" : " "),
6520                        INSN_UID (insn),
6521                        INSN_CODE (insn),
6522                        INSN_BB (insn),
6523                        INSN_DEP_COUNT (insn),
6524                        INSN_PRIORITY (insn),
6525                        insn_cost (insn, 0, 0),
6526                        (int) MIN_BLOCKAGE_COST (range),
6527                        (int) MAX_BLOCKAGE_COST (range));
6528               insn_print_units (insn);
6529               fprintf (dump, "\t: ");
6530               for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
6531                 fprintf (dump, "%d ", INSN_UID (XEXP (link, 0)));
6532               fprintf (dump, "\n");
6533             }
6534         }
6535     }
6536   fprintf (dump, "\n");
6537 }
6538
6539 /* Set_priorities: compute priority of each insn in the block.  */
6540
6541 static int
6542 set_priorities (bb)
6543      int bb;
6544 {
6545   rtx insn;
6546   int n_insn;
6547
6548   rtx tail;
6549   rtx prev_head;
6550   rtx head;
6551
6552   get_block_head_tail (bb, &head, &tail);
6553   prev_head = PREV_INSN (head);
6554
6555   if (head == tail
6556       && (GET_RTX_CLASS (GET_CODE (head)) != 'i'))
6557     return 0;
6558
6559   n_insn = 0;
6560   for (insn = tail; insn != prev_head; insn = PREV_INSN (insn))
6561     {
6562
6563       if (GET_CODE (insn) == NOTE)
6564         continue;
6565
6566       if (!(SCHED_GROUP_P (insn)))
6567         n_insn++;
6568       (void) priority (insn);
6569     }
6570
6571   return n_insn;
6572 }
6573
6574 /* Make each element of VECTOR point at an rtx-vector,
6575    taking the space for all those rtx-vectors from SPACE.
6576    SPACE is of type (rtx *), but it is really as long as NELTS rtx-vectors.
6577    BYTES_PER_ELT is the number of bytes in one rtx-vector.
6578    (this is the same as init_regset_vector () in flow.c)  */
6579
6580 static void
6581 init_rtx_vector (vector, space, nelts, bytes_per_elt)
6582      rtx **vector;
6583      rtx *space;
6584      int nelts;
6585      int bytes_per_elt;
6586 {
6587   register int i;
6588   register rtx *p = space;
6589
6590   for (i = 0; i < nelts; i++)
6591     {
6592       vector[i] = p;
6593       p += bytes_per_elt / sizeof (*p);
6594     }
6595 }
6596
6597 /* Schedule a region.  A region is either an inner loop, a loop-free
6598    subroutine, or a single basic block.  Each bb in the region is
6599    scheduled after its flow predecessors.  */
6600
6601 static void
6602 schedule_region (rgn)
6603      int rgn;
6604 {
6605   int bb;
6606   int rgn_n_insns = 0;
6607   int sched_rgn_n_insns = 0;
6608   int initial_deaths;
6609   sbitmap blocks;
6610
6611   /* Set variables for the current region.  */
6612   current_nr_blocks = RGN_NR_BLOCKS (rgn);
6613   current_blocks = RGN_BLOCKS (rgn);
6614
6615   reg_pending_sets = ALLOCA_REG_SET ();
6616   reg_pending_clobbers = ALLOCA_REG_SET ();
6617   reg_pending_sets_all = 0;
6618
6619   /* Create a bitmap of the blocks in this region.  */
6620   blocks = sbitmap_alloc (n_basic_blocks);
6621   sbitmap_zero (blocks);
6622
6623   for (bb = current_nr_blocks - 1; bb >= 0; --bb)
6624     SET_BIT (blocks, BB_TO_BLOCK (bb));
6625
6626   /* Initializations for region data dependence analyisis.  */
6627   if (current_nr_blocks > 1)
6628     {
6629       rtx *space;
6630       int maxreg = max_reg_num ();
6631
6632       bb_reg_last_uses = (rtx **) alloca (current_nr_blocks * sizeof (rtx *));
6633       space = (rtx *) alloca (current_nr_blocks * maxreg * sizeof (rtx));
6634       bzero ((char *) space, current_nr_blocks * maxreg * sizeof (rtx));
6635       init_rtx_vector (bb_reg_last_uses, space, current_nr_blocks,
6636                        maxreg * sizeof (rtx *));
6637
6638       bb_reg_last_sets = (rtx **) alloca (current_nr_blocks * sizeof (rtx *));
6639       space = (rtx *) alloca (current_nr_blocks * maxreg * sizeof (rtx));
6640       bzero ((char *) space, current_nr_blocks * maxreg * sizeof (rtx));
6641       init_rtx_vector (bb_reg_last_sets, space, current_nr_blocks,
6642                        maxreg * sizeof (rtx *));
6643
6644       bb_reg_last_clobbers =
6645         (rtx **) alloca (current_nr_blocks * sizeof (rtx *));
6646       space = (rtx *) alloca (current_nr_blocks * maxreg * sizeof (rtx));
6647       bzero ((char *) space, current_nr_blocks * maxreg * sizeof (rtx));
6648       init_rtx_vector (bb_reg_last_clobbers, space, current_nr_blocks,
6649                        maxreg * sizeof (rtx *));
6650
6651       bb_pending_read_insns = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
6652       bb_pending_read_mems = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
6653       bb_pending_write_insns =
6654         (rtx *) alloca (current_nr_blocks * sizeof (rtx));
6655       bb_pending_write_mems = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
6656       bb_pending_lists_length =
6657         (int *) alloca (current_nr_blocks * sizeof (int));
6658       bb_last_pending_memory_flush =
6659         (rtx *) alloca (current_nr_blocks * sizeof (rtx));
6660       bb_last_function_call = (rtx *) alloca (current_nr_blocks * sizeof (rtx));
6661       bb_sched_before_next_call =
6662         (rtx *) alloca (current_nr_blocks * sizeof (rtx));
6663
6664       init_rgn_data_dependences (current_nr_blocks);
6665     }
6666
6667   /* Compute LOG_LINKS.  */
6668   for (bb = 0; bb < current_nr_blocks; bb++)
6669     compute_block_backward_dependences (bb);
6670
6671   /* Compute INSN_DEPEND.  */
6672   for (bb = current_nr_blocks - 1; bb >= 0; bb--)
6673     compute_block_forward_dependences (bb);
6674
6675   /* Compute INSN_REG_WEIGHT.  */
6676   for (bb = current_nr_blocks - 1; bb >= 0; bb--)
6677     find_insn_reg_weight (bb);
6678
6679   /* Remove death notes.  */
6680   initial_deaths = count_or_remove_death_notes (blocks, 1);
6681
6682   /* Delete line notes and set priorities.  */
6683   for (bb = 0; bb < current_nr_blocks; bb++)
6684     {
6685       if (write_symbols != NO_DEBUG)
6686         {
6687           save_line_notes (bb);
6688           rm_line_notes (bb);
6689         }
6690
6691       rgn_n_insns += set_priorities (bb);
6692     }
6693
6694   /* Compute interblock info: probabilities, split-edges, dominators, etc.  */
6695   if (current_nr_blocks > 1)
6696     {
6697       int i;
6698
6699       prob = (float *) alloca ((current_nr_blocks) * sizeof (float));
6700
6701       bbset_size = current_nr_blocks / HOST_BITS_PER_WIDE_INT + 1;
6702       dom = (bbset *) alloca (current_nr_blocks * sizeof (bbset));
6703       for (i = 0; i < current_nr_blocks; i++)
6704         {
6705           dom[i] = (bbset) alloca (bbset_size * sizeof (HOST_WIDE_INT));
6706           bzero ((char *) dom[i], bbset_size * sizeof (HOST_WIDE_INT));
6707         }
6708
6709       /* Edge to bit.  */
6710       rgn_nr_edges = 0;
6711       edge_to_bit = (int *) alloca (nr_edges * sizeof (int));
6712       for (i = 1; i < nr_edges; i++)
6713         if (CONTAINING_RGN (FROM_BLOCK (i)) == rgn)
6714           EDGE_TO_BIT (i) = rgn_nr_edges++;
6715       rgn_edges = (int *) alloca (rgn_nr_edges * sizeof (int));
6716
6717       rgn_nr_edges = 0;
6718       for (i = 1; i < nr_edges; i++)
6719         if (CONTAINING_RGN (FROM_BLOCK (i)) == (rgn))
6720           rgn_edges[rgn_nr_edges++] = i;
6721
6722       /* Split edges.  */
6723       edgeset_size = rgn_nr_edges / HOST_BITS_PER_WIDE_INT + 1;
6724       pot_split = (edgeset *) alloca (current_nr_blocks * sizeof (edgeset));
6725       ancestor_edges = (edgeset *) alloca (current_nr_blocks
6726                                            * sizeof (edgeset));
6727       for (i = 0; i < current_nr_blocks; i++)
6728         {
6729           pot_split[i] =
6730             (edgeset) alloca (edgeset_size * sizeof (HOST_WIDE_INT));
6731           bzero ((char *) pot_split[i],
6732                  edgeset_size * sizeof (HOST_WIDE_INT));
6733           ancestor_edges[i] =
6734             (edgeset) alloca (edgeset_size * sizeof (HOST_WIDE_INT));
6735           bzero ((char *) ancestor_edges[i],
6736                  edgeset_size * sizeof (HOST_WIDE_INT));
6737         }
6738
6739       /* Compute probabilities, dominators, split_edges.  */
6740       for (bb = 0; bb < current_nr_blocks; bb++)
6741         compute_dom_prob_ps (bb);
6742     }
6743
6744   /* Now we can schedule all blocks.  */
6745   for (bb = 0; bb < current_nr_blocks; bb++)
6746     {
6747       sched_rgn_n_insns += schedule_block (bb, rgn_n_insns);
6748
6749 #ifdef USE_C_ALLOCA
6750       alloca (0);
6751 #endif
6752     }
6753
6754   /* Sanity check: verify that all region insns were scheduled.  */
6755   if (sched_rgn_n_insns != rgn_n_insns)
6756     abort ();
6757
6758   /* Update register life and usage information.  Scheduling a multi-block
6759      region requires a global update.  */
6760   if (current_nr_blocks > 1)
6761     update_life_info (blocks, UPDATE_LIFE_GLOBAL);
6762   else
6763     {
6764       update_life_info (blocks, UPDATE_LIFE_LOCAL);
6765
6766       /* In the single block case, the count of registers that died should
6767          not have changed during the schedule.  */
6768       if (count_or_remove_death_notes (blocks, 0) != initial_deaths)
6769         abort ();
6770     }
6771
6772   /* Restore line notes.  */
6773   if (write_symbols != NO_DEBUG)
6774     {
6775       for (bb = 0; bb < current_nr_blocks; bb++)
6776         restore_line_notes (bb);
6777     }
6778
6779   /* Done with this region.  */
6780   free_pending_lists ();
6781
6782   FREE_REG_SET (reg_pending_sets);
6783   FREE_REG_SET (reg_pending_clobbers);
6784   sbitmap_free (blocks);
6785 }
6786
6787 /* The one entry point in this file.  DUMP_FILE is the dump file for
6788    this pass.  */
6789
6790 void
6791 schedule_insns (dump_file)
6792      FILE *dump_file;
6793 {
6794
6795   int max_uid;
6796   int b;
6797   rtx insn;
6798   int rgn;
6799
6800   int luid;
6801
6802   /* Disable speculative loads in their presence if cc0 defined.  */
6803 #ifdef HAVE_cc0
6804   flag_schedule_speculative_load = 0;
6805 #endif
6806
6807   /* Taking care of this degenerate case makes the rest of
6808      this code simpler.  */
6809   if (n_basic_blocks == 0)
6810     return;
6811
6812   /* Set dump and sched_verbose for the desired debugging output.  If no
6813      dump-file was specified, but -fsched-verbose-N (any N), print to stderr.
6814      For -fsched-verbose-N, N>=10, print everything to stderr.  */
6815   sched_verbose = sched_verbose_param;
6816   if (sched_verbose_param == 0 && dump_file)
6817     sched_verbose = 1;
6818   dump = ((sched_verbose_param >= 10 || !dump_file) ? stderr : dump_file);
6819
6820   nr_inter = 0;
6821   nr_spec = 0;
6822
6823   /* Initialize issue_rate.  */
6824   issue_rate = ISSUE_RATE;
6825
6826   split_all_insns (1);
6827
6828   max_uid = (get_max_uid () + 1);
6829
6830   cant_move = xcalloc (max_uid, sizeof (char));
6831   fed_by_spec_load = xcalloc (max_uid, sizeof (char));
6832   is_load_insn = xcalloc (max_uid, sizeof (char));
6833
6834   insn_orig_block = (int *) xmalloc (max_uid * sizeof (int));
6835   insn_luid = (int *) xmalloc (max_uid * sizeof (int));
6836
6837   luid = 0;
6838   for (b = 0; b < n_basic_blocks; b++)
6839     for (insn = BLOCK_HEAD (b);; insn = NEXT_INSN (insn))
6840       {
6841         INSN_BLOCK (insn) = b;
6842         INSN_LUID (insn) = luid++;
6843
6844         if (insn == BLOCK_END (b))
6845           break;
6846       }
6847
6848   nr_regions = 0;
6849   rgn_table = (region *) alloca ((n_basic_blocks) * sizeof (region));
6850   rgn_bb_table = (int *) alloca ((n_basic_blocks) * sizeof (int));
6851   block_to_bb = (int *) alloca ((n_basic_blocks) * sizeof (int));
6852   containing_rgn = (int *) alloca ((n_basic_blocks) * sizeof (int));
6853
6854   /* Compute regions for scheduling.  */
6855   if (reload_completed
6856       || n_basic_blocks == 1
6857       || !flag_schedule_interblock)
6858     {
6859       find_single_block_region ();
6860     }
6861   else
6862     {
6863       /* Verify that a 'good' control flow graph can be built.  */
6864       if (is_cfg_nonregular ())
6865         {
6866           find_single_block_region ();
6867         }
6868       else
6869         {
6870           int_list_ptr *s_preds, *s_succs;
6871           int *num_preds, *num_succs;
6872           sbitmap *dom, *pdom;
6873
6874           s_preds = (int_list_ptr *) alloca (n_basic_blocks
6875                                              * sizeof (int_list_ptr));
6876           s_succs = (int_list_ptr *) alloca (n_basic_blocks
6877                                              * sizeof (int_list_ptr));
6878           num_preds = (int *) alloca (n_basic_blocks * sizeof (int));
6879           num_succs = (int *) alloca (n_basic_blocks * sizeof (int));
6880           dom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
6881           pdom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
6882
6883           /* The scheduler runs after flow; therefore, we can't blindly call
6884              back into find_basic_blocks since doing so could invalidate the
6885              info in global_live_at_start.
6886
6887              Consider a block consisting entirely of dead stores; after life
6888              analysis it would be a block of NOTE_INSN_DELETED notes.  If
6889              we call find_basic_blocks again, then the block would be removed
6890              entirely and invalidate our the register live information.
6891
6892              We could (should?) recompute register live information.  Doing
6893              so may even be beneficial.  */
6894
6895           compute_preds_succs (s_preds, s_succs, num_preds, num_succs);
6896
6897           /* Compute the dominators and post dominators.  We don't
6898              currently use post dominators, but we should for
6899              speculative motion analysis.  */
6900           compute_dominators (dom, pdom, s_preds, s_succs);
6901
6902           /* build_control_flow will return nonzero if it detects unreachable
6903              blocks or any other irregularity with the cfg which prevents
6904              cross block scheduling.  */
6905           if (build_control_flow (s_preds, s_succs, num_preds, num_succs) != 0)
6906             find_single_block_region ();
6907           else
6908             find_rgns (s_preds, s_succs, num_preds, num_succs, dom);
6909
6910           if (sched_verbose >= 3)
6911             debug_regions ();
6912
6913           /* For now.  This will move as more and more of haifa is converted
6914              to using the cfg code in flow.c.  */
6915           free_bb_mem ();
6916           free (dom);
6917           free (pdom);
6918         }
6919     }
6920
6921   /* Allocate data for this pass.  See comments, above,
6922      for what these vectors do.
6923
6924      We use xmalloc instead of alloca, because max_uid can be very large
6925      when there is a lot of function inlining.  If we used alloca, we could
6926      exceed stack limits on some hosts for some inputs.  */
6927   insn_priority = (int *) xcalloc (max_uid, sizeof (int));
6928   insn_reg_weight = (int *) xcalloc (max_uid, sizeof (int));
6929   insn_tick = (int *) xcalloc (max_uid, sizeof (int));
6930   insn_costs = (short *) xcalloc (max_uid, sizeof (short));
6931   insn_units = (short *) xcalloc (max_uid, sizeof (short));
6932   insn_blockage = (unsigned int *) xcalloc (max_uid, sizeof (unsigned int));
6933   insn_ref_count = (int *) xcalloc (max_uid, sizeof (int));
6934
6935   /* Allocate for forward dependencies.  */
6936   insn_dep_count = (int *) xcalloc (max_uid, sizeof (int));
6937   insn_depend = (rtx *) xcalloc (max_uid, sizeof (rtx));
6938
6939   init_alias_analysis ();
6940
6941   if (write_symbols != NO_DEBUG)
6942     {
6943       rtx line;
6944
6945       line_note = (rtx *) xcalloc (max_uid, sizeof (rtx));
6946       line_note_head = (rtx *) alloca (n_basic_blocks * sizeof (rtx));
6947       bzero ((char *) line_note_head, n_basic_blocks * sizeof (rtx));
6948
6949       /* Save-line-note-head:
6950          Determine the line-number at the start of each basic block.
6951          This must be computed and saved now, because after a basic block's
6952          predecessor has been scheduled, it is impossible to accurately
6953          determine the correct line number for the first insn of the block.  */
6954
6955       for (b = 0; b < n_basic_blocks; b++)
6956         for (line = BLOCK_HEAD (b); line; line = PREV_INSN (line))
6957           if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
6958             {
6959               line_note_head[b] = line;
6960               break;
6961             }
6962     }
6963
6964   /* Find units used in this fuction, for visualization.  */
6965   if (sched_verbose)
6966     init_target_units ();
6967
6968   /* ??? Add a NOTE after the last insn of the last basic block.  It is not
6969      known why this is done.  */
6970
6971   insn = BLOCK_END (n_basic_blocks - 1);
6972   if (NEXT_INSN (insn) == 0
6973       || (GET_CODE (insn) != NOTE
6974           && GET_CODE (insn) != CODE_LABEL
6975           /* Don't emit a NOTE if it would end up between an unconditional
6976              jump and a BARRIER.  */
6977           && !(GET_CODE (insn) == JUMP_INSN
6978                && GET_CODE (NEXT_INSN (insn)) == BARRIER)))
6979     emit_note_after (NOTE_INSN_DELETED, BLOCK_END (n_basic_blocks - 1));
6980
6981   /* Schedule every region in the subroutine.  */
6982   for (rgn = 0; rgn < nr_regions; rgn++)
6983     {
6984       schedule_region (rgn);
6985
6986 #ifdef USE_C_ALLOCA
6987       alloca (0);
6988 #endif
6989     }
6990
6991   /* Reposition the prologue and epilogue notes in case we moved the
6992      prologue/epilogue insns.  */
6993   if (reload_completed)
6994     reposition_prologue_and_epilogue_notes (get_insns ());
6995
6996   /* Delete redundant line notes.  */
6997   if (write_symbols != NO_DEBUG)
6998     rm_redundant_line_notes ();
6999
7000   if (sched_verbose)
7001     {
7002       if (reload_completed == 0 && flag_schedule_interblock)
7003         {
7004           fprintf (dump, "\n;; Procedure interblock/speculative motions == %d/%d \n",
7005                    nr_inter, nr_spec);
7006         }
7007       else
7008         {
7009           if (nr_inter > 0)
7010             abort ();
7011         }
7012       fprintf (dump, "\n\n");
7013     }
7014
7015   free (cant_move);
7016   free (fed_by_spec_load);
7017   free (is_load_insn);
7018   free (insn_orig_block);
7019   free (insn_luid);
7020
7021   free (insn_priority);
7022   free (insn_reg_weight);
7023   free (insn_tick);
7024   free (insn_costs);
7025   free (insn_units);
7026   free (insn_blockage);
7027   free (insn_ref_count);
7028
7029   free (insn_dep_count);
7030   free (insn_depend);
7031
7032   if (write_symbols != NO_DEBUG)
7033     free (line_note);
7034
7035   if (edge_table)
7036     {
7037       free (edge_table);
7038       edge_table = NULL;
7039     }
7040
7041   if (in_edges)
7042     {
7043       free (in_edges);
7044       in_edges = NULL;
7045     }
7046   if (out_edges)
7047     {
7048       free (out_edges);
7049       out_edges = NULL;
7050     }
7051 }
7052 #endif /* INSN_SCHEDULING */