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