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, 59 Temple Place - Suite 330, Boston, MA
  22 02111-1307, 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 \f
  45 /* The number of insns to be scheduled in total.  */
  46 static int target_n_insns;
  47 /* The number of insns scheduled so far.  */
  48 static int sched_n_insns;
  49
  50 /* Implementations of the sched_info functions for region scheduling.  */
  51 static void init_ready_list (struct ready_list *);
  52 static int can_schedule_ready_p (rtx);
  53 static int new_ready (rtx);
  54 static int schedule_more_p (void);
  55 static const char *ebb_print_insn (rtx, int);
  56 static int rank (rtx, rtx);
  57 static int contributes_to_priority (rtx, rtx);
  58 static void compute_jump_reg_dependencies (rtx, regset, regset, regset);
  59 static basic_block earliest_block_with_similiar_load (basic_block, rtx);
  60 static void add_deps_for_risky_insns (rtx, rtx);
  61 static basic_block schedule_ebb (rtx, rtx);
  62 static basic_block fix_basic_block_boundaries (basic_block, basic_block, rtx,
  63                                                rtx);
  64 static void add_missing_bbs (rtx, basic_block, basic_block);
  65
  66 /* Return nonzero if there are more insns that should be scheduled.  */
  67
  68 static int
  69 schedule_more_p (void)
  70 {
  71   return sched_n_insns < target_n_insns;
  72 }
  73
  74 /* Add all insns that are initially ready to the ready list READY.  Called
  75    once before scheduling a set of insns.  */
  76
  77 static void
  78 init_ready_list (struct ready_list *ready)
  79 {
  80   rtx prev_head = current_sched_info->prev_head;
  81   rtx next_tail = current_sched_info->next_tail;
  82   rtx insn;
  83
  84   target_n_insns = 0;
  85   sched_n_insns = 0;
  86
  87 #if 0
  88   /* Print debugging information.  */
  89   if (sched_verbose >= 5)
  90     debug_dependencies ();
  91 #endif
  92
  93   /* Initialize ready list with all 'ready' insns in target block.
  94      Count number of insns in the target block being scheduled.  */
  95   for (insn = NEXT_INSN (prev_head); insn != next_tail; insn = NEXT_INSN (insn))
  96     {
  97       if (INSN_DEP_COUNT (insn) == 0)
  98         ready_add (ready, insn);
  99       target_n_insns++;
 100     }
 101 }
 102
 103 /* Called after taking INSN from the ready list.  Returns nonzero if this
 104    insn can be scheduled, nonzero if we should silently discard it.  */
 105
 106 static int
 107 can_schedule_ready_p (rtx insn ATTRIBUTE_UNUSED)
 108 {
 109   sched_n_insns++;
 110   return 1;
 111 }
 112
 113 /* Called after INSN has all its dependencies resolved.  Return nonzero
 114    if it should be moved to the ready list or the queue, or zero if we
 115    should silently discard it.  */
 116 static int
 117 new_ready (rtx next ATTRIBUTE_UNUSED)
 118 {
 119   return 1;
 120 }
 121
 122 /* Return a string that contains the insn uid and optionally anything else
 123    necessary to identify this insn in an output.  It's valid to use a
 124    static buffer for this.  The ALIGNED parameter should cause the string
 125    to be formatted so that multiple output lines will line up nicely.  */
 126
 127 static const char *
 128 ebb_print_insn (rtx insn, int aligned ATTRIBUTE_UNUSED)
 129 {
 130   static char tmp[80];
 131
 132   sprintf (tmp, "%4d", INSN_UID (insn));
 133   return tmp;
 134 }
 135
 136 /* Compare priority of two insns.  Return a positive number if the second
 137    insn is to be preferred for scheduling, and a negative one if the first
 138    is to be preferred.  Zero if they are equally good.  */
 139
 140 static int
 141 rank (rtx insn1, rtx insn2)
 142 {
 143   basic_block bb1 = BLOCK_FOR_INSN (insn1);
 144   basic_block bb2 = BLOCK_FOR_INSN (insn2);
 145
 146   if (bb1->count > bb2->count
 147       || bb1->frequency > bb2->frequency)
 148     return -1;
 149   if (bb1->count < bb2->count
 150       || bb1->frequency < bb2->frequency)
 151     return 1;
 152   return 0;
 153 }
 154
 155 /* NEXT is an instruction that depends on INSN (a backward dependence);
 156    return nonzero if we should include this dependence in priority
 157    calculations.  */
 158
 159 static int
 160 contributes_to_priority (rtx next ATTRIBUTE_UNUSED,
 161                          rtx insn ATTRIBUTE_UNUSED)
 162 {
 163   return 1;
 164 }
 165
 166  /* INSN is a JUMP_INSN, COND_SET is the set of registers that are
 167     conditionally set before INSN.  Store the set of registers that
 168     must be considered as used by this jump in USED and that of
 169     registers that must be considered as set in SET.  */
 170
 171 static void
 172 compute_jump_reg_dependencies (rtx insn, regset cond_set, regset used,
 173                                regset set)
 174 {
 175   basic_block b = BLOCK_FOR_INSN (insn);
 176   edge e;
 177   edge_iterator ei;
 178
 179   FOR_EACH_EDGE (e, ei, b->succs)
 180     if (e->flags & EDGE_FALLTHRU)
 181       /* The jump may be a by-product of a branch that has been merged
 182          in the main codepath after being conditionalized.  Therefore
 183          it may guard the fallthrough block from using a value that has
 184          conditionally overwritten that of the main codepath.  So we
 185          consider that it restores the value of the main codepath.  */
 186       bitmap_and (set, e->dest->global_live_at_start, cond_set);
 187     else
 188       bitmap_ior_into (used, e->dest->global_live_at_start);
 189 }
 190
 191 /* Used in schedule_insns to initialize current_sched_info for scheduling
 192    regions (or single basic blocks).  */
 193
 194 static struct sched_info ebb_sched_info =
 195 {
 196   init_ready_list,
 197   can_schedule_ready_p,
 198   schedule_more_p,
 199   new_ready,
 200   rank,
 201   ebb_print_insn,
 202   contributes_to_priority,
 203   compute_jump_reg_dependencies,
 204
 205   NULL, NULL,
 206   NULL, NULL,
 207   0, 1, 0
 208 };
 209 \f
 210 /* It is possible that ebb scheduling eliminated some blocks.
 211    Place blocks from FIRST to LAST before BEFORE.  */
 212
 213 static void
 214 add_missing_bbs (rtx before, basic_block first, basic_block last)
 215 {
 216   for (; last != first->prev_bb; last = last->prev_bb)
 217     {
 218       before = emit_note_before (NOTE_INSN_BASIC_BLOCK, before);
 219       NOTE_BASIC_BLOCK (before) = last;
 220       BB_HEAD (last) = before;
 221       BB_END (last) = before;
 222       update_bb_for_insn (last);
 223     }
 224 }
 225
 226 /* Fixup the CFG after EBB scheduling.  Re-recognize the basic
 227    block boundaries in between HEAD and TAIL and update basic block
 228    structures between BB and LAST.  */
 229
 230 static basic_block
 231 fix_basic_block_boundaries (basic_block bb, basic_block last, rtx head,
 232                             rtx tail)
 233 {
 234   rtx insn = head;
 235   rtx last_inside = BB_HEAD (bb);
 236   rtx aftertail = NEXT_INSN (tail);
 237
 238   head = BB_HEAD (bb);
 239
 240   for (; insn != aftertail; insn = NEXT_INSN (insn))
 241     {
 242       gcc_assert (!LABEL_P (insn));
 243       /* Create new basic blocks just before first insn.  */
 244       if (inside_basic_block_p (insn))
 245         {
 246           if (!last_inside)
 247             {
 248               rtx note;
 249
 250               /* Re-emit the basic block note for newly found BB header.  */
 251               if (LABEL_P (insn))
 252                 {
 253                   note = emit_note_after (NOTE_INSN_BASIC_BLOCK, insn);
 254                   head = insn;
 255                   last_inside = note;
 256                 }
 257               else
 258                 {
 259                   note = emit_note_before (NOTE_INSN_BASIC_BLOCK, insn);
 260                   head = note;
 261                   last_inside = insn;
 262                 }
 263             }
 264           else
 265             last_inside = insn;
 266         }
 267       /* Control flow instruction terminate basic block.  It is possible
 268          that we've eliminated some basic blocks (made them empty).
 269          Find the proper basic block using BLOCK_FOR_INSN and arrange things in
 270          a sensible way by inserting empty basic blocks as needed.  */
 271       if (control_flow_insn_p (insn) || (insn == tail && last_inside))
 272         {
 273           basic_block curr_bb = BLOCK_FOR_INSN (insn);
 274           rtx note;
 275
 276           if (!control_flow_insn_p (insn))
 277             curr_bb = last;
 278           if (bb == last->next_bb)
 279             {
 280               edge f;
 281               rtx h;
 282               edge_iterator ei;
 283
 284               /* An obscure special case, where we do have partially dead
 285                  instruction scheduled after last control flow instruction.
 286                  In this case we can create new basic block.  It is
 287                  always exactly one basic block last in the sequence.  Handle
 288                  it by splitting the edge and repositioning the block.
 289                  This is somewhat hackish, but at least avoid cut&paste
 290
 291                  A safer solution can be to bring the code into sequence,
 292                  do the split and re-emit it back in case this will ever
 293                  trigger problem.  */
 294
 295               FOR_EACH_EDGE (f, ei, bb->prev_bb->succs)
 296                 if (f->flags & EDGE_FALLTHRU)
 297                   break;
 298
 299               if (f)
 300                 {
 301                   last = curr_bb = split_edge (f);
 302                   h = BB_HEAD (curr_bb);
 303                   BB_HEAD (curr_bb) = head;
 304                   BB_END (curr_bb) = insn;
 305                   /* Edge splitting created misplaced BASIC_BLOCK note, kill
 306                      it.  */
 307                   delete_insn (h);
 308                 }
 309               /* It may happen that code got moved past unconditional jump in
 310                  case the code is completely dead.  Kill it.  */
 311               else
 312                 {
 313                   rtx next = next_nonnote_insn (insn);
 314                   delete_insn_chain (head, insn);
 315                   /* We keep some notes in the way that may split barrier from the
 316                      jump.  */
 317                   if (BARRIER_P (next))
 318                      {
 319                        emit_barrier_after (prev_nonnote_insn (head));
 320                        delete_insn (next);
 321                      }
 322                   insn = NULL;
 323                 }
 324             }
 325           else
 326             {
 327               BB_HEAD (curr_bb) = head;
 328               BB_END (curr_bb) = insn;
 329               add_missing_bbs (BB_HEAD (curr_bb), bb, curr_bb->prev_bb);
 330             }
 331           note = LABEL_P (head) ? NEXT_INSN (head) : head;
 332           NOTE_BASIC_BLOCK (note) = curr_bb;
 333           update_bb_for_insn (curr_bb);
 334           bb = curr_bb->next_bb;
 335           last_inside = NULL;
 336           if (!insn)
 337              break;
 338         }
 339     }
 340   add_missing_bbs (BB_HEAD (last->next_bb), bb, last);
 341   return bb->prev_bb;
 342 }
 343
 344 /* Returns the earliest block in EBB currently being processed where a
 345    "similar load" 'insn2' is found, and hence LOAD_INSN can move
 346    speculatively into the found block.  All the following must hold:
 347
 348    (1) both loads have 1 base register (PFREE_CANDIDATEs).
 349    (2) load_insn and load2 have a def-use dependence upon
 350    the same insn 'insn1'.
 351
 352    From all these we can conclude that the two loads access memory
 353    addresses that differ at most by a constant, and hence if moving
 354    load_insn would cause an exception, it would have been caused by
 355    load2 anyhow.
 356
 357    The function uses list (given by LAST_BLOCK) of already processed
 358    blocks in EBB.  The list is formed in `add_deps_for_risky_insns'.  */
 359
 360 static basic_block
 361 earliest_block_with_similiar_load (basic_block last_block, rtx load_insn)
 362 {
 363   rtx back_link;
 364   basic_block bb, earliest_block = NULL;
 365
 366   for (back_link = LOG_LINKS (load_insn);
 367        back_link;
 368        back_link = XEXP (back_link, 1))
 369     {
 370       rtx insn1 = XEXP (back_link, 0);
 371
 372       if (GET_MODE (back_link) == VOIDmode)
 373         {
 374           /* Found a DEF-USE dependence (insn1, load_insn).  */
 375           rtx fore_link;
 376
 377           for (fore_link = INSN_DEPEND (insn1);
 378                fore_link;
 379                fore_link = XEXP (fore_link, 1))
 380             {
 381               rtx insn2 = XEXP (fore_link, 0);
 382               basic_block insn2_block = BLOCK_FOR_INSN (insn2);
 383
 384               if (GET_MODE (fore_link) == VOIDmode)
 385                 {
 386                   if (earliest_block != NULL
 387                       && earliest_block->index < insn2_block->index)
 388                     continue;
 389
 390                   /* Found a DEF-USE dependence (insn1, insn2).  */
 391                   if (haifa_classify_insn (insn2) != PFREE_CANDIDATE)
 392                     /* insn2 not guaranteed to be a 1 base reg load.  */
 393                     continue;
 394
 395                   for (bb = last_block; bb; bb = bb->aux)
 396                     if (insn2_block == bb)
 397                       break;
 398
 399                   if (!bb)
 400                     /* insn2 is the similar load.  */
 401                     earliest_block = insn2_block;
 402                 }
 403             }
 404         }
 405     }
 406
 407   return earliest_block;
 408 }
 409
 410 /* The following function adds dependencies between jumps and risky
 411    insns in given ebb.  */
 412
 413 static void
 414 add_deps_for_risky_insns (rtx head, rtx tail)
 415 {
 416   rtx insn, prev;
 417   int class;
 418   rtx last_jump = NULL_RTX;
 419   rtx next_tail = NEXT_INSN (tail);
 420   basic_block last_block = NULL, bb;
 421
 422   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
 423     if (JUMP_P (insn))
 424       {
 425         bb = BLOCK_FOR_INSN (insn);
 426         bb->aux = last_block;
 427         last_block = bb;
 428         last_jump = insn;
 429       }
 430     else if (INSN_P (insn) && last_jump != NULL_RTX)
 431       {
 432         class = haifa_classify_insn (insn);
 433         prev = last_jump;
 434         switch (class)
 435           {
 436           case PFREE_CANDIDATE:
 437             if (flag_schedule_speculative_load)
 438               {
 439                 bb = earliest_block_with_similiar_load (last_block, insn);
 440                 if (bb)
 441                   {
 442                     bb = bb->aux;
 443                     if (!bb)
 444                       break;
 445                     prev = BB_END (bb);
 446                   }
 447               }
 448             /* Fall through.  */
 449           case TRAP_RISKY:
 450           case IRISKY:
 451           case PRISKY_CANDIDATE:
 452             /* ??? We could implement better checking PRISKY_CANDIDATEs
 453                analogous to sched-rgn.c.  */
 454             /* We can not change the mode of the backward
 455                dependency because REG_DEP_ANTI has the lowest
 456                rank.  */
 457             if (add_dependence (insn, prev, REG_DEP_ANTI))
 458               add_forward_dependence (prev, insn, REG_DEP_ANTI);
 459             break;
 460
 461           default:
 462             break;
 463           }
 464       }
 465   /* Maintain the invariant that bb->aux is clear after use.  */
 466   while (last_block)
 467     {
 468       bb = last_block->aux;
 469       last_block->aux = NULL;
 470       last_block = bb;
 471     }
 472 }
 473
 474 /* Schedule a single extended basic block, defined by the boundaries HEAD
 475    and TAIL.  */
 476
 477 static basic_block
 478 schedule_ebb (rtx head, rtx tail)
 479 {
 480   int n_insns;
 481   basic_block b;
 482   struct deps tmp_deps;
 483   basic_block first_bb = BLOCK_FOR_INSN (head);
 484   basic_block last_bb = BLOCK_FOR_INSN (tail);
 485
 486   if (no_real_insns_p (head, tail))
 487     return BLOCK_FOR_INSN (tail);
 488
 489   init_deps_global ();
 490
 491   /* Compute LOG_LINKS.  */
 492   init_deps (&tmp_deps);
 493   sched_analyze (&tmp_deps, head, tail);
 494   free_deps (&tmp_deps);
 495
 496   /* Compute INSN_DEPEND.  */
 497   compute_forward_dependences (head, tail);
 498
 499   add_deps_for_risky_insns (head, tail);
 500
 501   if (targetm.sched.dependencies_evaluation_hook)
 502     targetm.sched.dependencies_evaluation_hook (head, tail);
 503
 504   /* Set priorities.  */
 505   n_insns = set_priorities (head, tail);
 506
 507   current_sched_info->prev_head = PREV_INSN (head);
 508   current_sched_info->next_tail = NEXT_INSN (tail);
 509
 510   if (write_symbols != NO_DEBUG)
 511     {
 512       save_line_notes (first_bb->index, head, tail);
 513       rm_line_notes (head, tail);
 514     }
 515
 516   /* rm_other_notes only removes notes which are _inside_ the
 517      block---that is, it won't remove notes before the first real insn
 518      or after the last real insn of the block.  So if the first insn
 519      has a REG_SAVE_NOTE which would otherwise be emitted before the
 520      insn, it is redundant with the note before the start of the
 521      block, and so we have to take it out.  */
 522   if (INSN_P (head))
 523     {
 524       rtx note;
 525
 526       for (note = REG_NOTES (head); note; note = XEXP (note, 1))
 527         if (REG_NOTE_KIND (note) == REG_SAVE_NOTE)
 528           {
 529             remove_note (head, note);
 530             note = XEXP (note, 1);
 531             remove_note (head, note);
 532           }
 533     }
 534
 535   /* Remove remaining note insns from the block, save them in
 536      note_list.  These notes are restored at the end of
 537      schedule_block ().  */
 538   rm_other_notes (head, tail);
 539
 540   current_sched_info->queue_must_finish_empty = 1;
 541
 542   schedule_block (-1, n_insns);
 543
 544   /* Sanity check: verify that all region insns were scheduled.  */
 545   gcc_assert (sched_n_insns == n_insns);
 546   head = current_sched_info->head;
 547   tail = current_sched_info->tail;
 548
 549   if (write_symbols != NO_DEBUG)
 550     restore_line_notes (head, tail);
 551   b = fix_basic_block_boundaries (first_bb, last_bb, head, tail);
 552
 553   finish_deps_global ();
 554   return b;
 555 }
 556
 557 /* The one entry point in this file.  DUMP_FILE is the dump file for
 558    this pass.  */
 559
 560 void
 561 schedule_ebbs (FILE *dump_file)
 562 {
 563   basic_block bb;
 564   int probability_cutoff;
 565
 566   if (profile_info && flag_branch_probabilities)
 567     probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY_FEEDBACK);
 568   else
 569     probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY);
 570   probability_cutoff = REG_BR_PROB_BASE / 100 * probability_cutoff;
 571
 572   /* Taking care of this degenerate case makes the rest of
 573      this code simpler.  */
 574   if (n_basic_blocks == 0)
 575     return;
 576
 577   sched_init (dump_file);
 578
 579   current_sched_info = &ebb_sched_info;
 580
 581   compute_bb_for_insn ();
 582
 583   /* Schedule every region in the subroutine.  */
 584   FOR_EACH_BB (bb)
 585     {
 586       rtx head = BB_HEAD (bb);
 587       rtx tail;
 588
 589       for (;;)
 590         {
 591           edge e;
 592           edge_iterator ei;
 593           tail = BB_END (bb);
 594           if (bb->next_bb == EXIT_BLOCK_PTR
 595               || LABEL_P (BB_HEAD (bb->next_bb)))
 596             break;
 597           FOR_EACH_EDGE (e, ei, bb->succs)
 598             if ((e->flags & EDGE_FALLTHRU) != 0)
 599               break;
 600           if (! e)
 601             break;
 602           if (e->probability <= probability_cutoff)
 603             break;
 604           bb = bb->next_bb;
 605         }
 606
 607       /* Blah.  We should fix the rest of the code not to get confused by
 608          a note or two.  */
 609       while (head != tail)
 610         {
 611           if (NOTE_P (head))
 612             head = NEXT_INSN (head);
 613           else if (NOTE_P (tail))
 614             tail = PREV_INSN (tail);
 615           else if (LABEL_P (head))
 616             head = NEXT_INSN (head);
 617           else
 618             break;
 619         }
 620
 621       bb = schedule_ebb (head, tail);
 622     }
 623
 624   /* Updating life info can be done by local propagation over the modified
 625      superblocks.  */
 626
 627   /* Reposition the prologue and epilogue notes in case we moved the
 628      prologue/epilogue insns.  */
 629   if (reload_completed)
 630     reposition_prologue_and_epilogue_notes (get_insns ());
 631
 632   if (write_symbols != NO_DEBUG)
 633     rm_redundant_line_notes ();
 634
 635   sched_finish ();
 636 }