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