gcc/sched-rgn.c

   1 /* Instruction scheduling pass.
   2    Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
   3    1999, 2000, 2001, 2002 Free Software Foundation, Inc.
   4    Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
   5    and currently maintained by, Jim Wilson (wilson@cygnus.com)
   6
   7 This file is part of GCC.
   8
   9 GCC is free software; you can redistribute it and/or modify it under
  10 the terms of the GNU General Public License as published by the Free
  11 Software Foundation; either version 2, or (at your option) any later
  12 version.
  13
  14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  16 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  17 for more details.
  18
  19 You should have received a copy of the GNU General Public License
  20 along with GCC; see the file COPYING.  If not, write to the Free
  21 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  22 02111-1307, USA.  */
  23
  24 /* This pass implements list scheduling within basic blocks.  It is
  25    run twice: (1) after flow analysis, but before register allocation,
  26    and (2) after register allocation.
  27
  28    The first run performs interblock scheduling, moving insns between
  29    different blocks in the same "region", and the second runs only
  30    basic block scheduling.
  31
  32    Interblock motions performed are useful motions and speculative
  33    motions, including speculative loads.  Motions requiring code
  34    duplication are not supported.  The identification of motion type
  35    and the check for validity of speculative motions requires
  36    construction and analysis of the function's control flow graph.
  37
  38    The main entry point for this pass is schedule_insns(), called for
  39    each function.  The work of the scheduler is organized in three
  40    levels: (1) function level: insns are subject to splitting,
  41    control-flow-graph is constructed, regions are computed (after
  42    reload, each region is of one block), (2) region level: control
  43    flow graph attributes required for interblock scheduling are
  44    computed (dominators, reachability, etc.), data dependences and
  45    priorities are computed, and (3) block level: insns in the block
  46    are actually scheduled.  */
  47 \f
  48 #include "config.h"
  49 #include "system.h"
  50 #include "toplev.h"
  51 #include "rtl.h"
  52 #include "tm_p.h"
  53 #include "hard-reg-set.h"
  54 #include "basic-block.h"
  55 #include "regs.h"
  56 #include "function.h"
  57 #include "flags.h"
  58 #include "insn-config.h"
  59 #include "insn-attr.h"
  60 #include "except.h"
  61 #include "toplev.h"
  62 #include "recog.h"
  63 #include "cfglayout.h"
  64 #include "sched-int.h"
  65 #include "target.h"
  66
  67 /* Define when we want to do count REG_DEAD notes before and after scheduling
  68    for sanity checking.  We can't do that when conditional execution is used,
  69    as REG_DEAD exist only for unconditional deaths.  */
  70
  71 #if !defined (HAVE_conditional_execution) && defined (ENABLE_CHECKING)
  72 #define CHECK_DEAD_NOTES 1
  73 #else
  74 #define CHECK_DEAD_NOTES 0
  75 #endif
  76
  77
  78 #ifdef INSN_SCHEDULING
  79 /* Some accessor macros for h_i_d members only used within this file.  */
  80 #define INSN_REF_COUNT(INSN)    (h_i_d[INSN_UID (INSN)].ref_count)
  81 #define FED_BY_SPEC_LOAD(insn)  (h_i_d[INSN_UID (insn)].fed_by_spec_load)
  82 #define IS_LOAD_INSN(insn)      (h_i_d[INSN_UID (insn)].is_load_insn)
  83
  84 #define MAX_RGN_BLOCKS 10
  85 #define MAX_RGN_INSNS 100
  86
  87 /* nr_inter/spec counts interblock/speculative motion for the function.  */
  88 static int nr_inter, nr_spec;
  89
  90 /* Control flow graph edges are kept in circular lists.  */
  91 typedef struct
  92 {
  93   int from_block;
  94   int to_block;
  95   int next_in;
  96   int next_out;
  97 }
  98 haifa_edge;
  99 static haifa_edge *edge_table;
 100
 101 #define NEXT_IN(edge) (edge_table[edge].next_in)
 102 #define NEXT_OUT(edge) (edge_table[edge].next_out)
 103 #define FROM_BLOCK(edge) (edge_table[edge].from_block)
 104 #define TO_BLOCK(edge) (edge_table[edge].to_block)
 105
 106 /* Number of edges in the control flow graph.  (In fact, larger than
 107    that by 1, since edge 0 is unused.)  */
 108 static int nr_edges;
 109
 110 /* Circular list of incoming/outgoing edges of a block.  */
 111 static int *in_edges;
 112 static int *out_edges;
 113
 114 #define IN_EDGES(block) (in_edges[block])
 115 #define OUT_EDGES(block) (out_edges[block])
 116
 117 static int is_cfg_nonregular PARAMS ((void));
 118 static int build_control_flow PARAMS ((struct edge_list *));
 119 static void new_edge PARAMS ((int, int));
 120
 121 /* A region is the main entity for interblock scheduling: insns
 122    are allowed to move between blocks in the same region, along
 123    control flow graph edges, in the 'up' direction.  */
 124 typedef struct
 125 {
 126   int rgn_nr_blocks;            /* Number of blocks in region.  */
 127   int rgn_blocks;               /* cblocks in the region (actually index in rgn_bb_table).  */
 128 }
 129 region;
 130
 131 /* Number of regions in the procedure.  */
 132 static int nr_regions;
 133
 134 /* Table of region descriptions.  */
 135 static region *rgn_table;
 136
 137 /* Array of lists of regions' blocks.  */
 138 static int *rgn_bb_table;
 139
 140 /* Topological order of blocks in the region (if b2 is reachable from
 141    b1, block_to_bb[b2] > block_to_bb[b1]).  Note: A basic block is
 142    always referred to by either block or b, while its topological
 143    order name (in the region) is refered to by bb.  */
 144 static int *block_to_bb;
 145
 146 /* The number of the region containing a block.  */
 147 static int *containing_rgn;
 148
 149 #define RGN_NR_BLOCKS(rgn) (rgn_table[rgn].rgn_nr_blocks)
 150 #define RGN_BLOCKS(rgn) (rgn_table[rgn].rgn_blocks)
 151 #define BLOCK_TO_BB(block) (block_to_bb[block])
 152 #define CONTAINING_RGN(block) (containing_rgn[block])
 153
 154 void debug_regions PARAMS ((void));
 155 static void find_single_block_region PARAMS ((void));
 156 static void find_rgns PARAMS ((struct edge_list *, dominance_info));
 157 static int too_large PARAMS ((int, int *, int *));
 158
 159 extern void debug_live PARAMS ((int, int));
 160
 161 /* Blocks of the current region being scheduled.  */
 162 static int current_nr_blocks;
 163 static int current_blocks;
 164
 165 /* The mapping from bb to block.  */
 166 #define BB_TO_BLOCK(bb) (rgn_bb_table[current_blocks + (bb)])
 167
 168 typedef struct
 169 {
 170   int *first_member;            /* Pointer to the list start in bitlst_table.  */
 171   int nr_members;               /* The number of members of the bit list.  */
 172 }
 173 bitlst;
 174
 175 static int bitlst_table_last;
 176 static int bitlst_table_size;
 177 static int *bitlst_table;
 178
 179 static void extract_bitlst PARAMS ((sbitmap, bitlst *));
 180
 181 /* Target info declarations.
 182
 183    The block currently being scheduled is referred to as the "target" block,
 184    while other blocks in the region from which insns can be moved to the
 185    target are called "source" blocks.  The candidate structure holds info
 186    about such sources: are they valid?  Speculative?  Etc.  */
 187 typedef bitlst bblst;
 188 typedef struct
 189 {
 190   char is_valid;
 191   char is_speculative;
 192   int src_prob;
 193   bblst split_bbs;
 194   bblst update_bbs;
 195 }
 196 candidate;
 197
 198 static candidate *candidate_table;
 199
 200 /* A speculative motion requires checking live information on the path
 201    from 'source' to 'target'.  The split blocks are those to be checked.
 202    After a speculative motion, live information should be modified in
 203    the 'update' blocks.
 204
 205    Lists of split and update blocks for each candidate of the current
 206    target are in array bblst_table.  */
 207 static int *bblst_table, bblst_size, bblst_last;
 208
 209 #define IS_VALID(src) ( candidate_table[src].is_valid )
 210 #define IS_SPECULATIVE(src) ( candidate_table[src].is_speculative )
 211 #define SRC_PROB(src) ( candidate_table[src].src_prob )
 212
 213 /* The bb being currently scheduled.  */
 214 static int target_bb;
 215
 216 /* List of edges.  */
 217 typedef bitlst edgelst;
 218
 219 /* Target info functions.  */
 220 static void split_edges PARAMS ((int, int, edgelst *));
 221 static void compute_trg_info PARAMS ((int));
 222 void debug_candidate PARAMS ((int));
 223 void debug_candidates PARAMS ((int));
 224
 225 /* Dominators array: dom[i] contains the sbitmap of dominators of
 226    bb i in the region.  */
 227 static sbitmap *dom;
 228
 229 /* bb 0 is the only region entry.  */
 230 #define IS_RGN_ENTRY(bb) (!bb)
 231
 232 /* Is bb_src dominated by bb_trg.  */
 233 #define IS_DOMINATED(bb_src, bb_trg)                                 \
 234 ( TEST_BIT (dom[bb_src], bb_trg) )
 235
 236 /* Probability: Prob[i] is a float in [0, 1] which is the probability
 237    of bb i relative to the region entry.  */
 238 static float *prob;
 239
 240 /* The probability of bb_src, relative to bb_trg.  Note, that while the
 241    'prob[bb]' is a float in [0, 1], this macro returns an integer
 242    in [0, 100].  */
 243 #define GET_SRC_PROB(bb_src, bb_trg) ((int) (100.0 * (prob[bb_src] / \
 244                                                       prob[bb_trg])))
 245
 246 /* Bit-set of edges, where bit i stands for edge i.  */
 247 typedef sbitmap edgeset;
 248
 249 /* Number of edges in the region.  */
 250 static int rgn_nr_edges;
 251
 252 /* Array of size rgn_nr_edges.  */
 253 static int *rgn_edges;
 254
 255
 256 /* Mapping from each edge in the graph to its number in the rgn.  */
 257 static int *edge_to_bit;
 258 #define EDGE_TO_BIT(edge) (edge_to_bit[edge])
 259
 260 /* The split edges of a source bb is different for each target
 261    bb.  In order to compute this efficiently, the 'potential-split edges'
 262    are computed for each bb prior to scheduling a region.  This is actually
 263    the split edges of each bb relative to the region entry.
 264
 265    pot_split[bb] is the set of potential split edges of bb.  */
 266 static edgeset *pot_split;
 267
 268 /* For every bb, a set of its ancestor edges.  */
 269 static edgeset *ancestor_edges;
 270
 271 static void compute_dom_prob_ps PARAMS ((int));
 272
 273 #define INSN_PROBABILITY(INSN) (SRC_PROB (BLOCK_TO_BB (BLOCK_NUM (INSN))))
 274 #define IS_SPECULATIVE_INSN(INSN) (IS_SPECULATIVE (BLOCK_TO_BB (BLOCK_NUM (INSN))))
 275 #define INSN_BB(INSN) (BLOCK_TO_BB (BLOCK_NUM (INSN)))
 276
 277 /* Parameters affecting the decision of rank_for_schedule().
 278    ??? Nope.  But MIN_PROBABILITY is used in copmute_trg_info.  */
 279 #define MIN_PROBABILITY 40
 280
 281 /* Speculative scheduling functions.  */
 282 static int check_live_1 PARAMS ((int, rtx));
 283 static void update_live_1 PARAMS ((int, rtx));
 284 static int check_live PARAMS ((rtx, int));
 285 static void update_live PARAMS ((rtx, int));
 286 static void set_spec_fed PARAMS ((rtx));
 287 static int is_pfree PARAMS ((rtx, int, int));
 288 static int find_conditional_protection PARAMS ((rtx, int));
 289 static int is_conditionally_protected PARAMS ((rtx, int, int));
 290 static int may_trap_exp PARAMS ((rtx, int));
 291 static int haifa_classify_insn PARAMS ((rtx));
 292 static int is_prisky PARAMS ((rtx, int, int));
 293 static int is_exception_free PARAMS ((rtx, int, int));
 294
 295 static bool sets_likely_spilled PARAMS ((rtx));
 296 static void sets_likely_spilled_1 PARAMS ((rtx, rtx, void *));
 297 static void add_branch_dependences PARAMS ((rtx, rtx));
 298 static void compute_block_backward_dependences PARAMS ((int));
 299 void debug_dependencies PARAMS ((void));
 300
 301 static void init_regions PARAMS ((void));
 302 static void schedule_region PARAMS ((int));
 303 static rtx concat_INSN_LIST PARAMS ((rtx, rtx));
 304 static void concat_insn_mem_list PARAMS ((rtx, rtx, rtx *, rtx *));
 305 static void propagate_deps PARAMS ((int, struct deps *));
 306 static void free_pending_lists PARAMS ((void));
 307
 308 /* Functions for construction of the control flow graph.  */
 309
 310 /* Return 1 if control flow graph should not be constructed, 0 otherwise.
 311
 312    We decide not to build the control flow graph if there is possibly more
 313    than one entry to the function, if computed branches exist, of if we
 314    have nonlocal gotos.  */
 315
 316 static int
 317 is_cfg_nonregular ()
 318 {
 319   basic_block b;
 320   rtx insn;
 321   RTX_CODE code;
 322
 323   /* If we have a label that could be the target of a nonlocal goto, then
 324      the cfg is not well structured.  */
 325   if (nonlocal_goto_handler_labels)
 326     return 1;
 327
 328   /* If we have any forced labels, then the cfg is not well structured.  */
 329   if (forced_labels)
 330     return 1;
 331
 332   /* If this function has a computed jump, then we consider the cfg
 333      not well structured.  */
 334   if (current_function_has_computed_jump)
 335     return 1;
 336
 337   /* If we have exception handlers, then we consider the cfg not well
 338      structured.  ?!?  We should be able to handle this now that flow.c
 339      computes an accurate cfg for EH.  */
 340   if (current_function_has_exception_handlers ())
 341     return 1;
 342
 343   /* If we have non-jumping insns which refer to labels, then we consider
 344      the cfg not well structured.  */
 345   /* Check for labels referred to other thn by jumps.  */
 346   FOR_EACH_BB (b)
 347     for (insn = b->head;; insn = NEXT_INSN (insn))
 348       {
 349         code = GET_CODE (insn);
 350         if (GET_RTX_CLASS (code) == 'i' && code != JUMP_INSN)
 351           {
 352             rtx note = find_reg_note (insn, REG_LABEL, NULL_RTX);
 353
 354             if (note
 355                 && ! (GET_CODE (NEXT_INSN (insn)) == JUMP_INSN
 356                       && find_reg_note (NEXT_INSN (insn), REG_LABEL,
 357                                         XEXP (note, 0))))
 358               return 1;
 359           }
 360
 361         if (insn == b->end)
 362           break;
 363       }
 364
 365   /* All the tests passed.  Consider the cfg well structured.  */
 366   return 0;
 367 }
 368
 369 /* Build the control flow graph and set nr_edges.
 370
 371    Instead of trying to build a cfg ourselves, we rely on flow to
 372    do it for us.  Stamp out useless code (and bug) duplication.
 373
 374    Return nonzero if an irregularity in the cfg is found which would
 375    prevent cross block scheduling.  */
 376
 377 static int
 378 build_control_flow (edge_list)
 379      struct edge_list *edge_list;
 380 {
 381   int i, unreachable, num_edges;
 382   basic_block b;
 383
 384   /* This already accounts for entry/exit edges.  */
 385   num_edges = NUM_EDGES (edge_list);
 386
 387   /* Unreachable loops with more than one basic block are detected
 388      during the DFS traversal in find_rgns.
 389
 390      Unreachable loops with a single block are detected here.  This
 391      test is redundant with the one in find_rgns, but it's much
 392     cheaper to go ahead and catch the trivial case here.  */
 393   unreachable = 0;
 394   FOR_EACH_BB (b)
 395     {
 396       if (b->pred == NULL
 397           || (b->pred->src == b
 398               && b->pred->pred_next == NULL))
 399         unreachable = 1;
 400     }
 401
 402   /* ??? We can kill these soon.  */
 403   in_edges = (int *) xcalloc (last_basic_block, sizeof (int));
 404   out_edges = (int *) xcalloc (last_basic_block, sizeof (int));
 405   edge_table = (haifa_edge *) xcalloc (num_edges, sizeof (haifa_edge));
 406
 407   nr_edges = 0;
 408   for (i = 0; i < num_edges; i++)
 409     {
 410       edge e = INDEX_EDGE (edge_list, i);
 411
 412       if (e->dest != EXIT_BLOCK_PTR
 413           && e->src != ENTRY_BLOCK_PTR)
 414         new_edge (e->src->index, e->dest->index);
 415     }
 416
 417   /* Increment by 1, since edge 0 is unused.  */
 418   nr_edges++;
 419
 420   return unreachable;
 421 }
 422
 423 /* Record an edge in the control flow graph from SOURCE to TARGET.
 424
 425    In theory, this is redundant with the s_succs computed above, but
 426    we have not converted all of haifa to use information from the
 427    integer lists.  */
 428
 429 static void
 430 new_edge (source, target)
 431      int source, target;
 432 {
 433   int e, next_edge;
 434   int curr_edge, fst_edge;
 435
 436   /* Check for duplicates.  */
 437   fst_edge = curr_edge = OUT_EDGES (source);
 438   while (curr_edge)
 439     {
 440       if (FROM_BLOCK (curr_edge) == source
 441           && TO_BLOCK (curr_edge) == target)
 442         {
 443           return;
 444         }
 445
 446       curr_edge = NEXT_OUT (curr_edge);
 447
 448       if (fst_edge == curr_edge)
 449         break;
 450     }
 451
 452   e = ++nr_edges;
 453
 454   FROM_BLOCK (e) = source;
 455   TO_BLOCK (e) = target;
 456
 457   if (OUT_EDGES (source))
 458     {
 459       next_edge = NEXT_OUT (OUT_EDGES (source));
 460       NEXT_OUT (OUT_EDGES (source)) = e;
 461       NEXT_OUT (e) = next_edge;
 462     }
 463   else
 464     {
 465       OUT_EDGES (source) = e;
 466       NEXT_OUT (e) = e;
 467     }
 468
 469   if (IN_EDGES (target))
 470     {
 471       next_edge = NEXT_IN (IN_EDGES (target));
 472       NEXT_IN (IN_EDGES (target)) = e;
 473       NEXT_IN (e) = next_edge;
 474     }
 475   else
 476     {
 477       IN_EDGES (target) = e;
 478       NEXT_IN (e) = e;
 479     }
 480 }
 481
 482 /* Translate a bit-set SET to a list BL of the bit-set members.  */
 483
 484 static void
 485 extract_bitlst (set, bl)
 486      sbitmap set;
 487      bitlst *bl;
 488 {
 489   int i;
 490
 491   /* bblst table space is reused in each call to extract_bitlst.  */
 492   bitlst_table_last = 0;
 493
 494   bl->first_member = &bitlst_table[bitlst_table_last];
 495   bl->nr_members = 0;
 496
 497   /* Iterate over each word in the bitset.  */
 498   EXECUTE_IF_SET_IN_SBITMAP (set, 0, i,
 499   {
 500     bitlst_table[bitlst_table_last++] = i;
 501     (bl->nr_members)++;
 502   });
 503
 504 }
 505
 506 /* Functions for the construction of regions.  */
 507
 508 /* Print the regions, for debugging purposes.  Callable from debugger.  */
 509
 510 void
 511 debug_regions ()
 512 {
 513   int rgn, bb;
 514
 515   fprintf (sched_dump, "\n;;   ------------ REGIONS ----------\n\n");
 516   for (rgn = 0; rgn < nr_regions; rgn++)
 517     {
 518       fprintf (sched_dump, ";;\trgn %d nr_blocks %d:\n", rgn,
 519                rgn_table[rgn].rgn_nr_blocks);
 520       fprintf (sched_dump, ";;\tbb/block: ");
 521
 522       for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++)
 523         {
 524           current_blocks = RGN_BLOCKS (rgn);
 525
 526           if (bb != BLOCK_TO_BB (BB_TO_BLOCK (bb)))
 527             abort ();
 528
 529           fprintf (sched_dump, " %d/%d ", bb, BB_TO_BLOCK (bb));
 530         }
 531
 532       fprintf (sched_dump, "\n\n");
 533     }
 534 }
 535
 536 /* Build a single block region for each basic block in the function.
 537    This allows for using the same code for interblock and basic block
 538    scheduling.  */
 539
 540 static void
 541 find_single_block_region ()
 542 {
 543   basic_block bb;
 544
 545   nr_regions = 0;
 546
 547   FOR_EACH_BB (bb)
 548     {
 549       rgn_bb_table[nr_regions] = bb->index;
 550       RGN_NR_BLOCKS (nr_regions) = 1;
 551       RGN_BLOCKS (nr_regions) = nr_regions;
 552       CONTAINING_RGN (bb->index) = nr_regions;
 553       BLOCK_TO_BB (bb->index) = 0;
 554       nr_regions++;
 555     }
 556 }
 557
 558 /* Update number of blocks and the estimate for number of insns
 559    in the region.  Return 1 if the region is "too large" for interblock
 560    scheduling (compile time considerations), otherwise return 0.  */
 561
 562 static int
 563 too_large (block, num_bbs, num_insns)
 564      int block, *num_bbs, *num_insns;
 565 {
 566   (*num_bbs)++;
 567   (*num_insns) += (INSN_LUID (BLOCK_END (block)) -
 568                    INSN_LUID (BLOCK_HEAD (block)));
 569   if ((*num_bbs > MAX_RGN_BLOCKS) || (*num_insns > MAX_RGN_INSNS))
 570     return 1;
 571   else
 572     return 0;
 573 }
 574
 575 /* Update_loop_relations(blk, hdr): Check if the loop headed by max_hdr[blk]
 576    is still an inner loop.  Put in max_hdr[blk] the header of the most inner
 577    loop containing blk.  */
 578 #define UPDATE_LOOP_RELATIONS(blk, hdr)         \
 579 {                                               \
 580   if (max_hdr[blk] == -1)                       \
 581     max_hdr[blk] = hdr;                         \
 582   else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr])  \
 583     RESET_BIT (inner, hdr);                     \
 584   else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr])  \
 585     {                                           \
 586       RESET_BIT (inner,max_hdr[blk]);           \
 587       max_hdr[blk] = hdr;                       \
 588     }                                           \
 589 }
 590
 591 /* Find regions for interblock scheduling.
 592
 593    A region for scheduling can be:
 594
 595      * A loop-free procedure, or
 596
 597      * A reducible inner loop, or
 598
 599      * A basic block not contained in any other region.
 600
 601    ?!? In theory we could build other regions based on extended basic
 602    blocks or reverse extended basic blocks.  Is it worth the trouble?
 603
 604    Loop blocks that form a region are put into the region's block list
 605    in topological order.
 606
 607    This procedure stores its results into the following global (ick) variables
 608
 609      * rgn_nr
 610      * rgn_table
 611      * rgn_bb_table
 612      * block_to_bb
 613      * containing region
 614
 615    We use dominator relationships to avoid making regions out of non-reducible
 616    loops.
 617
 618    This procedure needs to be converted to work on pred/succ lists instead
 619    of edge tables.  That would simplify it somewhat.  */
 620
 621 static void
 622 find_rgns (edge_list, dom)
 623      struct edge_list *edge_list;
 624      dominance_info dom;
 625 {
 626   int *max_hdr, *dfs_nr, *stack, *degree;
 627   char no_loops = 1;
 628   int node, child, loop_head, i, head, tail;
 629   int count = 0, sp, idx = 0, current_edge = out_edges[0];
 630   int num_bbs, num_insns, unreachable;
 631   int too_large_failure;
 632   basic_block bb;
 633
 634   /* Note if an edge has been passed.  */
 635   sbitmap passed;
 636
 637   /* Note if a block is a natural loop header.  */
 638   sbitmap header;
 639
 640   /* Note if a block is a natural inner loop header.  */
 641   sbitmap inner;
 642
 643   /* Note if a block is in the block queue.  */
 644   sbitmap in_queue;
 645
 646   /* Note if a block is in the block queue.  */
 647   sbitmap in_stack;
 648
 649   int num_edges = NUM_EDGES (edge_list);
 650
 651   /* Perform a DFS traversal of the cfg.  Identify loop headers, inner loops
 652      and a mapping from block to its loop header (if the block is contained
 653      in a loop, else -1).
 654
 655      Store results in HEADER, INNER, and MAX_HDR respectively, these will
 656      be used as inputs to the second traversal.
 657
 658      STACK, SP and DFS_NR are only used during the first traversal.  */
 659
 660   /* Allocate and initialize variables for the first traversal.  */
 661   max_hdr = (int *) xmalloc (last_basic_block * sizeof (int));
 662   dfs_nr = (int *) xcalloc (last_basic_block, sizeof (int));
 663   stack = (int *) xmalloc (nr_edges * sizeof (int));
 664
 665   inner = sbitmap_alloc (last_basic_block);
 666   sbitmap_ones (inner);
 667
 668   header = sbitmap_alloc (last_basic_block);
 669   sbitmap_zero (header);
 670
 671   passed = sbitmap_alloc (nr_edges);
 672   sbitmap_zero (passed);
 673
 674   in_queue = sbitmap_alloc (last_basic_block);
 675   sbitmap_zero (in_queue);
 676
 677   in_stack = sbitmap_alloc (last_basic_block);
 678   sbitmap_zero (in_stack);
 679
 680   for (i = 0; i < last_basic_block; i++)
 681     max_hdr[i] = -1;
 682
 683   /* DFS traversal to find inner loops in the cfg.  */
 684
 685   sp = -1;
 686   while (1)
 687     {
 688       if (current_edge == 0 || TEST_BIT (passed, current_edge))
 689         {
 690           /* We have reached a leaf node or a node that was already
 691              processed.  Pop edges off the stack until we find
 692              an edge that has not yet been processed.  */
 693           while (sp >= 0
 694                  && (current_edge == 0 || TEST_BIT (passed, current_edge)))
 695             {
 696               /* Pop entry off the stack.  */
 697               current_edge = stack[sp--];
 698               node = FROM_BLOCK (current_edge);
 699               child = TO_BLOCK (current_edge);
 700               RESET_BIT (in_stack, child);
 701               if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child]))
 702                 UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
 703               current_edge = NEXT_OUT (current_edge);
 704             }
 705
 706           /* See if have finished the DFS tree traversal.  */
 707           if (sp < 0 && TEST_BIT (passed, current_edge))
 708             break;
 709
 710           /* Nope, continue the traversal with the popped node.  */
 711           continue;
 712         }
 713
 714       /* Process a node.  */
 715       node = FROM_BLOCK (current_edge);
 716       child = TO_BLOCK (current_edge);
 717       SET_BIT (in_stack, node);
 718       dfs_nr[node] = ++count;
 719
 720       /* If the successor is in the stack, then we've found a loop.
 721          Mark the loop, if it is not a natural loop, then it will
 722          be rejected during the second traversal.  */
 723       if (TEST_BIT (in_stack, child))
 724         {
 725           no_loops = 0;
 726           SET_BIT (header, child);
 727           UPDATE_LOOP_RELATIONS (node, child);
 728           SET_BIT (passed, current_edge);
 729           current_edge = NEXT_OUT (current_edge);
 730           continue;
 731         }
 732
 733       /* If the child was already visited, then there is no need to visit
 734          it again.  Just update the loop relationships and restart
 735          with a new edge.  */
 736       if (dfs_nr[child])
 737         {
 738           if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child]))
 739             UPDATE_LOOP_RELATIONS (node, max_hdr[child]);
 740           SET_BIT (passed, current_edge);
 741           current_edge = NEXT_OUT (current_edge);
 742           continue;
 743         }
 744
 745       /* Push an entry on the stack and continue DFS traversal.  */
 746       stack[++sp] = current_edge;
 747       SET_BIT (passed, current_edge);
 748       current_edge = OUT_EDGES (child);
 749
 750       /* This is temporary until haifa is converted to use rth's new
 751          cfg routines which have true entry/exit blocks and the
 752          appropriate edges from/to those blocks.
 753
 754          Generally we update dfs_nr for a node when we process its
 755          out edge.  However, if the node has no out edge then we will
 756          not set dfs_nr for that node.  This can confuse the scheduler
 757          into thinking that we have unreachable blocks, which in turn
 758          disables cross block scheduling.
 759
 760          So, if we have a node with no out edges, go ahead and mark it
 761          as reachable now.  */
 762       if (current_edge == 0)
 763         dfs_nr[child] = ++count;
 764     }
 765
 766   /* Another check for unreachable blocks.  The earlier test in
 767      is_cfg_nonregular only finds unreachable blocks that do not
 768      form a loop.
 769
 770      The DFS traversal will mark every block that is reachable from
 771      the entry node by placing a nonzero value in dfs_nr.  Thus if
 772      dfs_nr is zero for any block, then it must be unreachable.  */
 773   unreachable = 0;
 774   FOR_EACH_BB (bb)
 775     if (dfs_nr[bb->index] == 0)
 776       {
 777         unreachable = 1;
 778         break;
 779       }
 780
 781   /* Gross.  To avoid wasting memory, the second pass uses the dfs_nr array
 782      to hold degree counts.  */
 783   degree = dfs_nr;
 784
 785   FOR_EACH_BB (bb)
 786     degree[bb->index] = 0;
 787   for (i = 0; i < num_edges; i++)
 788     {
 789       edge e = INDEX_EDGE (edge_list, i);
 790
 791       if (e->dest != EXIT_BLOCK_PTR)
 792         degree[e->dest->index]++;
 793     }
 794
 795   /* Do not perform region scheduling if there are any unreachable
 796      blocks.  */
 797   if (!unreachable)
 798     {
 799       int *queue;
 800
 801       if (no_loops)
 802         SET_BIT (header, 0);
 803
 804       /* Second travsersal:find reducible inner loops and topologically sort
 805          block of each region.  */
 806
 807       queue = (int *) xmalloc (n_basic_blocks * sizeof (int));
 808
 809       /* Find blocks which are inner loop headers.  We still have non-reducible
 810          loops to consider at this point.  */
 811       FOR_EACH_BB (bb)
 812         {
 813           if (TEST_BIT (header, bb->index) && TEST_BIT (inner, bb->index))
 814             {
 815               edge e;
 816               basic_block jbb;
 817
 818               /* Now check that the loop is reducible.  We do this separate
 819                  from finding inner loops so that we do not find a reducible
 820                  loop which contains an inner non-reducible loop.
 821
 822                  A simple way to find reducible/natural loops is to verify
 823                  that each block in the loop is dominated by the loop
 824                  header.
 825
 826                  If there exists a block that is not dominated by the loop
 827                  header, then the block is reachable from outside the loop
 828                  and thus the loop is not a natural loop.  */
 829               FOR_EACH_BB (jbb)
 830                 {
 831                   /* First identify blocks in the loop, except for the loop
 832                      entry block.  */
 833                   if (bb->index == max_hdr[jbb->index] && bb != jbb)
 834                     {
 835                       /* Now verify that the block is dominated by the loop
 836                          header.  */
 837                       if (!dominated_by_p (dom, jbb, bb))
 838                         break;
 839                     }
 840                 }
 841
 842               /* If we exited the loop early, then I is the header of
 843                  a non-reducible loop and we should quit processing it
 844                  now.  */
 845               if (jbb != EXIT_BLOCK_PTR)
 846                 continue;
 847
 848               /* I is a header of an inner loop, or block 0 in a subroutine
 849                  with no loops at all.  */
 850               head = tail = -1;
 851               too_large_failure = 0;
 852               loop_head = max_hdr[bb->index];
 853
 854               /* Decrease degree of all I's successors for topological
 855                  ordering.  */
 856               for (e = bb->succ; e; e = e->succ_next)
 857                 if (e->dest != EXIT_BLOCK_PTR)
 858                   --degree[e->dest->index];
 859
 860               /* Estimate # insns, and count # blocks in the region.  */
 861               num_bbs = 1;
 862               num_insns = (INSN_LUID (bb->end)
 863                            - INSN_LUID (bb->head));
 864
 865               /* Find all loop latches (blocks with back edges to the loop
 866                  header) or all the leaf blocks in the cfg has no loops.
 867
 868                  Place those blocks into the queue.  */
 869               if (no_loops)
 870                 {
 871                   FOR_EACH_BB (jbb)
 872                     /* Leaf nodes have only a single successor which must
 873                        be EXIT_BLOCK.  */
 874                     if (jbb->succ
 875                         && jbb->succ->dest == EXIT_BLOCK_PTR
 876                         && jbb->succ->succ_next == NULL)
 877                       {
 878                         queue[++tail] = jbb->index;
 879                         SET_BIT (in_queue, jbb->index);
 880
 881                         if (too_large (jbb->index, &num_bbs, &num_insns))
 882                           {
 883                             too_large_failure = 1;
 884                             break;
 885                           }
 886                       }
 887                 }
 888               else
 889                 {
 890                   edge e;
 891
 892                   for (e = bb->pred; e; e = e->pred_next)
 893                     {
 894                       if (e->src == ENTRY_BLOCK_PTR)
 895                         continue;
 896
 897                       node = e->src->index;
 898
 899                       if (max_hdr[node] == loop_head && node != bb->index)
 900                         {
 901                           /* This is a loop latch.  */
 902                           queue[++tail] = node;
 903                           SET_BIT (in_queue, node);
 904
 905                           if (too_large (node, &num_bbs, &num_insns))
 906                             {
 907                               too_large_failure = 1;
 908                               break;
 909                             }
 910                         }
 911                     }
 912                 }
 913
 914               /* Now add all the blocks in the loop to the queue.
 915
 916              We know the loop is a natural loop; however the algorithm
 917              above will not always mark certain blocks as being in the
 918              loop.  Consider:
 919                 node   children
 920                  a        b,c
 921                  b        c
 922                  c        a,d
 923                  d        b
 924
 925              The algorithm in the DFS traversal may not mark B & D as part
 926              of the loop (ie they will not have max_hdr set to A).
 927
 928              We know they can not be loop latches (else they would have
 929              had max_hdr set since they'd have a backedge to a dominator
 930              block).  So we don't need them on the initial queue.
 931
 932              We know they are part of the loop because they are dominated
 933              by the loop header and can be reached by a backwards walk of
 934              the edges starting with nodes on the initial queue.
 935
 936              It is safe and desirable to include those nodes in the
 937              loop/scheduling region.  To do so we would need to decrease
 938              the degree of a node if it is the target of a backedge
 939              within the loop itself as the node is placed in the queue.
 940
 941              We do not do this because I'm not sure that the actual
 942              scheduling code will properly handle this case. ?!? */
 943
 944               while (head < tail && !too_large_failure)
 945                 {
 946                   edge e;
 947                   child = queue[++head];
 948
 949                   for (e = BASIC_BLOCK (child)->pred; e; e = e->pred_next)
 950                     {
 951                       node = e->src->index;
 952
 953                       /* See discussion above about nodes not marked as in
 954                          this loop during the initial DFS traversal.  */
 955                       if (e->src == ENTRY_BLOCK_PTR
 956                           || max_hdr[node] != loop_head)
 957                         {
 958                           tail = -1;
 959                           break;
 960                         }
 961                       else if (!TEST_BIT (in_queue, node) && node != bb->index)
 962                         {
 963                           queue[++tail] = node;
 964                           SET_BIT (in_queue, node);
 965
 966                           if (too_large (node, &num_bbs, &num_insns))
 967                             {
 968                               too_large_failure = 1;
 969                               break;
 970                             }
 971                         }
 972                     }
 973                 }
 974
 975               if (tail >= 0 && !too_large_failure)
 976                 {
 977                   /* Place the loop header into list of region blocks.  */
 978                   degree[bb->index] = -1;
 979                   rgn_bb_table[idx] = bb->index;
 980                   RGN_NR_BLOCKS (nr_regions) = num_bbs;
 981                   RGN_BLOCKS (nr_regions) = idx++;
 982                   CONTAINING_RGN (bb->index) = nr_regions;
 983                   BLOCK_TO_BB (bb->index) = count = 0;
 984
 985                   /* Remove blocks from queue[] when their in degree
 986                      becomes zero.  Repeat until no blocks are left on the
 987                      list.  This produces a topological list of blocks in
 988                      the region.  */
 989                   while (tail >= 0)
 990                     {
 991                       if (head < 0)
 992                         head = tail;
 993                       child = queue[head];
 994                       if (degree[child] == 0)
 995                         {
 996                           edge e;
 997
 998                           degree[child] = -1;
 999                           rgn_bb_table[idx++] = child;
1000                           BLOCK_TO_BB (child) = ++count;
1001                           CONTAINING_RGN (child) = nr_regions;
1002                           queue[head] = queue[tail--];
1003
1004                           for (e = BASIC_BLOCK (child)->succ;
1005                                e;
1006                                e = e->succ_next)
1007                             if (e->dest != EXIT_BLOCK_PTR)
1008                               --degree[e->dest->index];
1009                         }
1010                       else
1011                         --head;
1012                     }
1013                   ++nr_regions;
1014                 }
1015             }
1016         }
1017       free (queue);
1018     }
1019
1020   /* Any block that did not end up in a region is placed into a region
1021      by itself.  */
1022   FOR_EACH_BB (bb)
1023     if (degree[bb->index] >= 0)
1024       {
1025         rgn_bb_table[idx] = bb->index;
1026         RGN_NR_BLOCKS (nr_regions) = 1;
1027         RGN_BLOCKS (nr_regions) = idx++;
1028         CONTAINING_RGN (bb->index) = nr_regions++;
1029         BLOCK_TO_BB (bb->index) = 0;
1030       }
1031
1032   free (max_hdr);
1033   free (dfs_nr);
1034   free (stack);
1035   sbitmap_free (passed);
1036   sbitmap_free (header);
1037   sbitmap_free (inner);
1038   sbitmap_free (in_queue);
1039   sbitmap_free (in_stack);
1040 }
1041
1042 /* Functions for regions scheduling information.  */
1043
1044 /* Compute dominators, probability, and potential-split-edges of bb.
1045    Assume that these values were already computed for bb's predecessors.  */
1046
1047 static void
1048 compute_dom_prob_ps (bb)
1049      int bb;
1050 {
1051   int nxt_in_edge, fst_in_edge, pred;
1052   int fst_out_edge, nxt_out_edge, nr_out_edges, nr_rgn_out_edges;
1053
1054   prob[bb] = 0.0;
1055   if (IS_RGN_ENTRY (bb))
1056     {
1057       SET_BIT (dom[bb], 0);
1058       prob[bb] = 1.0;
1059       return;
1060     }
1061
1062   fst_in_edge = nxt_in_edge = IN_EDGES (BB_TO_BLOCK (bb));
1063
1064   /* Initialize dom[bb] to '111..1'.  */
1065   sbitmap_ones (dom[bb]);
1066
1067   do
1068     {
1069       pred = FROM_BLOCK (nxt_in_edge);
1070       sbitmap_a_and_b (dom[bb], dom[bb], dom[BLOCK_TO_BB (pred)]);
1071       sbitmap_a_or_b (ancestor_edges[bb], ancestor_edges[bb], ancestor_edges[BLOCK_TO_BB (pred)]);
1072
1073       SET_BIT (ancestor_edges[bb], EDGE_TO_BIT (nxt_in_edge));
1074
1075       nr_out_edges = 1;
1076       nr_rgn_out_edges = 0;
1077       fst_out_edge = OUT_EDGES (pred);
1078       nxt_out_edge = NEXT_OUT (fst_out_edge);
1079
1080       sbitmap_a_or_b (pot_split[bb], pot_split[bb], pot_split[BLOCK_TO_BB (pred)]);
1081
1082       SET_BIT (pot_split[bb], EDGE_TO_BIT (fst_out_edge));
1083
1084       /* The successor doesn't belong in the region?  */
1085       if (CONTAINING_RGN (TO_BLOCK (fst_out_edge)) !=
1086           CONTAINING_RGN (BB_TO_BLOCK (bb)))
1087         ++nr_rgn_out_edges;
1088
1089       while (fst_out_edge != nxt_out_edge)
1090         {
1091           ++nr_out_edges;
1092           /* The successor doesn't belong in the region?  */
1093           if (CONTAINING_RGN (TO_BLOCK (nxt_out_edge)) !=
1094               CONTAINING_RGN (BB_TO_BLOCK (bb)))
1095             ++nr_rgn_out_edges;
1096           SET_BIT (pot_split[bb], EDGE_TO_BIT (nxt_out_edge));
1097           nxt_out_edge = NEXT_OUT (nxt_out_edge);
1098
1099         }
1100
1101       /* Now nr_rgn_out_edges is the number of region-exit edges from
1102          pred, and nr_out_edges will be the number of pred out edges
1103          not leaving the region.  */
1104       nr_out_edges -= nr_rgn_out_edges;
1105       if (nr_rgn_out_edges > 0)
1106         prob[bb] += 0.9 * prob[BLOCK_TO_BB (pred)] / nr_out_edges;
1107       else
1108         prob[bb] += prob[BLOCK_TO_BB (pred)] / nr_out_edges;
1109       nxt_in_edge = NEXT_IN (nxt_in_edge);
1110     }
1111   while (fst_in_edge != nxt_in_edge);
1112
1113   SET_BIT (dom[bb], bb);
1114   sbitmap_difference (pot_split[bb], pot_split[bb], ancestor_edges[bb]);
1115
1116   if (sched_verbose >= 2)
1117     fprintf (sched_dump, ";;  bb_prob(%d, %d) = %3d\n", bb, BB_TO_BLOCK (bb),
1118              (int) (100.0 * prob[bb]));
1119 }
1120
1121 /* Functions for target info.  */
1122
1123 /* Compute in BL the list of split-edges of bb_src relatively to bb_trg.
1124    Note that bb_trg dominates bb_src.  */
1125
1126 static void
1127 split_edges (bb_src, bb_trg, bl)
1128      int bb_src;
1129      int bb_trg;
1130      edgelst *bl;
1131 {
1132   sbitmap src = (edgeset) sbitmap_alloc (pot_split[bb_src]->n_bits);
1133   sbitmap_copy (src, pot_split[bb_src]);
1134
1135   sbitmap_difference (src, src, pot_split[bb_trg]);
1136   extract_bitlst (src, bl);
1137   sbitmap_free (src);
1138 }
1139
1140 /* Find the valid candidate-source-blocks for the target block TRG, compute
1141    their probability, and check if they are speculative or not.
1142    For speculative sources, compute their update-blocks and split-blocks.  */
1143
1144 static void
1145 compute_trg_info (trg)
1146      int trg;
1147 {
1148   candidate *sp;
1149   edgelst el;
1150   int check_block, update_idx;
1151   int i, j, k, fst_edge, nxt_edge;
1152
1153   /* Define some of the fields for the target bb as well.  */
1154   sp = candidate_table + trg;
1155   sp->is_valid = 1;
1156   sp->is_speculative = 0;
1157   sp->src_prob = 100;
1158
1159   for (i = trg + 1; i < current_nr_blocks; i++)
1160     {
1161       sp = candidate_table + i;
1162
1163       sp->is_valid = IS_DOMINATED (i, trg);
1164       if (sp->is_valid)
1165         {
1166           sp->src_prob = GET_SRC_PROB (i, trg);
1167           sp->is_valid = (sp->src_prob >= MIN_PROBABILITY);
1168         }
1169
1170       if (sp->is_valid)
1171         {
1172           split_edges (i, trg, &el);
1173           sp->is_speculative = (el.nr_members) ? 1 : 0;
1174           if (sp->is_speculative && !flag_schedule_speculative)
1175             sp->is_valid = 0;
1176         }
1177
1178       if (sp->is_valid)
1179         {
1180           char *update_blocks;
1181
1182           /* Compute split blocks and store them in bblst_table.
1183              The TO block of every split edge is a split block.  */
1184           sp->split_bbs.first_member = &bblst_table[bblst_last];
1185           sp->split_bbs.nr_members = el.nr_members;
1186           for (j = 0; j < el.nr_members; bblst_last++, j++)
1187             bblst_table[bblst_last] =
1188               TO_BLOCK (rgn_edges[el.first_member[j]]);
1189           sp->update_bbs.first_member = &bblst_table[bblst_last];
1190
1191           /* Compute update blocks and store them in bblst_table.
1192              For every split edge, look at the FROM block, and check
1193              all out edges.  For each out edge that is not a split edge,
1194              add the TO block to the update block list.  This list can end
1195              up with a lot of duplicates.  We need to weed them out to avoid
1196              overrunning the end of the bblst_table.  */
1197           update_blocks = (char *) alloca (last_basic_block);
1198           memset (update_blocks, 0, last_basic_block);
1199
1200           update_idx = 0;
1201           for (j = 0; j < el.nr_members; j++)
1202             {
1203               check_block = FROM_BLOCK (rgn_edges[el.first_member[j]]);
1204               fst_edge = nxt_edge = OUT_EDGES (check_block);
1205               do
1206                 {
1207                   if (! update_blocks[TO_BLOCK (nxt_edge)])
1208                     {
1209                       for (k = 0; k < el.nr_members; k++)
1210                         if (EDGE_TO_BIT (nxt_edge) == el.first_member[k])
1211                           break;
1212
1213                       if (k >= el.nr_members)
1214                         {
1215                           bblst_table[bblst_last++] = TO_BLOCK (nxt_edge);
1216                           update_blocks[TO_BLOCK (nxt_edge)] = 1;
1217                           update_idx++;
1218                         }
1219                     }
1220
1221                   nxt_edge = NEXT_OUT (nxt_edge);
1222                 }
1223               while (fst_edge != nxt_edge);
1224             }
1225           sp->update_bbs.nr_members = update_idx;
1226
1227           /* Make sure we didn't overrun the end of bblst_table.  */
1228           if (bblst_last > bblst_size)
1229             abort ();
1230         }
1231       else
1232         {
1233           sp->split_bbs.nr_members = sp->update_bbs.nr_members = 0;
1234
1235           sp->is_speculative = 0;
1236           sp->src_prob = 0;
1237         }
1238     }
1239 }
1240
1241 /* Print candidates info, for debugging purposes.  Callable from debugger.  */
1242
1243 void
1244 debug_candidate (i)
1245      int i;
1246 {
1247   if (!candidate_table[i].is_valid)
1248     return;
1249
1250   if (candidate_table[i].is_speculative)
1251     {
1252       int j;
1253       fprintf (sched_dump, "src b %d bb %d speculative \n", BB_TO_BLOCK (i), i);
1254
1255       fprintf (sched_dump, "split path: ");
1256       for (j = 0; j < candidate_table[i].split_bbs.nr_members; j++)
1257         {
1258           int b = candidate_table[i].split_bbs.first_member[j];
1259
1260           fprintf (sched_dump, " %d ", b);
1261         }
1262       fprintf (sched_dump, "\n");
1263
1264       fprintf (sched_dump, "update path: ");
1265       for (j = 0; j < candidate_table[i].update_bbs.nr_members; j++)
1266         {
1267           int b = candidate_table[i].update_bbs.first_member[j];
1268
1269           fprintf (sched_dump, " %d ", b);
1270         }
1271       fprintf (sched_dump, "\n");
1272     }
1273   else
1274     {
1275       fprintf (sched_dump, " src %d equivalent\n", BB_TO_BLOCK (i));
1276     }
1277 }
1278
1279 /* Print candidates info, for debugging purposes.  Callable from debugger.  */
1280
1281 void
1282 debug_candidates (trg)
1283      int trg;
1284 {
1285   int i;
1286
1287   fprintf (sched_dump, "----------- candidate table: target: b=%d bb=%d ---\n",
1288            BB_TO_BLOCK (trg), trg);
1289   for (i = trg + 1; i < current_nr_blocks; i++)
1290     debug_candidate (i);
1291 }
1292
1293 /* Functions for speculative scheduing.  */
1294
1295 /* Return 0 if x is a set of a register alive in the beginning of one
1296    of the split-blocks of src, otherwise return 1.  */
1297
1298 static int
1299 check_live_1 (src, x)
1300      int src;
1301      rtx x;
1302 {
1303   int i;
1304   int regno;
1305   rtx reg = SET_DEST (x);
1306
1307   if (reg == 0)
1308     return 1;
1309
1310   while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
1311          || GET_CODE (reg) == SIGN_EXTRACT
1312          || GET_CODE (reg) == STRICT_LOW_PART)
1313     reg = XEXP (reg, 0);
1314
1315   if (GET_CODE (reg) == PARALLEL)
1316     {
1317       int i;
1318
1319       for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
1320         if (XEXP (XVECEXP (reg, 0, i), 0) != 0)
1321           if (check_live_1 (src, XEXP (XVECEXP (reg, 0, i), 0)))
1322             return 1;
1323
1324       return 0;
1325     }
1326
1327   if (GET_CODE (reg) != REG)
1328     return 1;
1329
1330   regno = REGNO (reg);
1331
1332   if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
1333     {
1334       /* Global registers are assumed live.  */
1335       return 0;
1336     }
1337   else
1338     {
1339       if (regno < FIRST_PSEUDO_REGISTER)
1340         {
1341           /* Check for hard registers.  */
1342           int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
1343           while (--j >= 0)
1344             {
1345               for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
1346                 {
1347                   int b = candidate_table[src].split_bbs.first_member[i];
1348
1349                   if (REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start,
1350                                        regno + j))
1351                     {
1352                       return 0;
1353                     }
1354                 }
1355             }
1356         }
1357       else
1358         {
1359           /* Check for psuedo registers.  */
1360           for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++)
1361             {
1362               int b = candidate_table[src].split_bbs.first_member[i];
1363
1364               if (REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start, regno))
1365                 {
1366                   return 0;
1367                 }
1368             }
1369         }
1370     }
1371
1372   return 1;
1373 }
1374
1375 /* If x is a set of a register R, mark that R is alive in the beginning
1376    of every update-block of src.  */
1377
1378 static void
1379 update_live_1 (src, x)
1380      int src;
1381      rtx x;
1382 {
1383   int i;
1384   int regno;
1385   rtx reg = SET_DEST (x);
1386
1387   if (reg == 0)
1388     return;
1389
1390   while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
1391          || GET_CODE (reg) == SIGN_EXTRACT
1392          || GET_CODE (reg) == STRICT_LOW_PART)
1393     reg = XEXP (reg, 0);
1394
1395   if (GET_CODE (reg) == PARALLEL)
1396     {
1397       int i;
1398
1399       for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
1400         if (XEXP (XVECEXP (reg, 0, i), 0) != 0)
1401           update_live_1 (src, XEXP (XVECEXP (reg, 0, i), 0));
1402
1403       return;
1404     }
1405
1406   if (GET_CODE (reg) != REG)
1407     return;
1408
1409   /* Global registers are always live, so the code below does not apply
1410      to them.  */
1411
1412   regno = REGNO (reg);
1413
1414   if (regno >= FIRST_PSEUDO_REGISTER || !global_regs[regno])
1415     {
1416       if (regno < FIRST_PSEUDO_REGISTER)
1417         {
1418           int j = HARD_REGNO_NREGS (regno, GET_MODE (reg));
1419           while (--j >= 0)
1420             {
1421               for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
1422                 {
1423                   int b = candidate_table[src].update_bbs.first_member[i];
1424
1425                   SET_REGNO_REG_SET (BASIC_BLOCK (b)->global_live_at_start,
1426                                      regno + j);
1427                 }
1428             }
1429         }
1430       else
1431         {
1432           for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++)
1433             {
1434               int b = candidate_table[src].update_bbs.first_member[i];
1435
1436               SET_REGNO_REG_SET (BASIC_BLOCK (b)->global_live_at_start, regno);
1437             }
1438         }
1439     }
1440 }
1441
1442 /* Return 1 if insn can be speculatively moved from block src to trg,
1443    otherwise return 0.  Called before first insertion of insn to
1444    ready-list or before the scheduling.  */
1445
1446 static int
1447 check_live (insn, src)
1448      rtx insn;
1449      int src;
1450 {
1451   /* Find the registers set by instruction.  */
1452   if (GET_CODE (PATTERN (insn)) == SET
1453       || GET_CODE (PATTERN (insn)) == CLOBBER)
1454     return check_live_1 (src, PATTERN (insn));
1455   else if (GET_CODE (PATTERN (insn)) == PARALLEL)
1456     {
1457       int j;
1458       for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
1459         if ((GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
1460              || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
1461             && !check_live_1 (src, XVECEXP (PATTERN (insn), 0, j)))
1462           return 0;
1463
1464       return 1;
1465     }
1466
1467   return 1;
1468 }
1469
1470 /* Update the live registers info after insn was moved speculatively from
1471    block src to trg.  */
1472
1473 static void
1474 update_live (insn, src)
1475      rtx insn;
1476      int src;
1477 {
1478   /* Find the registers set by instruction.  */
1479   if (GET_CODE (PATTERN (insn)) == SET
1480       || GET_CODE (PATTERN (insn)) == CLOBBER)
1481     update_live_1 (src, PATTERN (insn));
1482   else if (GET_CODE (PATTERN (insn)) == PARALLEL)
1483     {
1484       int j;
1485       for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
1486         if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
1487             || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
1488           update_live_1 (src, XVECEXP (PATTERN (insn), 0, j));
1489     }
1490 }
1491
1492 /* Exception Free Loads:
1493
1494    We define five classes of speculative loads: IFREE, IRISKY,
1495    PFREE, PRISKY, and MFREE.
1496
1497    IFREE loads are loads that are proved to be exception-free, just
1498    by examining the load insn.  Examples for such loads are loads
1499    from TOC and loads of global data.
1500
1501    IRISKY loads are loads that are proved to be exception-risky,
1502    just by examining the load insn.  Examples for such loads are
1503    volatile loads and loads from shared memory.
1504
1505    PFREE loads are loads for which we can prove, by examining other
1506    insns, that they are exception-free.  Currently, this class consists
1507    of loads for which we are able to find a "similar load", either in
1508    the target block, or, if only one split-block exists, in that split
1509    block.  Load2 is similar to load1 if both have same single base
1510    register.  We identify only part of the similar loads, by finding
1511    an insn upon which both load1 and load2 have a DEF-USE dependence.
1512
1513    PRISKY loads are loads for which we can prove, by examining other
1514    insns, that they are exception-risky.  Currently we have two proofs for
1515    such loads.  The first proof detects loads that are probably guarded by a
1516    test on the memory address.  This proof is based on the
1517    backward and forward data dependence information for the region.
1518    Let load-insn be the examined load.
1519    Load-insn is PRISKY iff ALL the following hold:
1520
1521    - insn1 is not in the same block as load-insn
1522    - there is a DEF-USE dependence chain (insn1, ..., load-insn)
1523    - test-insn is either a compare or a branch, not in the same block
1524      as load-insn
1525    - load-insn is reachable from test-insn
1526    - there is a DEF-USE dependence chain (insn1, ..., test-insn)
1527
1528    This proof might fail when the compare and the load are fed
1529    by an insn not in the region.  To solve this, we will add to this
1530    group all loads that have no input DEF-USE dependence.
1531
1532    The second proof detects loads that are directly or indirectly
1533    fed by a speculative load.  This proof is affected by the
1534    scheduling process.  We will use the flag  fed_by_spec_load.
1535    Initially, all insns have this flag reset.  After a speculative
1536    motion of an insn, if insn is either a load, or marked as
1537    fed_by_spec_load, we will also mark as fed_by_spec_load every
1538    insn1 for which a DEF-USE dependence (insn, insn1) exists.  A
1539    load which is fed_by_spec_load is also PRISKY.
1540
1541    MFREE (maybe-free) loads are all the remaining loads. They may be
1542    exception-free, but we cannot prove it.
1543
1544    Now, all loads in IFREE and PFREE classes are considered
1545    exception-free, while all loads in IRISKY and PRISKY classes are
1546    considered exception-risky.  As for loads in the MFREE class,
1547    these are considered either exception-free or exception-risky,
1548    depending on whether we are pessimistic or optimistic.  We have
1549    to take the pessimistic approach to assure the safety of
1550    speculative scheduling, but we can take the optimistic approach
1551    by invoking the -fsched_spec_load_dangerous option.  */
1552
1553 enum INSN_TRAP_CLASS
1554 {
1555   TRAP_FREE = 0, IFREE = 1, PFREE_CANDIDATE = 2,
1556   PRISKY_CANDIDATE = 3, IRISKY = 4, TRAP_RISKY = 5
1557 };
1558
1559 #define WORST_CLASS(class1, class2) \
1560 ((class1 > class2) ? class1 : class2)
1561
1562 /* Non-zero if block bb_to is equal to, or reachable from block bb_from.  */
1563 #define IS_REACHABLE(bb_from, bb_to)                                    \
1564   (bb_from == bb_to                                                     \
1565    || IS_RGN_ENTRY (bb_from)                                            \
1566    || (TEST_BIT (ancestor_edges[bb_to],                                 \
1567                  EDGE_TO_BIT (IN_EDGES (BB_TO_BLOCK (bb_from))))))
1568
1569 /* Non-zero iff the address is comprised from at most 1 register.  */
1570 #define CONST_BASED_ADDRESS_P(x)                        \
1571   (GET_CODE (x) == REG                                  \
1572    || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS   \
1573         || (GET_CODE (x) == LO_SUM))                    \
1574        && (CONSTANT_P (XEXP (x, 0))                     \
1575            || CONSTANT_P (XEXP (x, 1)))))
1576
1577 /* Turns on the fed_by_spec_load flag for insns fed by load_insn.  */
1578
1579 static void
1580 set_spec_fed (load_insn)
1581      rtx load_insn;
1582 {
1583   rtx link;
1584
1585   for (link = INSN_DEPEND (load_insn); link; link = XEXP (link, 1))
1586     if (GET_MODE (link) == VOIDmode)
1587       FED_BY_SPEC_LOAD (XEXP (link, 0)) = 1;
1588 }                               /* set_spec_fed */
1589
1590 /* On the path from the insn to load_insn_bb, find a conditional
1591 branch depending on insn, that guards the speculative load.  */
1592
1593 static int
1594 find_conditional_protection (insn, load_insn_bb)
1595      rtx insn;
1596      int load_insn_bb;
1597 {
1598   rtx link;
1599
1600   /* Iterate through DEF-USE forward dependences.  */
1601   for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
1602     {
1603       rtx next = XEXP (link, 0);
1604       if ((CONTAINING_RGN (BLOCK_NUM (next)) ==
1605            CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb)))
1606           && IS_REACHABLE (INSN_BB (next), load_insn_bb)
1607           && load_insn_bb != INSN_BB (next)
1608           && GET_MODE (link) == VOIDmode
1609           && (GET_CODE (next) == JUMP_INSN
1610               || find_conditional_protection (next, load_insn_bb)))
1611         return 1;
1612     }
1613   return 0;
1614 }                               /* find_conditional_protection */
1615
1616 /* Returns 1 if the same insn1 that participates in the computation
1617    of load_insn's address is feeding a conditional branch that is
1618    guarding on load_insn. This is true if we find a the two DEF-USE
1619    chains:
1620    insn1 -> ... -> conditional-branch
1621    insn1 -> ... -> load_insn,
1622    and if a flow path exist:
1623    insn1 -> ... -> conditional-branch -> ... -> load_insn,
1624    and if insn1 is on the path
1625    region-entry -> ... -> bb_trg -> ... load_insn.
1626
1627    Locate insn1 by climbing on LOG_LINKS from load_insn.
1628    Locate the branch by following INSN_DEPEND from insn1.  */
1629
1630 static int
1631 is_conditionally_protected (load_insn, bb_src, bb_trg)
1632      rtx load_insn;
1633      int bb_src, bb_trg;
1634 {
1635   rtx link;
1636
1637   for (link = LOG_LINKS (load_insn); link; link = XEXP (link, 1))
1638     {
1639       rtx insn1 = XEXP (link, 0);
1640
1641       /* Must be a DEF-USE dependence upon non-branch.  */
1642       if (GET_MODE (link) != VOIDmode
1643           || GET_CODE (insn1) == JUMP_INSN)
1644         continue;
1645
1646       /* Must exist a path: region-entry -> ... -> bb_trg -> ... load_insn.  */
1647       if (INSN_BB (insn1) == bb_src
1648           || (CONTAINING_RGN (BLOCK_NUM (insn1))
1649               != CONTAINING_RGN (BB_TO_BLOCK (bb_src)))
1650           || (!IS_REACHABLE (bb_trg, INSN_BB (insn1))
1651               && !IS_REACHABLE (INSN_BB (insn1), bb_trg)))
1652         continue;
1653
1654       /* Now search for the conditional-branch.  */
1655       if (find_conditional_protection (insn1, bb_src))
1656         return 1;
1657
1658       /* Recursive step: search another insn1, "above" current insn1.  */
1659       return is_conditionally_protected (insn1, bb_src, bb_trg);
1660     }
1661
1662   /* The chain does not exist.  */
1663   return 0;
1664 }                               /* is_conditionally_protected */
1665
1666 /* Returns 1 if a clue for "similar load" 'insn2' is found, and hence
1667    load_insn can move speculatively from bb_src to bb_trg.  All the
1668    following must hold:
1669
1670    (1) both loads have 1 base register (PFREE_CANDIDATEs).
1671    (2) load_insn and load1 have a def-use dependence upon
1672    the same insn 'insn1'.
1673    (3) either load2 is in bb_trg, or:
1674    - there's only one split-block, and
1675    - load1 is on the escape path, and
1676
1677    From all these we can conclude that the two loads access memory
1678    addresses that differ at most by a constant, and hence if moving
1679    load_insn would cause an exception, it would have been caused by
1680    load2 anyhow.  */
1681
1682 static int
1683 is_pfree (load_insn, bb_src, bb_trg)
1684      rtx load_insn;
1685      int bb_src, bb_trg;
1686 {
1687   rtx back_link;
1688   candidate *candp = candidate_table + bb_src;
1689
1690   if (candp->split_bbs.nr_members != 1)
1691     /* Must have exactly one escape block.  */
1692     return 0;
1693
1694   for (back_link = LOG_LINKS (load_insn);
1695        back_link; back_link = XEXP (back_link, 1))
1696     {
1697       rtx insn1 = XEXP (back_link, 0);
1698
1699       if (GET_MODE (back_link) == VOIDmode)
1700         {
1701           /* Found a DEF-USE dependence (insn1, load_insn).  */
1702           rtx fore_link;
1703
1704           for (fore_link = INSN_DEPEND (insn1);
1705                fore_link; fore_link = XEXP (fore_link, 1))
1706             {
1707               rtx insn2 = XEXP (fore_link, 0);
1708               if (GET_MODE (fore_link) == VOIDmode)
1709                 {
1710                   /* Found a DEF-USE dependence (insn1, insn2).  */
1711                   if (haifa_classify_insn (insn2) != PFREE_CANDIDATE)
1712                     /* insn2 not guaranteed to be a 1 base reg load.  */
1713                     continue;
1714
1715                   if (INSN_BB (insn2) == bb_trg)
1716                     /* insn2 is the similar load, in the target block.  */
1717                     return 1;
1718
1719                   if (*(candp->split_bbs.first_member) == BLOCK_NUM (insn2))
1720                     /* insn2 is a similar load, in a split-block.  */
1721                     return 1;
1722                 }
1723             }
1724         }
1725     }
1726
1727   /* Couldn't find a similar load.  */
1728   return 0;
1729 }                               /* is_pfree */
1730
1731 /* Returns a class that insn with GET_DEST(insn)=x may belong to,
1732    as found by analyzing insn's expression.  */
1733
1734 static int
1735 may_trap_exp (x, is_store)
1736      rtx x;
1737      int is_store;
1738 {
1739   enum rtx_code code;
1740
1741   if (x == 0)
1742     return TRAP_FREE;
1743   code = GET_CODE (x);
1744   if (is_store)
1745     {
1746       if (code == MEM && may_trap_p (x))
1747         return TRAP_RISKY;
1748       else
1749         return TRAP_FREE;
1750     }
1751   if (code == MEM)
1752     {
1753       /* The insn uses memory:  a volatile load.  */
1754       if (MEM_VOLATILE_P (x))
1755         return IRISKY;
1756       /* An exception-free load.  */
1757       if (!may_trap_p (x))
1758         return IFREE;
1759       /* A load with 1 base register, to be further checked.  */
1760       if (CONST_BASED_ADDRESS_P (XEXP (x, 0)))
1761         return PFREE_CANDIDATE;
1762       /* No info on the load, to be further checked.  */
1763       return PRISKY_CANDIDATE;
1764     }
1765   else
1766     {
1767       const char *fmt;
1768       int i, insn_class = TRAP_FREE;
1769
1770       /* Neither store nor load, check if it may cause a trap.  */
1771       if (may_trap_p (x))
1772         return TRAP_RISKY;
1773       /* Recursive step: walk the insn...  */
1774       fmt = GET_RTX_FORMAT (code);
1775       for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1776         {
1777           if (fmt[i] == 'e')
1778             {
1779               int tmp_class = may_trap_exp (XEXP (x, i), is_store);
1780               insn_class = WORST_CLASS (insn_class, tmp_class);
1781             }
1782           else if (fmt[i] == 'E')
1783             {
1784               int j;
1785               for (j = 0; j < XVECLEN (x, i); j++)
1786                 {
1787                   int tmp_class = may_trap_exp (XVECEXP (x, i, j), is_store);
1788                   insn_class = WORST_CLASS (insn_class, tmp_class);
1789                   if (insn_class == TRAP_RISKY || insn_class == IRISKY)
1790                     break;
1791                 }
1792             }
1793           if (insn_class == TRAP_RISKY || insn_class == IRISKY)
1794             break;
1795         }
1796       return insn_class;
1797     }
1798 }
1799
1800 /* Classifies insn for the purpose of verifying that it can be
1801    moved speculatively, by examining it's patterns, returning:
1802    TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
1803    TRAP_FREE: non-load insn.
1804    IFREE: load from a globaly safe location.
1805    IRISKY: volatile load.
1806    PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
1807    being either PFREE or PRISKY.  */
1808
1809 static int
1810 haifa_classify_insn (insn)
1811      rtx insn;
1812 {
1813   rtx pat = PATTERN (insn);
1814   int tmp_class = TRAP_FREE;
1815   int insn_class = TRAP_FREE;
1816   enum rtx_code code;
1817
1818   if (GET_CODE (pat) == PARALLEL)
1819     {
1820       int i, len = XVECLEN (pat, 0);
1821
1822       for (i = len - 1; i >= 0; i--)
1823         {
1824           code = GET_CODE (XVECEXP (pat, 0, i));
1825           switch (code)
1826             {
1827             case CLOBBER:
1828               /* Test if it is a 'store'.  */
1829               tmp_class = may_trap_exp (XEXP (XVECEXP (pat, 0, i), 0), 1);
1830               break;
1831             case SET:
1832               /* Test if it is a store.  */
1833               tmp_class = may_trap_exp (SET_DEST (XVECEXP (pat, 0, i)), 1);
1834               if (tmp_class == TRAP_RISKY)
1835                 break;
1836               /* Test if it is a load.  */
1837               tmp_class
1838                 = WORST_CLASS (tmp_class,
1839                                may_trap_exp (SET_SRC (XVECEXP (pat, 0, i)),
1840                                              0));
1841               break;
1842             case COND_EXEC:
1843             case TRAP_IF:
1844               tmp_class = TRAP_RISKY;
1845               break;
1846             default:
1847               ;
1848             }
1849           insn_class = WORST_CLASS (insn_class, tmp_class);
1850           if (insn_class == TRAP_RISKY || insn_class == IRISKY)
1851             break;
1852         }
1853     }
1854   else
1855     {
1856       code = GET_CODE (pat);
1857       switch (code)
1858         {
1859         case CLOBBER:
1860           /* Test if it is a 'store'.  */
1861           tmp_class = may_trap_exp (XEXP (pat, 0), 1);
1862           break;
1863         case SET:
1864           /* Test if it is a store.  */
1865           tmp_class = may_trap_exp (SET_DEST (pat), 1);
1866           if (tmp_class == TRAP_RISKY)
1867             break;
1868           /* Test if it is a load.  */
1869           tmp_class =
1870             WORST_CLASS (tmp_class,
1871                          may_trap_exp (SET_SRC (pat), 0));
1872           break;
1873         case COND_EXEC:
1874         case TRAP_IF:
1875           tmp_class = TRAP_RISKY;
1876           break;
1877         default:;
1878         }
1879       insn_class = tmp_class;
1880     }
1881
1882   return insn_class;
1883 }
1884
1885 /* Return 1 if load_insn is prisky (i.e. if load_insn is fed by
1886    a load moved speculatively, or if load_insn is protected by
1887    a compare on load_insn's address).  */
1888
1889 static int
1890 is_prisky (load_insn, bb_src, bb_trg)
1891      rtx load_insn;
1892      int bb_src, bb_trg;
1893 {
1894   if (FED_BY_SPEC_LOAD (load_insn))
1895     return 1;
1896
1897   if (LOG_LINKS (load_insn) == NULL)
1898     /* Dependence may 'hide' out of the region.  */
1899     return 1;
1900
1901   if (is_conditionally_protected (load_insn, bb_src, bb_trg))
1902     return 1;
1903
1904   return 0;
1905 }
1906
1907 /* Insn is a candidate to be moved speculatively from bb_src to bb_trg.
1908    Return 1 if insn is exception-free (and the motion is valid)
1909    and 0 otherwise.  */
1910
1911 static int
1912 is_exception_free (insn, bb_src, bb_trg)
1913      rtx insn;
1914      int bb_src, bb_trg;
1915 {
1916   int insn_class = haifa_classify_insn (insn);
1917
1918   /* Handle non-load insns.  */
1919   switch (insn_class)
1920     {
1921     case TRAP_FREE:
1922       return 1;
1923     case TRAP_RISKY:
1924       return 0;
1925     default:;
1926     }
1927
1928   /* Handle loads.  */
1929   if (!flag_schedule_speculative_load)
1930     return 0;
1931   IS_LOAD_INSN (insn) = 1;
1932   switch (insn_class)
1933     {
1934     case IFREE:
1935       return (1);
1936     case IRISKY:
1937       return 0;
1938     case PFREE_CANDIDATE:
1939       if (is_pfree (insn, bb_src, bb_trg))
1940         return 1;
1941       /* Don't 'break' here: PFREE-candidate is also PRISKY-candidate.  */
1942     case PRISKY_CANDIDATE:
1943       if (!flag_schedule_speculative_load_dangerous
1944           || is_prisky (insn, bb_src, bb_trg))
1945         return 0;
1946       break;
1947     default:;
1948     }
1949
1950   return flag_schedule_speculative_load_dangerous;
1951 }
1952 \f
1953 /* The number of insns from the current block scheduled so far.  */
1954 static int sched_target_n_insns;
1955 /* The number of insns from the current block to be scheduled in total.  */
1956 static int target_n_insns;
1957 /* The number of insns from the entire region scheduled so far.  */
1958 static int sched_n_insns;
1959 /* Nonzero if the last scheduled insn was a jump.  */
1960 static int last_was_jump;
1961
1962 /* Implementations of the sched_info functions for region scheduling.  */
1963 static void init_ready_list PARAMS ((struct ready_list *));
1964 static int can_schedule_ready_p PARAMS ((rtx));
1965 static int new_ready PARAMS ((rtx));
1966 static int schedule_more_p PARAMS ((void));
1967 static const char *rgn_print_insn PARAMS ((rtx, int));
1968 static int rgn_rank PARAMS ((rtx, rtx));
1969 static int contributes_to_priority PARAMS ((rtx, rtx));
1970 static void compute_jump_reg_dependencies PARAMS ((rtx, regset));
1971
1972 /* Return nonzero if there are more insns that should be scheduled.  */
1973
1974 static int
1975 schedule_more_p ()
1976 {
1977   return ! last_was_jump && sched_target_n_insns < target_n_insns;
1978 }
1979
1980 /* Add all insns that are initially ready to the ready list READY.  Called
1981    once before scheduling a set of insns.  */
1982
1983 static void
1984 init_ready_list (ready)
1985      struct ready_list *ready;
1986 {
1987   rtx prev_head = current_sched_info->prev_head;
1988   rtx next_tail = current_sched_info->next_tail;
1989   int bb_src;
1990   rtx insn;
1991
1992   target_n_insns = 0;
1993   sched_target_n_insns = 0;
1994   sched_n_insns = 0;
1995   last_was_jump = 0;
1996
1997   /* Print debugging information.  */
1998   if (sched_verbose >= 5)
1999     debug_dependencies ();
2000
2001   /* Prepare current target block info.  */
2002   if (current_nr_blocks > 1)
2003     {
2004       candidate_table = (candidate *) xmalloc (current_nr_blocks
2005                                                * sizeof (candidate));
2006
2007       bblst_last = 0;
2008       /* bblst_table holds split blocks and update blocks for each block after
2009          the current one in the region.  split blocks and update blocks are
2010          the TO blocks of region edges, so there can be at most rgn_nr_edges
2011          of them.  */
2012       bblst_size = (current_nr_blocks - target_bb) * rgn_nr_edges;
2013       bblst_table = (int *) xmalloc (bblst_size * sizeof (int));
2014
2015       bitlst_table_last = 0;
2016       bitlst_table_size = rgn_nr_edges;
2017       bitlst_table = (int *) xmalloc (rgn_nr_edges * sizeof (int));
2018
2019       compute_trg_info (target_bb);
2020     }
2021
2022   /* Initialize ready list with all 'ready' insns in target block.
2023      Count number of insns in the target block being scheduled.  */
2024   for (insn = NEXT_INSN (prev_head); insn != next_tail; insn = NEXT_INSN (insn))
2025     {
2026       rtx next;
2027
2028       if (! INSN_P (insn))
2029         continue;
2030       next = NEXT_INSN (insn);
2031
2032       if (INSN_DEP_COUNT (insn) == 0
2033           && (! INSN_P (next) || SCHED_GROUP_P (next) == 0))
2034         ready_add (ready, insn);
2035       if (!(SCHED_GROUP_P (insn)))
2036         target_n_insns++;
2037     }
2038
2039   /* Add to ready list all 'ready' insns in valid source blocks.
2040      For speculative insns, check-live, exception-free, and
2041      issue-delay.  */
2042   for (bb_src = target_bb + 1; bb_src < current_nr_blocks; bb_src++)
2043     if (IS_VALID (bb_src))
2044       {
2045         rtx src_head;
2046         rtx src_next_tail;
2047         rtx tail, head;
2048
2049         get_block_head_tail (BB_TO_BLOCK (bb_src), &head, &tail);
2050         src_next_tail = NEXT_INSN (tail);
2051         src_head = head;
2052
2053         for (insn = src_head; insn != src_next_tail; insn = NEXT_INSN (insn))
2054           {
2055             if (! INSN_P (insn))
2056               continue;
2057
2058             if (!CANT_MOVE (insn)
2059                 && (!IS_SPECULATIVE_INSN (insn)
2060                     || ((((!targetm.sched.use_dfa_pipeline_interface
2061                            || !(*targetm.sched.use_dfa_pipeline_interface) ())
2062                           && insn_issue_delay (insn) <= 3)
2063                          || (targetm.sched.use_dfa_pipeline_interface
2064                              && (*targetm.sched.use_dfa_pipeline_interface) ()
2065                              && (recog_memoized (insn) < 0
2066                                  || min_insn_conflict_delay (curr_state,
2067                                                              insn, insn) <= 3)))
2068                         && check_live (insn, bb_src)
2069                         && is_exception_free (insn, bb_src, target_bb))))
2070               {
2071                 rtx next;
2072
2073                 /* Note that we haven't squirreled away the notes for
2074                    blocks other than the current.  So if this is a
2075                    speculative insn, NEXT might otherwise be a note.  */
2076                 next = next_nonnote_insn (insn);
2077                 if (INSN_DEP_COUNT (insn) == 0
2078                     && (! next
2079                         || ! INSN_P (next)
2080                         || SCHED_GROUP_P (next) == 0))
2081                   ready_add (ready, insn);
2082               }
2083           }
2084       }
2085 }
2086
2087 /* Called after taking INSN from the ready list.  Returns nonzero if this
2088    insn can be scheduled, nonzero if we should silently discard it.  */
2089
2090 static int
2091 can_schedule_ready_p (insn)
2092      rtx insn;
2093 {
2094   if (GET_CODE (insn) == JUMP_INSN)
2095     last_was_jump = 1;
2096
2097   /* An interblock motion?  */
2098   if (INSN_BB (insn) != target_bb)
2099     {
2100       rtx temp;
2101       basic_block b1;
2102
2103       if (IS_SPECULATIVE_INSN (insn))
2104         {
2105           if (!check_live (insn, INSN_BB (insn)))
2106             return 0;
2107           update_live (insn, INSN_BB (insn));
2108
2109           /* For speculative load, mark insns fed by it.  */
2110           if (IS_LOAD_INSN (insn) || FED_BY_SPEC_LOAD (insn))
2111             set_spec_fed (insn);
2112
2113           nr_spec++;
2114         }
2115       nr_inter++;
2116
2117       /* Find the beginning of the scheduling group.  */
2118       /* ??? Ought to update basic block here, but later bits of
2119          schedule_block assumes the original insn block is
2120          still intact.  */
2121
2122       temp = insn;
2123       while (SCHED_GROUP_P (temp))
2124         temp = PREV_INSN (temp);
2125
2126       /* Update source block boundaries.  */
2127       b1 = BLOCK_FOR_INSN (temp);
2128       if (temp == b1->head && insn == b1->end)
2129         {
2130           /* We moved all the insns in the basic block.
2131              Emit a note after the last insn and update the
2132              begin/end boundaries to point to the note.  */
2133           rtx note = emit_note_after (NOTE_INSN_DELETED, insn);
2134           b1->head = note;
2135           b1->end = note;
2136         }
2137       else if (insn == b1->end)
2138         {
2139           /* We took insns from the end of the basic block,
2140              so update the end of block boundary so that it
2141              points to the first insn we did not move.  */
2142           b1->end = PREV_INSN (temp);
2143         }
2144       else if (temp == b1->head)
2145         {
2146           /* We took insns from the start of the basic block,
2147              so update the start of block boundary so that
2148              it points to the first insn we did not move.  */
2149           b1->head = NEXT_INSN (insn);
2150         }
2151     }
2152   else
2153     {
2154       /* In block motion.  */
2155       sched_target_n_insns++;
2156     }
2157   sched_n_insns++;
2158
2159   return 1;
2160 }
2161
2162 /* Called after INSN has all its dependencies resolved.  Return nonzero
2163    if it should be moved to the ready list or the queue, or zero if we
2164    should silently discard it.  */
2165 static int
2166 new_ready (next)
2167      rtx next;
2168 {
2169   /* For speculative insns, before inserting to ready/queue,
2170      check live, exception-free, and issue-delay.  */
2171   if (INSN_BB (next) != target_bb
2172       && (!IS_VALID (INSN_BB (next))
2173           || CANT_MOVE (next)
2174           || (IS_SPECULATIVE_INSN (next)
2175               && (0
2176                   || (targetm.sched.use_dfa_pipeline_interface
2177                       && (*targetm.sched.use_dfa_pipeline_interface) ()
2178                       && recog_memoized (next) >= 0
2179                       && min_insn_conflict_delay (curr_state, next,
2180                                                   next) > 3)
2181                   || ((!targetm.sched.use_dfa_pipeline_interface
2182                        || !(*targetm.sched.use_dfa_pipeline_interface) ())
2183                       && insn_issue_delay (next) > 3)
2184                   || !check_live (next, INSN_BB (next))
2185                   || !is_exception_free (next, INSN_BB (next), target_bb)))))
2186     return 0;
2187   return 1;
2188 }
2189
2190 /* Return a string that contains the insn uid and optionally anything else
2191    necessary to identify this insn in an output.  It's valid to use a
2192    static buffer for this.  The ALIGNED parameter should cause the string
2193    to be formatted so that multiple output lines will line up nicely.  */
2194
2195 static const char *
2196 rgn_print_insn (insn, aligned)
2197      rtx insn;
2198      int aligned;
2199 {
2200   static char tmp[80];
2201
2202   if (aligned)
2203     sprintf (tmp, "b%3d: i%4d", INSN_BB (insn), INSN_UID (insn));
2204   else
2205     {
2206       if (current_nr_blocks > 1 && INSN_BB (insn) != target_bb)
2207         sprintf (tmp, "%d/b%d", INSN_UID (insn), INSN_BB (insn));
2208       else
2209         sprintf (tmp, "%d", INSN_UID (insn));
2210     }
2211   return tmp;
2212 }
2213
2214 /* Compare priority of two insns.  Return a positive number if the second
2215    insn is to be preferred for scheduling, and a negative one if the first
2216    is to be preferred.  Zero if they are equally good.  */
2217
2218 static int
2219 rgn_rank (insn1, insn2)
2220      rtx insn1, insn2;
2221 {
2222   /* Some comparison make sense in interblock scheduling only.  */
2223   if (INSN_BB (insn1) != INSN_BB (insn2))
2224     {
2225       int spec_val, prob_val;
2226
2227       /* Prefer an inblock motion on an interblock motion.  */
2228       if ((INSN_BB (insn2) == target_bb) && (INSN_BB (insn1) != target_bb))
2229         return 1;
2230       if ((INSN_BB (insn1) == target_bb) && (INSN_BB (insn2) != target_bb))
2231         return -1;
2232
2233       /* Prefer a useful motion on a speculative one.  */
2234       spec_val = IS_SPECULATIVE_INSN (insn1) - IS_SPECULATIVE_INSN (insn2);
2235       if (spec_val)
2236         return spec_val;
2237
2238       /* Prefer a more probable (speculative) insn.  */
2239       prob_val = INSN_PROBABILITY (insn2) - INSN_PROBABILITY (insn1);
2240       if (prob_val)
2241         return prob_val;
2242     }
2243   return 0;
2244 }
2245
2246 /* NEXT is an instruction that depends on INSN (a backward dependence);
2247    return nonzero if we should include this dependence in priority
2248    calculations.  */
2249
2250 static int
2251 contributes_to_priority (next, insn)
2252      rtx next, insn;
2253 {
2254   return BLOCK_NUM (next) == BLOCK_NUM (insn);
2255 }
2256
2257 /* INSN is a JUMP_INSN.  Store the set of registers that must be considered
2258    to be set by this jump in SET.  */
2259
2260 static void
2261 compute_jump_reg_dependencies (insn, set)
2262      rtx insn ATTRIBUTE_UNUSED;
2263      regset set ATTRIBUTE_UNUSED;
2264 {
2265   /* Nothing to do here, since we postprocess jumps in
2266      add_branch_dependences.  */
2267 }
2268
2269 /* Used in schedule_insns to initialize current_sched_info for scheduling
2270    regions (or single basic blocks).  */
2271
2272 static struct sched_info region_sched_info =
2273 {
2274   init_ready_list,
2275   can_schedule_ready_p,
2276   schedule_more_p,
2277   new_ready,
2278   rgn_rank,
2279   rgn_print_insn,
2280   contributes_to_priority,
2281   compute_jump_reg_dependencies,
2282
2283   NULL, NULL,
2284   NULL, NULL,
2285   0, 0
2286 };
2287
2288 /* Determine if PAT sets a CLASS_LIKELY_SPILLED_P register.  */
2289
2290 static bool
2291 sets_likely_spilled (pat)
2292      rtx pat;
2293 {
2294   bool ret = false;
2295   note_stores (pat, sets_likely_spilled_1, &ret);
2296   return ret;
2297 }
2298
2299 static void
2300 sets_likely_spilled_1 (x, pat, data)
2301      rtx x, pat;
2302      void *data;
2303 {
2304   bool *ret = (bool *) data;
2305
2306   if (GET_CODE (pat) == SET
2307       && REG_P (x)
2308       && REGNO (x) < FIRST_PSEUDO_REGISTER
2309       && CLASS_LIKELY_SPILLED_P (REGNO_REG_CLASS (REGNO (x))))
2310     *ret = true;
2311 }
2312
2313 /* Add dependences so that branches are scheduled to run last in their
2314    block.  */
2315
2316 static void
2317 add_branch_dependences (head, tail)
2318      rtx head, tail;
2319 {
2320   rtx insn, last;
2321
2322   /* For all branches, calls, uses, clobbers, cc0 setters, and instructions
2323      that can throw exceptions, force them to remain in order at the end of
2324      the block by adding dependencies and giving the last a high priority.
2325      There may be notes present, and prev_head may also be a note.
2326
2327      Branches must obviously remain at the end.  Calls should remain at the
2328      end since moving them results in worse register allocation.  Uses remain
2329      at the end to ensure proper register allocation.
2330
2331      cc0 setters remaim at the end because they can't be moved away from
2332      their cc0 user.
2333
2334      Insns setting CLASS_LIKELY_SPILLED_P registers (usually return values)
2335      are not moved before reload because we can wind up with register
2336      allocation failures.  */
2337
2338   insn = tail;
2339   last = 0;
2340   while (GET_CODE (insn) == CALL_INSN
2341          || GET_CODE (insn) == JUMP_INSN
2342          || (GET_CODE (insn) == INSN
2343              && (GET_CODE (PATTERN (insn)) == USE
2344                  || GET_CODE (PATTERN (insn)) == CLOBBER
2345                  || can_throw_internal (insn)
2346 #ifdef HAVE_cc0
2347                  || sets_cc0_p (PATTERN (insn))
2348 #endif
2349                  || (!reload_completed
2350                      && sets_likely_spilled (PATTERN (insn)))))
2351          || GET_CODE (insn) == NOTE)
2352     {
2353       if (GET_CODE (insn) != NOTE)
2354         {
2355           if (last != 0 && !find_insn_list (insn, LOG_LINKS (last)))
2356             {
2357               add_dependence (last, insn, REG_DEP_ANTI);
2358               INSN_REF_COUNT (insn)++;
2359             }
2360
2361           CANT_MOVE (insn) = 1;
2362
2363           last = insn;
2364           /* Skip over insns that are part of a group.
2365              Make each insn explicitly depend on the previous insn.
2366              This ensures that only the group header will ever enter
2367              the ready queue (and, when scheduled, will automatically
2368              schedule the SCHED_GROUP_P block).  */
2369           while (SCHED_GROUP_P (insn))
2370             {
2371               rtx temp = prev_nonnote_insn (insn);
2372               add_dependence (insn, temp, REG_DEP_ANTI);
2373               insn = temp;
2374             }
2375         }
2376
2377       /* Don't overrun the bounds of the basic block.  */
2378       if (insn == head)
2379         break;
2380
2381       insn = PREV_INSN (insn);
2382     }
2383
2384   /* Make sure these insns are scheduled last in their block.  */
2385   insn = last;
2386   if (insn != 0)
2387     while (insn != head)
2388       {
2389         insn = prev_nonnote_insn (insn);
2390
2391         if (INSN_REF_COUNT (insn) != 0)
2392           continue;
2393
2394         add_dependence (last, insn, REG_DEP_ANTI);
2395         INSN_REF_COUNT (insn) = 1;
2396
2397         /* Skip over insns that are part of a group.  */
2398         while (SCHED_GROUP_P (insn))
2399           insn = prev_nonnote_insn (insn);
2400       }
2401 }
2402
2403 /* Data structures for the computation of data dependences in a regions.  We
2404    keep one `deps' structure for every basic block.  Before analyzing the
2405    data dependences for a bb, its variables are initialized as a function of
2406    the variables of its predecessors.  When the analysis for a bb completes,
2407    we save the contents to the corresponding bb_deps[bb] variable.  */
2408
2409 static struct deps *bb_deps;
2410
2411 /* Duplicate the INSN_LIST elements of COPY and prepend them to OLD.  */
2412
2413 static rtx
2414 concat_INSN_LIST (copy, old)
2415      rtx copy, old;
2416 {
2417   rtx new = old;
2418   for (; copy ; copy = XEXP (copy, 1))
2419     new = alloc_INSN_LIST (XEXP (copy, 0), new);
2420   return new;
2421 }
2422
2423 static void
2424 concat_insn_mem_list (copy_insns, copy_mems, old_insns_p, old_mems_p)
2425      rtx copy_insns, copy_mems;
2426      rtx *old_insns_p, *old_mems_p;
2427 {
2428   rtx new_insns = *old_insns_p;
2429   rtx new_mems = *old_mems_p;
2430
2431   while (copy_insns)
2432     {
2433       new_insns = alloc_INSN_LIST (XEXP (copy_insns, 0), new_insns);
2434       new_mems = alloc_EXPR_LIST (VOIDmode, XEXP (copy_mems, 0), new_mems);
2435       copy_insns = XEXP (copy_insns, 1);
2436       copy_mems = XEXP (copy_mems, 1);
2437     }
2438
2439   *old_insns_p = new_insns;
2440   *old_mems_p = new_mems;
2441 }
2442
2443 /* After computing the dependencies for block BB, propagate the dependencies
2444    found in TMP_DEPS to the successors of the block.  */
2445 static void
2446 propagate_deps (bb, pred_deps)
2447      int bb;
2448      struct deps *pred_deps;
2449 {
2450   int b = BB_TO_BLOCK (bb);
2451   int e, first_edge;
2452
2453   /* bb's structures are inherited by its successors.  */
2454   first_edge = e = OUT_EDGES (b);
2455   if (e > 0)
2456     do
2457       {
2458         int b_succ = TO_BLOCK (e);
2459         int bb_succ = BLOCK_TO_BB (b_succ);
2460         struct deps *succ_deps = bb_deps + bb_succ;
2461         int reg;
2462
2463         /* Only bbs "below" bb, in the same region, are interesting.  */
2464         if (CONTAINING_RGN (b) != CONTAINING_RGN (b_succ)
2465             || bb_succ <= bb)
2466           {
2467             e = NEXT_OUT (e);
2468             continue;
2469           }
2470
2471         /* The reg_last lists are inherited by bb_succ.  */
2472         EXECUTE_IF_SET_IN_REG_SET (&pred_deps->reg_last_in_use, 0, reg,
2473           {
2474             struct deps_reg *pred_rl = &pred_deps->reg_last[reg];
2475             struct deps_reg *succ_rl = &succ_deps->reg_last[reg];
2476
2477             succ_rl->uses = concat_INSN_LIST (pred_rl->uses, succ_rl->uses);
2478             succ_rl->sets = concat_INSN_LIST (pred_rl->sets, succ_rl->sets);
2479             succ_rl->clobbers = concat_INSN_LIST (pred_rl->clobbers,
2480                                                   succ_rl->clobbers);
2481             succ_rl->uses_length += pred_rl->uses_length;
2482             succ_rl->clobbers_length += pred_rl->clobbers_length;
2483           });
2484         IOR_REG_SET (&succ_deps->reg_last_in_use, &pred_deps->reg_last_in_use);
2485
2486         /* Mem read/write lists are inherited by bb_succ.  */
2487         concat_insn_mem_list (pred_deps->pending_read_insns,
2488                               pred_deps->pending_read_mems,
2489                               &succ_deps->pending_read_insns,
2490                               &succ_deps->pending_read_mems);
2491         concat_insn_mem_list (pred_deps->pending_write_insns,
2492                               pred_deps->pending_write_mems,
2493                               &succ_deps->pending_write_insns,
2494                               &succ_deps->pending_write_mems);
2495
2496         succ_deps->last_pending_memory_flush
2497           = concat_INSN_LIST (pred_deps->last_pending_memory_flush,
2498                               succ_deps->last_pending_memory_flush);
2499
2500         succ_deps->pending_lists_length += pred_deps->pending_lists_length;
2501         succ_deps->pending_flush_length += pred_deps->pending_flush_length;
2502
2503         /* last_function_call is inherited by bb_succ.  */
2504         succ_deps->last_function_call
2505           = concat_INSN_LIST (pred_deps->last_function_call,
2506                               succ_deps->last_function_call);
2507
2508         /* sched_before_next_call is inherited by bb_succ.  */
2509         succ_deps->sched_before_next_call
2510           = concat_INSN_LIST (pred_deps->sched_before_next_call,
2511                               succ_deps->sched_before_next_call);
2512
2513         e = NEXT_OUT (e);
2514       }
2515     while (e != first_edge);
2516
2517   /* These lists should point to the right place, for correct
2518      freeing later.  */
2519   bb_deps[bb].pending_read_insns = pred_deps->pending_read_insns;
2520   bb_deps[bb].pending_read_mems = pred_deps->pending_read_mems;
2521   bb_deps[bb].pending_write_insns = pred_deps->pending_write_insns;
2522   bb_deps[bb].pending_write_mems = pred_deps->pending_write_mems;
2523
2524   /* Can't allow these to be freed twice.  */
2525   pred_deps->pending_read_insns = 0;
2526   pred_deps->pending_read_mems = 0;
2527   pred_deps->pending_write_insns = 0;
2528   pred_deps->pending_write_mems = 0;
2529 }
2530
2531 /* Compute backward dependences inside bb.  In a multiple blocks region:
2532    (1) a bb is analyzed after its predecessors, and (2) the lists in
2533    effect at the end of bb (after analyzing for bb) are inherited by
2534    bb's successrs.
2535
2536    Specifically for reg-reg data dependences, the block insns are
2537    scanned by sched_analyze () top-to-bottom.  Two lists are
2538    maintained by sched_analyze (): reg_last[].sets for register DEFs,
2539    and reg_last[].uses for register USEs.
2540
2541    When analysis is completed for bb, we update for its successors:
2542    ;  - DEFS[succ] = Union (DEFS [succ], DEFS [bb])
2543    ;  - USES[succ] = Union (USES [succ], DEFS [bb])
2544
2545    The mechanism for computing mem-mem data dependence is very
2546    similar, and the result is interblock dependences in the region.  */
2547
2548 static void
2549 compute_block_backward_dependences (bb)
2550      int bb;
2551 {
2552   rtx head, tail;
2553   struct deps tmp_deps;
2554
2555   tmp_deps = bb_deps[bb];
2556
2557   /* Do the analysis for this block.  */
2558   get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail);
2559   sched_analyze (&tmp_deps, head, tail);
2560   add_branch_dependences (head, tail);
2561
2562   if (current_nr_blocks > 1)
2563     propagate_deps (bb, &tmp_deps);
2564
2565   /* Free up the INSN_LISTs.  */
2566   free_deps (&tmp_deps);
2567 }
2568
2569 /* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
2570    them to the unused_*_list variables, so that they can be reused.  */
2571
2572 static void
2573 free_pending_lists ()
2574 {
2575   int bb;
2576
2577   for (bb = 0; bb < current_nr_blocks; bb++)
2578     {
2579       free_INSN_LIST_list (&bb_deps[bb].pending_read_insns);
2580       free_INSN_LIST_list (&bb_deps[bb].pending_write_insns);
2581       free_EXPR_LIST_list (&bb_deps[bb].pending_read_mems);
2582       free_EXPR_LIST_list (&bb_deps[bb].pending_write_mems);
2583     }
2584 }
2585 \f
2586 /* Print dependences for debugging, callable from debugger.  */
2587
2588 void
2589 debug_dependencies ()
2590 {
2591   int bb;
2592
2593   fprintf (sched_dump, ";;   --------------- forward dependences: ------------ \n");
2594   for (bb = 0; bb < current_nr_blocks; bb++)
2595     {
2596       if (1)
2597         {
2598           rtx head, tail;
2599           rtx next_tail;
2600           rtx insn;
2601
2602           get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail);
2603           next_tail = NEXT_INSN (tail);
2604           fprintf (sched_dump, "\n;;   --- Region Dependences --- b %d bb %d \n",
2605                    BB_TO_BLOCK (bb), bb);
2606
2607           if (targetm.sched.use_dfa_pipeline_interface
2608               && (*targetm.sched.use_dfa_pipeline_interface) ())
2609             {
2610               fprintf (sched_dump, ";;   %7s%6s%6s%6s%6s%6s%14s\n",
2611                        "insn", "code", "bb", "dep", "prio", "cost",
2612                        "reservation");
2613               fprintf (sched_dump, ";;   %7s%6s%6s%6s%6s%6s%14s\n",
2614                        "----", "----", "--", "---", "----", "----",
2615                        "-----------");
2616             }
2617           else
2618             {
2619               fprintf (sched_dump, ";;   %7s%6s%6s%6s%6s%6s%11s%6s\n",
2620               "insn", "code", "bb", "dep", "prio", "cost", "blockage", "units");
2621               fprintf (sched_dump, ";;   %7s%6s%6s%6s%6s%6s%11s%6s\n",
2622               "----", "----", "--", "---", "----", "----", "--------", "-----");
2623             }
2624
2625           for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
2626             {
2627               rtx link;
2628
2629               if (! INSN_P (insn))
2630                 {
2631                   int n;
2632                   fprintf (sched_dump, ";;   %6d ", INSN_UID (insn));
2633                   if (GET_CODE (insn) == NOTE)
2634                     {
2635                       n = NOTE_LINE_NUMBER (insn);
2636                       if (n < 0)
2637                         fprintf (sched_dump, "%s\n", GET_NOTE_INSN_NAME (n));
2638                       else
2639                         fprintf (sched_dump, "line %d, file %s\n", n,
2640                                  NOTE_SOURCE_FILE (insn));
2641                     }
2642                   else
2643                     fprintf (sched_dump, " {%s}\n", GET_RTX_NAME (GET_CODE (insn)));
2644                   continue;
2645                 }
2646
2647               if (targetm.sched.use_dfa_pipeline_interface
2648                   && (*targetm.sched.use_dfa_pipeline_interface) ())
2649                 {
2650                   fprintf (sched_dump,
2651                            ";;   %s%5d%6d%6d%6d%6d%6d   ",
2652                            (SCHED_GROUP_P (insn) ? "+" : " "),
2653                            INSN_UID (insn),
2654                            INSN_CODE (insn),
2655                            INSN_BB (insn),
2656                            INSN_DEP_COUNT (insn),
2657                            INSN_PRIORITY (insn),
2658                            insn_cost (insn, 0, 0));
2659
2660                   if (recog_memoized (insn) < 0)
2661                     fprintf (sched_dump, "nothing");
2662                   else
2663                     print_reservation (sched_dump, insn);
2664                 }
2665               else
2666                 {
2667                   int unit = insn_unit (insn);
2668                   int range
2669                     = (unit < 0
2670                        || function_units[unit].blockage_range_function == 0
2671                        ? 0
2672                        : function_units[unit].blockage_range_function (insn));
2673                   fprintf (sched_dump,
2674                            ";;   %s%5d%6d%6d%6d%6d%6d  %3d -%3d   ",
2675                            (SCHED_GROUP_P (insn) ? "+" : " "),
2676                            INSN_UID (insn),
2677                            INSN_CODE (insn),
2678                            INSN_BB (insn),
2679                            INSN_DEP_COUNT (insn),
2680                            INSN_PRIORITY (insn),
2681                            insn_cost (insn, 0, 0),
2682                            (int) MIN_BLOCKAGE_COST (range),
2683                            (int) MAX_BLOCKAGE_COST (range));
2684                   insn_print_units (insn);
2685                 }
2686
2687               fprintf (sched_dump, "\t: ");
2688               for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
2689                 fprintf (sched_dump, "%d ", INSN_UID (XEXP (link, 0)));
2690               fprintf (sched_dump, "\n");
2691             }
2692         }
2693     }
2694   fprintf (sched_dump, "\n");
2695 }
2696 \f
2697 /* Schedule a region.  A region is either an inner loop, a loop-free
2698    subroutine, or a single basic block.  Each bb in the region is
2699    scheduled after its flow predecessors.  */
2700
2701 static void
2702 schedule_region (rgn)
2703      int rgn;
2704 {
2705   int bb;
2706   int rgn_n_insns = 0;
2707   int sched_rgn_n_insns = 0;
2708
2709   /* Set variables for the current region.  */
2710   current_nr_blocks = RGN_NR_BLOCKS (rgn);
2711   current_blocks = RGN_BLOCKS (rgn);
2712
2713   init_deps_global ();
2714
2715   /* Initializations for region data dependence analyisis.  */
2716   bb_deps = (struct deps *) xmalloc (sizeof (struct deps) * current_nr_blocks);
2717   for (bb = 0; bb < current_nr_blocks; bb++)
2718     init_deps (bb_deps + bb);
2719
2720   /* Compute LOG_LINKS.  */
2721   for (bb = 0; bb < current_nr_blocks; bb++)
2722     compute_block_backward_dependences (bb);
2723
2724   /* Compute INSN_DEPEND.  */
2725   for (bb = current_nr_blocks - 1; bb >= 0; bb--)
2726     {
2727       rtx head, tail;
2728       get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail);
2729
2730       compute_forward_dependences (head, tail);
2731     }
2732
2733   /* Set priorities.  */
2734   for (bb = 0; bb < current_nr_blocks; bb++)
2735     {
2736       rtx head, tail;
2737       get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail);
2738
2739       rgn_n_insns += set_priorities (head, tail);
2740     }
2741
2742   /* Compute interblock info: probabilities, split-edges, dominators, etc.  */
2743   if (current_nr_blocks > 1)
2744     {
2745       int i;
2746
2747       prob = (float *) xmalloc ((current_nr_blocks) * sizeof (float));
2748
2749       dom = sbitmap_vector_alloc (current_nr_blocks, current_nr_blocks);
2750       sbitmap_vector_zero (dom, current_nr_blocks);
2751       /* Edge to bit.  */
2752       rgn_nr_edges = 0;
2753       edge_to_bit = (int *) xmalloc (nr_edges * sizeof (int));
2754       for (i = 1; i < nr_edges; i++)
2755         if (CONTAINING_RGN (FROM_BLOCK (i)) == rgn)
2756           EDGE_TO_BIT (i) = rgn_nr_edges++;
2757       rgn_edges = (int *) xmalloc (rgn_nr_edges * sizeof (int));
2758
2759       rgn_nr_edges = 0;
2760       for (i = 1; i < nr_edges; i++)
2761         if (CONTAINING_RGN (FROM_BLOCK (i)) == (rgn))
2762           rgn_edges[rgn_nr_edges++] = i;
2763
2764       /* Split edges.  */
2765       pot_split = sbitmap_vector_alloc (current_nr_blocks, rgn_nr_edges);
2766       sbitmap_vector_zero (pot_split, current_nr_blocks);
2767       ancestor_edges = sbitmap_vector_alloc (current_nr_blocks, rgn_nr_edges);
2768       sbitmap_vector_zero (ancestor_edges, current_nr_blocks);
2769
2770       /* Compute probabilities, dominators, split_edges.  */
2771       for (bb = 0; bb < current_nr_blocks; bb++)
2772         compute_dom_prob_ps (bb);
2773     }
2774
2775   /* Now we can schedule all blocks.  */
2776   for (bb = 0; bb < current_nr_blocks; bb++)
2777     {
2778       rtx head, tail;
2779       int b = BB_TO_BLOCK (bb);
2780
2781       get_block_head_tail (b, &head, &tail);
2782
2783       if (no_real_insns_p (head, tail))
2784         continue;
2785
2786       current_sched_info->prev_head = PREV_INSN (head);
2787       current_sched_info->next_tail = NEXT_INSN (tail);
2788
2789       if (write_symbols != NO_DEBUG)
2790         {
2791           save_line_notes (b, head, tail);
2792           rm_line_notes (head, tail);
2793         }
2794
2795       /* rm_other_notes only removes notes which are _inside_ the
2796          block---that is, it won't remove notes before the first real insn
2797          or after the last real insn of the block.  So if the first insn
2798          has a REG_SAVE_NOTE which would otherwise be emitted before the
2799          insn, it is redundant with the note before the start of the
2800          block, and so we have to take it out.  */
2801       if (INSN_P (head))
2802         {
2803           rtx note;
2804
2805           for (note = REG_NOTES (head); note; note = XEXP (note, 1))
2806             if (REG_NOTE_KIND (note) == REG_SAVE_NOTE)
2807               {
2808                 remove_note (head, note);
2809                 note = XEXP (note, 1);
2810                 remove_note (head, note);
2811               }
2812         }
2813
2814       /* Remove remaining note insns from the block, save them in
2815          note_list.  These notes are restored at the end of
2816          schedule_block ().  */
2817       rm_other_notes (head, tail);
2818
2819       target_bb = bb;
2820
2821       current_sched_info->queue_must_finish_empty
2822         = current_nr_blocks > 1 && !flag_schedule_interblock;
2823
2824       schedule_block (b, rgn_n_insns);
2825       sched_rgn_n_insns += sched_n_insns;
2826
2827       /* Update target block boundaries.  */
2828       if (head == BLOCK_HEAD (b))
2829         BLOCK_HEAD (b) = current_sched_info->head;
2830       if (tail == BLOCK_END (b))
2831         BLOCK_END (b) = current_sched_info->tail;
2832
2833       /* Clean up.  */
2834       if (current_nr_blocks > 1)
2835         {
2836           free (candidate_table);
2837           free (bblst_table);
2838           free (bitlst_table);
2839         }
2840     }
2841
2842   /* Sanity check: verify that all region insns were scheduled.  */
2843   if (sched_rgn_n_insns != rgn_n_insns)
2844     abort ();
2845
2846   /* Restore line notes.  */
2847   if (write_symbols != NO_DEBUG)
2848     {
2849       for (bb = 0; bb < current_nr_blocks; bb++)
2850         {
2851           rtx head, tail;
2852           get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail);
2853           restore_line_notes (head, tail);
2854         }
2855     }
2856
2857   /* Done with this region.  */
2858   free_pending_lists ();
2859
2860   finish_deps_global ();
2861
2862   free (bb_deps);
2863
2864   if (current_nr_blocks > 1)
2865     {
2866       free (prob);
2867       sbitmap_vector_free (dom);
2868       sbitmap_vector_free (pot_split);
2869       sbitmap_vector_free (ancestor_edges);
2870       free (edge_to_bit);
2871       free (rgn_edges);
2872     }
2873 }
2874
2875 /* Indexed by region, holds the number of death notes found in that region.
2876    Used for consistency checks.  */
2877 static int *deaths_in_region;
2878
2879 /* Initialize data structures for region scheduling.  */
2880
2881 static void
2882 init_regions ()
2883 {
2884   sbitmap blocks;
2885   int rgn;
2886
2887   nr_regions = 0;
2888   rgn_table = (region *) xmalloc ((n_basic_blocks) * sizeof (region));
2889   rgn_bb_table = (int *) xmalloc ((n_basic_blocks) * sizeof (int));
2890   block_to_bb = (int *) xmalloc ((last_basic_block) * sizeof (int));
2891   containing_rgn = (int *) xmalloc ((last_basic_block) * sizeof (int));
2892
2893   /* Compute regions for scheduling.  */
2894   if (reload_completed
2895       || n_basic_blocks == 1
2896       || !flag_schedule_interblock)
2897     {
2898       find_single_block_region ();
2899     }
2900   else
2901     {
2902       /* Verify that a 'good' control flow graph can be built.  */
2903       if (is_cfg_nonregular ())
2904         {
2905           find_single_block_region ();
2906         }
2907       else
2908         {
2909           dominance_info dom;
2910           struct edge_list *edge_list;
2911
2912           /* The scheduler runs after flow; therefore, we can't blindly call
2913              back into find_basic_blocks since doing so could invalidate the
2914              info in global_live_at_start.
2915
2916              Consider a block consisting entirely of dead stores; after life
2917              analysis it would be a block of NOTE_INSN_DELETED notes.  If
2918              we call find_basic_blocks again, then the block would be removed
2919              entirely and invalidate our the register live information.
2920
2921              We could (should?) recompute register live information.  Doing
2922              so may even be beneficial.  */
2923           edge_list = create_edge_list ();
2924
2925           /* Compute the dominators and post dominators.  */
2926           dom = calculate_dominance_info (CDI_DOMINATORS);
2927
2928           /* build_control_flow will return nonzero if it detects unreachable
2929              blocks or any other irregularity with the cfg which prevents
2930              cross block scheduling.  */
2931           if (build_control_flow (edge_list) != 0)
2932             find_single_block_region ();
2933           else
2934             find_rgns (edge_list, dom);
2935
2936           if (sched_verbose >= 3)
2937             debug_regions ();
2938
2939           /* We are done with flow's edge list.  */
2940           free_edge_list (edge_list);
2941
2942           /* For now.  This will move as more and more of haifa is converted
2943              to using the cfg code in flow.c.  */
2944           free_dominance_info (dom);
2945         }
2946     }
2947
2948
2949   if (CHECK_DEAD_NOTES)
2950     {
2951       blocks = sbitmap_alloc (last_basic_block);
2952       deaths_in_region = (int *) xmalloc (sizeof (int) * nr_regions);
2953       /* Remove all death notes from the subroutine.  */
2954       for (rgn = 0; rgn < nr_regions; rgn++)
2955         {
2956           int b;
2957
2958           sbitmap_zero (blocks);
2959           for (b = RGN_NR_BLOCKS (rgn) - 1; b >= 0; --b)
2960             SET_BIT (blocks, rgn_bb_table[RGN_BLOCKS (rgn) + b]);
2961
2962           deaths_in_region[rgn] = count_or_remove_death_notes (blocks, 1);
2963         }
2964       sbitmap_free (blocks);
2965     }
2966   else
2967     count_or_remove_death_notes (NULL, 1);
2968 }
2969
2970 /* The one entry point in this file.  DUMP_FILE is the dump file for
2971    this pass.  */
2972
2973 void
2974 schedule_insns (dump_file)
2975      FILE *dump_file;
2976 {
2977   sbitmap large_region_blocks, blocks;
2978   int rgn;
2979   int any_large_regions;
2980   basic_block bb;
2981
2982   /* Taking care of this degenerate case makes the rest of
2983      this code simpler.  */
2984   if (n_basic_blocks == 0)
2985     return;
2986
2987   nr_inter = 0;
2988   nr_spec = 0;
2989
2990   sched_init (dump_file);
2991
2992   init_regions ();
2993
2994   current_sched_info = &region_sched_info;
2995
2996   /* Schedule every region in the subroutine.  */
2997   for (rgn = 0; rgn < nr_regions; rgn++)
2998     schedule_region (rgn);
2999
3000   /* Update life analysis for the subroutine.  Do single block regions
3001      first so that we can verify that live_at_start didn't change.  Then
3002      do all other blocks.  */
3003   /* ??? There is an outside possibility that update_life_info, or more
3004      to the point propagate_block, could get called with nonzero flags
3005      more than once for one basic block.  This would be kinda bad if it
3006      were to happen, since REG_INFO would be accumulated twice for the
3007      block, and we'd have twice the REG_DEAD notes.
3008
3009      I'm fairly certain that this _shouldn't_ happen, since I don't think
3010      that live_at_start should change at region heads.  Not sure what the
3011      best way to test for this kind of thing...  */
3012
3013   allocate_reg_life_data ();
3014   compute_bb_for_insn ();
3015
3016   any_large_regions = 0;
3017   large_region_blocks = sbitmap_alloc (last_basic_block);
3018   sbitmap_zero (large_region_blocks);
3019   FOR_EACH_BB (bb)
3020     SET_BIT (large_region_blocks, bb->index);
3021
3022   blocks = sbitmap_alloc (last_basic_block);
3023   sbitmap_zero (blocks);
3024
3025   /* Update life information.  For regions consisting of multiple blocks
3026      we've possibly done interblock scheduling that affects global liveness.
3027      For regions consisting of single blocks we need to do only local
3028      liveness.  */
3029   for (rgn = 0; rgn < nr_regions; rgn++)
3030     if (RGN_NR_BLOCKS (rgn) > 1)
3031       any_large_regions = 1;
3032     else
3033       {
3034         SET_BIT (blocks, rgn_bb_table[RGN_BLOCKS (rgn)]);
3035         RESET_BIT (large_region_blocks, rgn_bb_table[RGN_BLOCKS (rgn)]);
3036       }
3037
3038   /* Don't update reg info after reload, since that affects
3039      regs_ever_live, which should not change after reload.  */
3040   update_life_info (blocks, UPDATE_LIFE_LOCAL,
3041                     (reload_completed ? PROP_DEATH_NOTES
3042                      : PROP_DEATH_NOTES | PROP_REG_INFO));
3043   if (any_large_regions)
3044     {
3045       update_life_info (large_region_blocks, UPDATE_LIFE_GLOBAL,
3046                         PROP_DEATH_NOTES | PROP_REG_INFO);
3047     }
3048
3049   if (CHECK_DEAD_NOTES)
3050     {
3051       /* Verify the counts of basic block notes in single the basic block
3052          regions.  */
3053       for (rgn = 0; rgn < nr_regions; rgn++)
3054         if (RGN_NR_BLOCKS (rgn) == 1)
3055           {
3056             sbitmap_zero (blocks);
3057             SET_BIT (blocks, rgn_bb_table[RGN_BLOCKS (rgn)]);
3058
3059             if (deaths_in_region[rgn]
3060                 != count_or_remove_death_notes (blocks, 0))
3061               abort ();
3062           }
3063       free (deaths_in_region);
3064     }
3065
3066   /* Reposition the prologue and epilogue notes in case we moved the
3067      prologue/epilogue insns.  */
3068   if (reload_completed)
3069     reposition_prologue_and_epilogue_notes (get_insns ());
3070
3071   /* Delete redundant line notes.  */
3072   if (write_symbols != NO_DEBUG)
3073     rm_redundant_line_notes ();
3074
3075   if (sched_verbose)
3076     {
3077       if (reload_completed == 0 && flag_schedule_interblock)
3078         {
3079           fprintf (sched_dump,
3080                    "\n;; Procedure interblock/speculative motions == %d/%d \n",
3081                    nr_inter, nr_spec);
3082         }
3083       else
3084         {
3085           if (nr_inter > 0)
3086             abort ();
3087         }
3088       fprintf (sched_dump, "\n\n");
3089     }
3090
3091   /* Clean up.  */
3092   free (rgn_table);
3093   free (rgn_bb_table);
3094   free (block_to_bb);
3095   free (containing_rgn);
3096
3097   sched_finish ();
3098
3099   if (edge_table)
3100     {
3101       free (edge_table);
3102       edge_table = NULL;
3103     }
3104
3105   if (in_edges)
3106     {
3107       free (in_edges);
3108       in_edges = NULL;
3109     }
3110   if (out_edges)
3111     {
3112       free (out_edges);
3113       out_edges = NULL;
3114     }
3115
3116   sbitmap_free (blocks);
3117   sbitmap_free (large_region_blocks);
3118 }
3119 #endif