gcc/sched-ebb.c

   1 /* Instruction scheduling pass.
   2    Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
   3    1999, 2000, 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
   4    Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
   5    and currently maintained by, Jim Wilson (wilson@cygnus.com)
   6
   7 This file is part of GCC.
   8
   9 GCC is free software; you can redistribute it and/or modify it under
  10 the terms of the GNU General Public License as published by the Free
  11 Software Foundation; either version 2, or (at your option) any later
  12 version.
  13
  14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  16 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  17 for more details.
  18
  19 You should have received a copy of the GNU General Public License
  20 along with GCC; see the file COPYING.  If not, write to the Free
  21 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  22 02110-1301, USA.  */
  23 \f
  24 #include "config.h"
  25 #include "system.h"
  26 #include "coretypes.h"
  27 #include "tm.h"
  28 #include "toplev.h"
  29 #include "rtl.h"
  30 #include "tm_p.h"
  31 #include "hard-reg-set.h"
  32 #include "regs.h"
  33 #include "function.h"
  34 #include "flags.h"
  35 #include "insn-config.h"
  36 #include "insn-attr.h"
  37 #include "except.h"
  38 #include "toplev.h"
  39 #include "recog.h"
  40 #include "cfglayout.h"
  41 #include "params.h"
  42 #include "sched-int.h"
  43 #include "target.h"
  44 #include "output.h"
  45 \f
  46 /* The number of insns scheduled so far.  */
  47 static int sched_n_insns;
  48
  49 /* The number of insns to be scheduled in total.  */
  50 static int n_insns;
  51
  52 /* Set of blocks, that already have their dependencies calculated.  */
  53 static bitmap_head dont_calc_deps;
  54 /* Set of basic blocks, that are ebb heads of tails respectively.  */
  55 static bitmap_head ebb_head, ebb_tail;
  56
  57 /* Last basic block in current ebb.  */
  58 static basic_block last_bb;
  59
  60 /* Implementations of the sched_info functions for region scheduling.  */
  61 static void init_ready_list (void);
  62 static void begin_schedule_ready (rtx, rtx);
  63 static int schedule_more_p (void);
  64 static const char *ebb_print_insn (rtx, int);
  65 static int rank (rtx, rtx);
  66 static int contributes_to_priority (rtx, rtx);
  67 static void compute_jump_reg_dependencies (rtx, regset, regset, regset);
  68 static basic_block earliest_block_with_similiar_load (basic_block, rtx);
  69 static void add_deps_for_risky_insns (rtx, rtx);
  70 static basic_block schedule_ebb (rtx, rtx);
  71
  72 static void add_remove_insn (rtx, int);
  73 static void add_block1 (basic_block, basic_block);
  74 static basic_block advance_target_bb (basic_block, rtx);
  75 static void fix_recovery_cfg (int, int, int);
  76
  77 #ifdef ENABLE_CHECKING
  78 static int ebb_head_or_leaf_p (basic_block, int);
  79 #endif
  80
  81 /* Return nonzero if there are more insns that should be scheduled.  */
  82
  83 static int
  84 schedule_more_p (void)
  85 {
  86   return sched_n_insns < n_insns;
  87 }
  88
  89 /* Print dependency information about ebb between HEAD and TAIL.  */
  90 static void
  91 debug_ebb_dependencies (rtx head, rtx tail)
  92 {
  93   fprintf (sched_dump,
  94            ";;   --------------- forward dependences: ------------ \n");
  95
  96   fprintf (sched_dump, "\n;;   --- EBB Dependences --- from bb%d to bb%d \n",
  97            BLOCK_NUM (head), BLOCK_NUM (tail));
  98
  99   debug_dependencies (head, tail);
 100 }
 101
 102 /* Add all insns that are initially ready to the ready list READY.  Called
 103    once before scheduling a set of insns.  */
 104
 105 static void
 106 init_ready_list (void)
 107 {
 108   int n = 0;
 109   rtx prev_head = current_sched_info->prev_head;
 110   rtx next_tail = current_sched_info->next_tail;
 111   rtx insn;
 112
 113   sched_n_insns = 0;
 114
 115   /* Print debugging information.  */
 116   if (sched_verbose >= 5)
 117     debug_ebb_dependencies (NEXT_INSN (prev_head), PREV_INSN (next_tail));
 118
 119   /* Initialize ready list with all 'ready' insns in target block.
 120      Count number of insns in the target block being scheduled.  */
 121   for (insn = NEXT_INSN (prev_head); insn != next_tail; insn = NEXT_INSN (insn))
 122     {
 123       try_ready (insn);
 124       n++;
 125     }
 126
 127   gcc_assert (n == n_insns);
 128 }
 129
 130 /* INSN is being scheduled after LAST.  Update counters.  */
 131 static void
 132 begin_schedule_ready (rtx insn, rtx last)
 133 {
 134   sched_n_insns++;
 135
 136   if (BLOCK_FOR_INSN (insn) == last_bb
 137       /* INSN is a jump in the last block, ...  */
 138       && control_flow_insn_p (insn)
 139       /* that is going to be moved over some instructions.  */
 140       && last != PREV_INSN (insn))
 141     {
 142       edge e;
 143       edge_iterator ei;
 144       basic_block bb;
 145
 146       /* An obscure special case, where we do have partially dead
 147          instruction scheduled after last control flow instruction.
 148          In this case we can create new basic block.  It is
 149          always exactly one basic block last in the sequence.  */
 150
 151       FOR_EACH_EDGE (e, ei, last_bb->succs)
 152         if (e->flags & EDGE_FALLTHRU)
 153           break;
 154
 155 #ifdef ENABLE_CHECKING
 156       gcc_assert (!e || !(e->flags & EDGE_COMPLEX));
 157
 158       gcc_assert (BLOCK_FOR_INSN (insn) == last_bb
 159                   && !IS_SPECULATION_CHECK_P (insn)
 160                   && BB_HEAD (last_bb) != insn
 161                   && BB_END (last_bb) == insn);
 162
 163       {
 164         rtx x;
 165
 166         x = NEXT_INSN (insn);
 167         if (e)
 168           gcc_assert (NOTE_P (x) || LABEL_P (x));
 169         else
 170           gcc_assert (BARRIER_P (x));
 171       }
 172 #endif
 173
 174       if (e)
 175         {
 176           bb = split_edge (e);
 177           gcc_assert (NOTE_INSN_BASIC_BLOCK_P (BB_END (bb)));
 178         }
 179       else
 180         /* Create an empty unreachable block after the INSN.  */
 181         bb = create_basic_block (NEXT_INSN (insn), NULL_RTX, last_bb);
 182
 183       /* split_edge () creates BB before E->DEST.  Keep in mind, that
 184          this operation extends scheduling region till the end of BB.
 185          Hence, we need to shift NEXT_TAIL, so haifa-sched.c won't go out
 186          of the scheduling region.  */
 187       current_sched_info->next_tail = NEXT_INSN (BB_END (bb));
 188       gcc_assert (current_sched_info->next_tail);
 189
 190       add_block (bb, last_bb);
 191       gcc_assert (last_bb == bb);
 192     }
 193 }
 194
 195 /* Return a string that contains the insn uid and optionally anything else
 196    necessary to identify this insn in an output.  It's valid to use a
 197    static buffer for this.  The ALIGNED parameter should cause the string
 198    to be formatted so that multiple output lines will line up nicely.  */
 199
 200 static const char *
 201 ebb_print_insn (rtx insn, int aligned ATTRIBUTE_UNUSED)
 202 {
 203   static char tmp[80];
 204
 205   sprintf (tmp, "%4d", INSN_UID (insn));
 206   return tmp;
 207 }
 208
 209 /* Compare priority of two insns.  Return a positive number if the second
 210    insn is to be preferred for scheduling, and a negative one if the first
 211    is to be preferred.  Zero if they are equally good.  */
 212
 213 static int
 214 rank (rtx insn1, rtx insn2)
 215 {
 216   basic_block bb1 = BLOCK_FOR_INSN (insn1);
 217   basic_block bb2 = BLOCK_FOR_INSN (insn2);
 218
 219   if (bb1->count > bb2->count
 220       || bb1->frequency > bb2->frequency)
 221     return -1;
 222   if (bb1->count < bb2->count
 223       || bb1->frequency < bb2->frequency)
 224     return 1;
 225   return 0;
 226 }
 227
 228 /* NEXT is an instruction that depends on INSN (a backward dependence);
 229    return nonzero if we should include this dependence in priority
 230    calculations.  */
 231
 232 static int
 233 contributes_to_priority (rtx next ATTRIBUTE_UNUSED,
 234                          rtx insn ATTRIBUTE_UNUSED)
 235 {
 236   return 1;
 237 }
 238
 239  /* INSN is a JUMP_INSN, COND_SET is the set of registers that are
 240     conditionally set before INSN.  Store the set of registers that
 241     must be considered as used by this jump in USED and that of
 242     registers that must be considered as set in SET.  */
 243
 244 static void
 245 compute_jump_reg_dependencies (rtx insn, regset cond_set, regset used,
 246                                regset set)
 247 {
 248   basic_block b = BLOCK_FOR_INSN (insn);
 249   edge e;
 250   edge_iterator ei;
 251
 252   FOR_EACH_EDGE (e, ei, b->succs)
 253     if (e->flags & EDGE_FALLTHRU)
 254       /* The jump may be a by-product of a branch that has been merged
 255          in the main codepath after being conditionalized.  Therefore
 256          it may guard the fallthrough block from using a value that has
 257          conditionally overwritten that of the main codepath.  So we
 258          consider that it restores the value of the main codepath.  */
 259       bitmap_and (set, glat_start [e->dest->index], cond_set);
 260     else
 261       bitmap_ior_into (used, glat_start [e->dest->index]);
 262 }
 263
 264 /* Used in schedule_insns to initialize current_sched_info for scheduling
 265    regions (or single basic blocks).  */
 266
 267 static struct sched_info ebb_sched_info =
 268 {
 269   init_ready_list,
 270   NULL,
 271   schedule_more_p,
 272   NULL,
 273   rank,
 274   ebb_print_insn,
 275   contributes_to_priority,
 276   compute_jump_reg_dependencies,
 277
 278   NULL, NULL,
 279   NULL, NULL,
 280   0, 1, 0,
 281
 282   add_remove_insn,
 283   begin_schedule_ready,
 284   add_block1,
 285   advance_target_bb,
 286   fix_recovery_cfg,
 287 #ifdef ENABLE_CHECKING
 288   ebb_head_or_leaf_p,
 289 #endif
 290   /* We need to DETACH_LIVE_INFO to be able to create new basic blocks.
 291      See begin_schedule_ready ().  */
 292   SCHED_EBB | USE_GLAT | DETACH_LIFE_INFO
 293 };
 294 \f
 295 /* Returns the earliest block in EBB currently being processed where a
 296    "similar load" 'insn2' is found, and hence LOAD_INSN can move
 297    speculatively into the found block.  All the following must hold:
 298
 299    (1) both loads have 1 base register (PFREE_CANDIDATEs).
 300    (2) load_insn and load2 have a def-use dependence upon
 301    the same insn 'insn1'.
 302
 303    From all these we can conclude that the two loads access memory
 304    addresses that differ at most by a constant, and hence if moving
 305    load_insn would cause an exception, it would have been caused by
 306    load2 anyhow.
 307
 308    The function uses list (given by LAST_BLOCK) of already processed
 309    blocks in EBB.  The list is formed in `add_deps_for_risky_insns'.  */
 310
 311 static basic_block
 312 earliest_block_with_similiar_load (basic_block last_block, rtx load_insn)
 313 {
 314   dep_link_t back_link;
 315   basic_block bb, earliest_block = NULL;
 316
 317   FOR_EACH_DEP_LINK (back_link, INSN_BACK_DEPS (load_insn))
 318     {
 319       rtx insn1 = DEP_LINK_PRO (back_link);
 320
 321       if (DEP_LINK_KIND (back_link) == REG_DEP_TRUE)
 322         {
 323           /* Found a DEF-USE dependence (insn1, load_insn).  */
 324           dep_link_t fore_link;
 325
 326           FOR_EACH_DEP_LINK (fore_link, INSN_FORW_DEPS (insn1))
 327             {
 328               rtx insn2 = DEP_LINK_CON (fore_link);
 329               basic_block insn2_block = BLOCK_FOR_INSN (insn2);
 330
 331               if (DEP_LINK_KIND (fore_link) == REG_DEP_TRUE)
 332                 {
 333                   if (earliest_block != NULL
 334                       && earliest_block->index < insn2_block->index)
 335                     continue;
 336
 337                   /* Found a DEF-USE dependence (insn1, insn2).  */
 338                   if (haifa_classify_insn (insn2) != PFREE_CANDIDATE)
 339                     /* insn2 not guaranteed to be a 1 base reg load.  */
 340                     continue;
 341
 342                   for (bb = last_block; bb; bb = bb->aux)
 343                     if (insn2_block == bb)
 344                       break;
 345
 346                   if (!bb)
 347                     /* insn2 is the similar load.  */
 348                     earliest_block = insn2_block;
 349                 }
 350             }
 351         }
 352     }
 353
 354   return earliest_block;
 355 }
 356
 357 /* The following function adds dependencies between jumps and risky
 358    insns in given ebb.  */
 359
 360 static void
 361 add_deps_for_risky_insns (rtx head, rtx tail)
 362 {
 363   rtx insn, prev;
 364   int class;
 365   rtx last_jump = NULL_RTX;
 366   rtx next_tail = NEXT_INSN (tail);
 367   basic_block last_block = NULL, bb;
 368
 369   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
 370     if (control_flow_insn_p (insn))
 371       {
 372         bb = BLOCK_FOR_INSN (insn);
 373         bb->aux = last_block;
 374         last_block = bb;
 375         last_jump = insn;
 376       }
 377     else if (INSN_P (insn) && last_jump != NULL_RTX)
 378       {
 379         class = haifa_classify_insn (insn);
 380         prev = last_jump;
 381         switch (class)
 382           {
 383           case PFREE_CANDIDATE:
 384             if (flag_schedule_speculative_load)
 385               {
 386                 bb = earliest_block_with_similiar_load (last_block, insn);
 387                 if (bb)
 388                   {
 389                     bb = bb->aux;
 390                     if (!bb)
 391                       break;
 392                     prev = BB_END (bb);
 393                   }
 394               }
 395             /* Fall through.  */
 396           case TRAP_RISKY:
 397           case IRISKY:
 398           case PRISKY_CANDIDATE:
 399             /* ??? We could implement better checking PRISKY_CANDIDATEs
 400                analogous to sched-rgn.c.  */
 401             /* We can not change the mode of the backward
 402                dependency because REG_DEP_ANTI has the lowest
 403                rank.  */
 404             if (! sched_insns_conditions_mutex_p (insn, prev))
 405               {
 406                 if (!(current_sched_info->flags & DO_SPECULATION))
 407                   {
 408                     enum DEPS_ADJUST_RESULT res;
 409
 410                     res = add_or_update_back_dep (insn, prev,
 411                                                   REG_DEP_ANTI, DEP_ANTI);
 412
 413                     if (res == DEP_CREATED)
 414                       add_forw_dep (DEPS_LIST_FIRST (INSN_BACK_DEPS (insn)));
 415                     else
 416                       gcc_assert (res != DEP_CHANGED);
 417                   }
 418                 else
 419                   add_or_update_back_forw_dep (insn, prev, REG_DEP_ANTI,
 420                                                set_dep_weak (DEP_ANTI,
 421                                                              BEGIN_CONTROL,
 422                                                              MAX_DEP_WEAK));
 423               }
 424
 425             break;
 426
 427           default:
 428             break;
 429           }
 430       }
 431   /* Maintain the invariant that bb->aux is clear after use.  */
 432   while (last_block)
 433     {
 434       bb = last_block->aux;
 435       last_block->aux = NULL;
 436       last_block = bb;
 437     }
 438 }
 439
 440 /* Schedule a single extended basic block, defined by the boundaries HEAD
 441    and TAIL.  */
 442
 443 static basic_block
 444 schedule_ebb (rtx head, rtx tail)
 445 {
 446   basic_block first_bb, target_bb;
 447   struct deps tmp_deps;
 448
 449   first_bb = BLOCK_FOR_INSN (head);
 450   last_bb = BLOCK_FOR_INSN (tail);
 451
 452   if (no_real_insns_p (head, tail))
 453     return BLOCK_FOR_INSN (tail);
 454
 455   gcc_assert (INSN_P (head) && INSN_P (tail));
 456
 457   if (!bitmap_bit_p (&dont_calc_deps, first_bb->index))
 458     {
 459       init_deps_global ();
 460
 461       /* Compute backward dependencies.  */
 462       init_deps (&tmp_deps);
 463       sched_analyze (&tmp_deps, head, tail);
 464       free_deps (&tmp_deps);
 465
 466       /* Compute forward dependencies.  */
 467       compute_forward_dependences (head, tail);
 468
 469       add_deps_for_risky_insns (head, tail);
 470
 471       if (targetm.sched.dependencies_evaluation_hook)
 472         targetm.sched.dependencies_evaluation_hook (head, tail);
 473
 474       finish_deps_global ();
 475     }
 476   else
 477     /* Only recovery blocks can have their dependencies already calculated,
 478        and they always are single block ebbs.  */
 479     gcc_assert (first_bb == last_bb);
 480
 481   /* Set priorities.  */
 482   current_sched_info->sched_max_insns_priority = 0;
 483   n_insns = set_priorities (head, tail);
 484   current_sched_info->sched_max_insns_priority++;
 485
 486   current_sched_info->prev_head = PREV_INSN (head);
 487   current_sched_info->next_tail = NEXT_INSN (tail);
 488
 489   /* rm_other_notes only removes notes which are _inside_ the
 490      block---that is, it won't remove notes before the first real insn
 491      or after the last real insn of the block.  So if the first insn
 492      has a REG_SAVE_NOTE which would otherwise be emitted before the
 493      insn, it is redundant with the note before the start of the
 494      block, and so we have to take it out.  */
 495   if (INSN_P (head))
 496     {
 497       rtx note;
 498
 499       for (note = REG_NOTES (head); note; note = XEXP (note, 1))
 500         if (REG_NOTE_KIND (note) == REG_SAVE_NOTE)
 501           remove_note (head, note);
 502     }
 503
 504   /* Remove remaining note insns from the block, save them in
 505      note_list.  These notes are restored at the end of
 506      schedule_block ().  */
 507   rm_other_notes (head, tail);
 508
 509   unlink_bb_notes (first_bb, last_bb);
 510
 511   current_sched_info->queue_must_finish_empty = 1;
 512
 513   target_bb = first_bb;
 514   schedule_block (&target_bb, n_insns);
 515
 516   /* We might pack all instructions into fewer blocks,
 517      so we may made some of them empty.  Can't assert (b == last_bb).  */
 518
 519   /* Sanity check: verify that all region insns were scheduled.  */
 520   gcc_assert (sched_n_insns == n_insns);
 521   head = current_sched_info->head;
 522   tail = current_sched_info->tail;
 523
 524   if (EDGE_COUNT (last_bb->preds) == 0)
 525     /* LAST_BB is unreachable.  */
 526     {
 527       gcc_assert (first_bb != last_bb
 528                   && EDGE_COUNT (last_bb->succs) == 0);
 529       last_bb = last_bb->prev_bb;
 530       delete_basic_block (last_bb->next_bb);
 531     }
 532
 533   return last_bb;
 534 }
 535
 536 /* The one entry point in this file.  */
 537
 538 void
 539 schedule_ebbs (void)
 540 {
 541   basic_block bb;
 542   int probability_cutoff;
 543   rtx tail;
 544   sbitmap large_region_blocks, blocks;
 545   int any_large_regions;
 546
 547   if (profile_info && flag_branch_probabilities)
 548     probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY_FEEDBACK);
 549   else
 550     probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY);
 551   probability_cutoff = REG_BR_PROB_BASE / 100 * probability_cutoff;
 552
 553   /* Taking care of this degenerate case makes the rest of
 554      this code simpler.  */
 555   if (n_basic_blocks == NUM_FIXED_BLOCKS)
 556     return;
 557
 558   /* We need current_sched_info in init_dependency_caches, which is
 559      invoked via sched_init.  */
 560   current_sched_info = &ebb_sched_info;
 561
 562   sched_init ();
 563
 564   compute_bb_for_insn ();
 565
 566   /* Initialize DONT_CALC_DEPS and ebb-{start, end} markers.  */
 567   bitmap_initialize (&dont_calc_deps, 0);
 568   bitmap_clear (&dont_calc_deps);
 569   bitmap_initialize (&ebb_head, 0);
 570   bitmap_clear (&ebb_head);
 571   bitmap_initialize (&ebb_tail, 0);
 572   bitmap_clear (&ebb_tail);
 573
 574   /* Schedule every region in the subroutine.  */
 575   FOR_EACH_BB (bb)
 576     {
 577       rtx head = BB_HEAD (bb);
 578
 579       for (;;)
 580         {
 581           edge e;
 582           edge_iterator ei;
 583           tail = BB_END (bb);
 584           if (bb->next_bb == EXIT_BLOCK_PTR
 585               || LABEL_P (BB_HEAD (bb->next_bb)))
 586             break;
 587           FOR_EACH_EDGE (e, ei, bb->succs)
 588             if ((e->flags & EDGE_FALLTHRU) != 0)
 589               break;
 590           if (! e)
 591             break;
 592           if (e->probability <= probability_cutoff)
 593             break;
 594           bb = bb->next_bb;
 595         }
 596
 597       /* Blah.  We should fix the rest of the code not to get confused by
 598          a note or two.  */
 599       while (head != tail)
 600         {
 601           if (NOTE_P (head))
 602             head = NEXT_INSN (head);
 603           else if (NOTE_P (tail))
 604             tail = PREV_INSN (tail);
 605           else if (LABEL_P (head))
 606             head = NEXT_INSN (head);
 607           else
 608             break;
 609         }
 610
 611       bitmap_set_bit (&ebb_head, BLOCK_NUM (head));
 612       bb = schedule_ebb (head, tail);
 613       bitmap_set_bit (&ebb_tail, bb->index);
 614     }
 615   bitmap_clear (&dont_calc_deps);
 616
 617   gcc_assert (current_sched_info->flags & DETACH_LIFE_INFO);
 618   /* We can create new basic blocks during scheduling, and
 619      attach_life_info () will create regsets for them
 620      (along with attaching existing info back).  */
 621   attach_life_info ();
 622
 623   /* Updating register live information.  */
 624   allocate_reg_life_data ();
 625
 626   any_large_regions = 0;
 627   large_region_blocks = sbitmap_alloc (last_basic_block);
 628   sbitmap_zero (large_region_blocks);
 629   FOR_EACH_BB (bb)
 630     SET_BIT (large_region_blocks, bb->index);
 631
 632   blocks = sbitmap_alloc (last_basic_block);
 633   sbitmap_zero (blocks);
 634
 635   /* Update life information.  For regions consisting of multiple blocks
 636      we've possibly done interblock scheduling that affects global liveness.
 637      For regions consisting of single blocks we need to do only local
 638      liveness.  */
 639   FOR_EACH_BB (bb)
 640     {
 641       int bbi;
 642
 643       bbi = bb->index;
 644
 645       if (!bitmap_bit_p (&ebb_head, bbi)
 646           || !bitmap_bit_p (&ebb_tail, bbi)
 647           /* New blocks (e.g. recovery blocks) should be processed
 648              as parts of large regions.  */
 649           || !glat_start[bbi])
 650         any_large_regions = 1;
 651       else
 652         {
 653           SET_BIT (blocks, bbi);
 654           RESET_BIT (large_region_blocks, bbi);
 655         }
 656     }
 657
 658   update_life_info (blocks, UPDATE_LIFE_LOCAL, 0);
 659   sbitmap_free (blocks);
 660
 661   if (any_large_regions)
 662     {
 663       update_life_info (large_region_blocks, UPDATE_LIFE_GLOBAL, 0);
 664
 665 #ifdef ENABLE_CHECKING
 666       /* !!! We can't check reg_live_info here because of the fact,
 667          that destination registers of COND_EXEC's may be dead
 668          before scheduling (while they should be alive).  Don't know why.  */
 669       /*check_reg_live (true);*/
 670 #endif
 671     }
 672   sbitmap_free (large_region_blocks);
 673
 674   bitmap_clear (&ebb_head);
 675   bitmap_clear (&ebb_tail);
 676
 677   /* Reposition the prologue and epilogue notes in case we moved the
 678      prologue/epilogue insns.  */
 679   if (reload_completed)
 680     reposition_prologue_and_epilogue_notes (get_insns ());
 681
 682   sched_finish ();
 683 }
 684
 685 /* INSN has been added to/removed from current ebb.  */
 686 static void
 687 add_remove_insn (rtx insn ATTRIBUTE_UNUSED, int remove_p)
 688 {
 689   if (!remove_p)
 690     n_insns++;
 691   else
 692     n_insns--;
 693 }
 694
 695 /* BB was added to ebb after AFTER.  */
 696 static void
 697 add_block1 (basic_block bb, basic_block after)
 698 {
 699   /* Recovery blocks are always bounded by BARRIERS,
 700      therefore, they always form single block EBB,
 701      therefore, we can use rec->index to identify such EBBs.  */
 702   if (after == EXIT_BLOCK_PTR)
 703     bitmap_set_bit (&dont_calc_deps, bb->index);
 704   else if (after == last_bb)
 705     last_bb = bb;
 706 }
 707
 708 /* Return next block in ebb chain.  For parameter meaning please refer to
 709    sched-int.h: struct sched_info: advance_target_bb.  */
 710 static basic_block
 711 advance_target_bb (basic_block bb, rtx insn)
 712 {
 713   if (insn)
 714     {
 715       if (BLOCK_FOR_INSN (insn) != bb
 716           && control_flow_insn_p (insn)
 717           /* We handle interblock movement of the speculation check
 718              or over a speculation check in
 719              haifa-sched.c: move_block_after_check ().  */
 720           && !IS_SPECULATION_BRANCHY_CHECK_P (insn)
 721           && !IS_SPECULATION_BRANCHY_CHECK_P (BB_END (bb)))
 722         {
 723           /* Assert that we don't move jumps across blocks.  */
 724           gcc_assert (!control_flow_insn_p (BB_END (bb))
 725                       && NOTE_INSN_BASIC_BLOCK_P (BB_HEAD (bb->next_bb)));
 726           return bb;
 727         }
 728       else
 729         return 0;
 730     }
 731   else
 732     /* Return next non empty block.  */
 733     {
 734       do
 735         {
 736           gcc_assert (bb != last_bb);
 737
 738           bb = bb->next_bb;
 739         }
 740       while (bb_note (bb) == BB_END (bb));
 741
 742       return bb;
 743     }
 744 }
 745
 746 /* Fix internal data after interblock movement of jump instruction.
 747    For parameter meaning please refer to
 748    sched-int.h: struct sched_info: fix_recovery_cfg.  */
 749 static void
 750 fix_recovery_cfg (int bbi ATTRIBUTE_UNUSED, int jump_bbi, int jump_bb_nexti)
 751 {
 752   gcc_assert (last_bb->index != bbi);
 753
 754   if (jump_bb_nexti == last_bb->index)
 755     last_bb = BASIC_BLOCK (jump_bbi);
 756 }
 757
 758 #ifdef ENABLE_CHECKING
 759 /* Return non zero, if BB is first or last (depending of LEAF_P) block in
 760    current ebb.  For more information please refer to
 761    sched-int.h: struct sched_info: region_head_or_leaf_p.  */
 762 static int
 763 ebb_head_or_leaf_p (basic_block bb, int leaf_p)
 764 {
 765   if (!leaf_p)
 766     return bitmap_bit_p (&ebb_head, bb->index);
 767   else
 768     return bitmap_bit_p (&ebb_tail, bb->index);
 769 }
 770 #endif /* ENABLE_CHECKING  */