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