gcc/sched-ebb.c

   1 /* Instruction scheduling pass.
   2    Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
   3    1999, 2000, 2001, 2002, 2003 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 "basic-block.h"
  33 #include "regs.h"
  34 #include "function.h"
  35 #include "flags.h"
  36 #include "insn-config.h"
  37 #include "insn-attr.h"
  38 #include "except.h"
  39 #include "toplev.h"
  40 #include "recog.h"
  41 #include "cfglayout.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);
  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.  Store the set of registers that must be considered
 167    to be set by this jump in SET.  */
 168
 169 static void
 170 compute_jump_reg_dependencies (rtx insn, regset set)
 171 {
 172   basic_block b = BLOCK_FOR_INSN (insn);
 173   edge e;
 174   for (e = b->succ; e; e = e->succ_next)
 175     if ((e->flags & EDGE_FALLTHRU) == 0)
 176       {
 177         bitmap_operation (set, set, e->dest->global_live_at_start,
 178                           BITMAP_IOR);
 179       }
 180 }
 181
 182 /* Used in schedule_insns to initialize current_sched_info for scheduling
 183    regions (or single basic blocks).  */
 184
 185 static struct sched_info ebb_sched_info =
 186 {
 187   init_ready_list,
 188   can_schedule_ready_p,
 189   schedule_more_p,
 190   new_ready,
 191   rank,
 192   ebb_print_insn,
 193   contributes_to_priority,
 194   compute_jump_reg_dependencies,
 195
 196   NULL, NULL,
 197   NULL, NULL,
 198   0, 1
 199 };
 200 \f
 201 /* It is possible that ebb scheduling eliminated some blocks.
 202    Place blocks from FIRST to LAST before BEFORE.  */
 203
 204 static void
 205 add_missing_bbs (rtx before, basic_block first, basic_block last)
 206 {
 207   for (; last != first->prev_bb; last = last->prev_bb)
 208     {
 209       before = emit_note_before (NOTE_INSN_BASIC_BLOCK, before);
 210       NOTE_BASIC_BLOCK (before) = last;
 211       last->head = before;
 212       last->end = before;
 213       update_bb_for_insn (last);
 214     }
 215 }
 216
 217 /* Fixup the CFG after EBB scheduling.  Re-recognize the basic
 218    block boundaries in between HEAD and TAIL and update basic block
 219    structures between BB and LAST.  */
 220
 221 static basic_block
 222 fix_basic_block_boundaries (basic_block bb, basic_block last, rtx head,
 223                             rtx tail)
 224 {
 225   rtx insn = head;
 226   rtx last_inside = bb->head;
 227   rtx aftertail = NEXT_INSN (tail);
 228
 229   head = bb->head;
 230
 231   for (; insn != aftertail; insn = NEXT_INSN (insn))
 232     {
 233       if (GET_CODE (insn) == CODE_LABEL)
 234         abort ();
 235       /* Create new basic blocks just before first insn.  */
 236       if (inside_basic_block_p (insn))
 237         {
 238           if (!last_inside)
 239             {
 240               rtx note;
 241
 242               /* Re-emit the basic block note for newly found BB header.  */
 243               if (GET_CODE (insn) == CODE_LABEL)
 244                 {
 245                   note = emit_note_after (NOTE_INSN_BASIC_BLOCK, insn);
 246                   head = insn;
 247                   last_inside = note;
 248                 }
 249               else
 250                 {
 251                   note = emit_note_before (NOTE_INSN_BASIC_BLOCK, insn);
 252                   head = note;
 253                   last_inside = insn;
 254                 }
 255             }
 256           else
 257             last_inside = insn;
 258         }
 259       /* Control flow instruction terminate basic block.  It is possible
 260          that we've eliminated some basic blocks (made them empty).
 261          Find the proper basic block using BLOCK_FOR_INSN and arrange things in
 262          a sensible way by inserting empty basic blocks as needed.  */
 263       if (control_flow_insn_p (insn) || (insn == tail && last_inside))
 264         {
 265           basic_block curr_bb = BLOCK_FOR_INSN (insn);
 266           rtx note;
 267
 268           if (!control_flow_insn_p (insn))
 269             curr_bb = last;
 270           if (bb == last->next_bb)
 271             {
 272               edge f;
 273               rtx h;
 274
 275               /* An obscure special case, where we do have partially dead
 276                  instruction scheduled after last control flow instruction.
 277                  In this case we can create new basic block.  It is
 278                  always exactly one basic block last in the sequence.  Handle
 279                  it by splitting the edge and repositioning the block.
 280                  This is somewhat hackish, but at least avoid cut&paste
 281
 282                  A safer solution can be to bring the code into sequence,
 283                  do the split and re-emit it back in case this will ever
 284                  trigger problem.  */
 285               f = bb->prev_bb->succ;
 286               while (f && !(f->flags & EDGE_FALLTHRU))
 287                 f = f->succ_next;
 288
 289               if (f)
 290                 {
 291                   last = curr_bb = split_edge (f);
 292                   h = curr_bb->head;
 293                   curr_bb->head = head;
 294                   curr_bb->end = insn;
 295                   /* Edge splitting created misplaced BASIC_BLOCK note, kill
 296                      it.  */
 297                   delete_insn (h);
 298                 }
 299               /* It may happen that code got moved past unconditional jump in
 300                  case the code is completely dead.  Kill it.  */
 301               else
 302                 {
 303                   rtx next = next_nonnote_insn (insn);
 304                   delete_insn_chain (head, insn);
 305                   /* We keep some notes in the way that may split barrier from the
 306                      jump.  */
 307                   if (GET_CODE (next) == BARRIER)
 308                      {
 309                        emit_barrier_after (prev_nonnote_insn (head));
 310                        delete_insn (next);
 311                      }
 312                   insn = NULL;
 313                 }
 314             }
 315           else
 316             {
 317               curr_bb->head = head;
 318               curr_bb->end = insn;
 319               add_missing_bbs (curr_bb->head, bb, curr_bb->prev_bb);
 320             }
 321           note = GET_CODE (head) == CODE_LABEL ? NEXT_INSN (head) : head;
 322           NOTE_BASIC_BLOCK (note) = curr_bb;
 323           update_bb_for_insn (curr_bb);
 324           bb = curr_bb->next_bb;
 325           last_inside = NULL;
 326           if (!insn)
 327              break;
 328         }
 329     }
 330   add_missing_bbs (last->next_bb->head, bb, last);
 331   return bb->prev_bb;
 332 }
 333
 334 /* Returns the earliest block in EBB currently being processed where a
 335    "similar load" 'insn2' is found, and hence LOAD_INSN can move
 336    speculatively into the found block.  All the following must hold:
 337
 338    (1) both loads have 1 base register (PFREE_CANDIDATEs).
 339    (2) load_insn and load2 have a def-use dependence upon
 340    the same insn 'insn1'.
 341
 342    From all these we can conclude that the two loads access memory
 343    addresses that differ at most by a constant, and hence if moving
 344    load_insn would cause an exception, it would have been caused by
 345    load2 anyhow.
 346
 347    The function uses list (given by LAST_BLOCK) of already processed
 348    blocks in EBB.  The list is formed in `add_deps_for_risky_insns'.  */
 349
 350 static basic_block
 351 earliest_block_with_similiar_load (basic_block last_block, rtx load_insn)
 352 {
 353   rtx back_link;
 354   basic_block bb, earliest_block = NULL;
 355
 356   for (back_link = LOG_LINKS (load_insn);
 357        back_link;
 358        back_link = XEXP (back_link, 1))
 359     {
 360       rtx insn1 = XEXP (back_link, 0);
 361
 362       if (GET_MODE (back_link) == VOIDmode)
 363         {
 364           /* Found a DEF-USE dependence (insn1, load_insn).  */
 365           rtx fore_link;
 366
 367           for (fore_link = INSN_DEPEND (insn1);
 368                fore_link;
 369                fore_link = XEXP (fore_link, 1))
 370             {
 371               rtx insn2 = XEXP (fore_link, 0);
 372               basic_block insn2_block = BLOCK_FOR_INSN (insn2);
 373
 374               if (GET_MODE (fore_link) == VOIDmode)
 375                 {
 376                   if (earliest_block != NULL
 377                       && earliest_block->index < insn2_block->index)
 378                     continue;
 379
 380                   /* Found a DEF-USE dependence (insn1, insn2).  */
 381                   if (haifa_classify_insn (insn2) != PFREE_CANDIDATE)
 382                     /* insn2 not guaranteed to be a 1 base reg load.  */
 383                     continue;
 384
 385                   for (bb = last_block; bb; bb = bb->aux)
 386                     if (insn2_block == bb)
 387                       break;
 388
 389                   if (!bb)
 390                     /* insn2 is the similar load.  */
 391                     earliest_block = insn2_block;
 392                 }
 393             }
 394         }
 395     }
 396
 397   return earliest_block;
 398 }
 399
 400 /* The following function adds dependencies between jumps and risky
 401    insns in given ebb.  */
 402
 403 static void
 404 add_deps_for_risky_insns (rtx head, rtx tail)
 405 {
 406   rtx insn, prev;
 407   int class;
 408   rtx last_jump = NULL_RTX;
 409   rtx next_tail = NEXT_INSN (tail);
 410   basic_block last_block = NULL, bb;
 411
 412   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
 413     if (GET_CODE (insn) == JUMP_INSN)
 414       {
 415         bb = BLOCK_FOR_INSN (insn);
 416         bb->aux = last_block;
 417         last_block = bb;
 418         last_jump = insn;
 419       }
 420     else if (INSN_P (insn) && last_jump != NULL_RTX)
 421       {
 422         class = haifa_classify_insn (insn);
 423         prev = last_jump;
 424         switch (class)
 425           {
 426           case PFREE_CANDIDATE:
 427             if (flag_schedule_speculative_load)
 428               {
 429                 bb = earliest_block_with_similiar_load (last_block, insn);
 430                 if (bb)
 431                   {
 432                     bb = bb->aux;
 433                     if (!bb)
 434                       break;
 435                     prev = bb->end;
 436                   }
 437               }
 438             /* FALLTHRU */
 439           case TRAP_RISKY:
 440           case IRISKY:
 441           case PRISKY_CANDIDATE:
 442             /* ??? We could implement better checking PRISKY_CANDIDATEs
 443                analogous to sched-rgn.c.  */
 444             /* We can not change the mode of the backward
 445                dependency because REG_DEP_ANTI has the lowest
 446                rank.  */
 447             if (add_dependence (insn, prev, REG_DEP_ANTI))
 448               add_forward_dependence (prev, insn, REG_DEP_ANTI);
 449             break;
 450
 451           default:
 452             break;
 453           }
 454       }
 455   /* Maintain the invariant that bb->aux is clear after use.  */
 456   while (last_block)
 457     {
 458       bb = last_block->aux;
 459       last_block->aux = NULL;
 460       last_block = bb;
 461     }
 462 }
 463
 464 /* Schedule a single extended basic block, defined by the boundaries HEAD
 465    and TAIL.  */
 466
 467 static basic_block
 468 schedule_ebb (rtx head, rtx tail)
 469 {
 470   int n_insns;
 471   basic_block b;
 472   struct deps tmp_deps;
 473   basic_block first_bb = BLOCK_FOR_INSN (head);
 474   basic_block last_bb = BLOCK_FOR_INSN (tail);
 475
 476   if (no_real_insns_p (head, tail))
 477     return BLOCK_FOR_INSN (tail);
 478
 479   init_deps_global ();
 480
 481   /* Compute LOG_LINKS.  */
 482   init_deps (&tmp_deps);
 483   sched_analyze (&tmp_deps, head, tail);
 484   free_deps (&tmp_deps);
 485
 486   /* Compute INSN_DEPEND.  */
 487   compute_forward_dependences (head, tail);
 488
 489   add_deps_for_risky_insns (head, tail);
 490
 491   if (targetm.sched.dependencies_evaluation_hook)
 492     targetm.sched.dependencies_evaluation_hook (head, tail);
 493
 494   /* Set priorities.  */
 495   n_insns = set_priorities (head, tail);
 496
 497   current_sched_info->prev_head = PREV_INSN (head);
 498   current_sched_info->next_tail = NEXT_INSN (tail);
 499
 500   if (write_symbols != NO_DEBUG)
 501     {
 502       save_line_notes (first_bb->index, head, tail);
 503       rm_line_notes (head, tail);
 504     }
 505
 506   /* rm_other_notes only removes notes which are _inside_ the
 507      block---that is, it won't remove notes before the first real insn
 508      or after the last real insn of the block.  So if the first insn
 509      has a REG_SAVE_NOTE which would otherwise be emitted before the
 510      insn, it is redundant with the note before the start of the
 511      block, and so we have to take it out.  */
 512   if (INSN_P (head))
 513     {
 514       rtx note;
 515
 516       for (note = REG_NOTES (head); note; note = XEXP (note, 1))
 517         if (REG_NOTE_KIND (note) == REG_SAVE_NOTE)
 518           {
 519             remove_note (head, note);
 520             note = XEXP (note, 1);
 521             remove_note (head, note);
 522           }
 523     }
 524
 525   /* Remove remaining note insns from the block, save them in
 526      note_list.  These notes are restored at the end of
 527      schedule_block ().  */
 528   rm_other_notes (head, tail);
 529
 530   current_sched_info->queue_must_finish_empty = 1;
 531
 532   schedule_block (-1, n_insns);
 533
 534   /* Sanity check: verify that all region insns were scheduled.  */
 535   if (sched_n_insns != n_insns)
 536     abort ();
 537   head = current_sched_info->head;
 538   tail = current_sched_info->tail;
 539
 540   if (write_symbols != NO_DEBUG)
 541     restore_line_notes (head, tail);
 542   b = fix_basic_block_boundaries (first_bb, last_bb, head, tail);
 543
 544   finish_deps_global ();
 545   return b;
 546 }
 547
 548 /* The one entry point in this file.  DUMP_FILE is the dump file for
 549    this pass.  */
 550
 551 void
 552 schedule_ebbs (FILE *dump_file)
 553 {
 554   basic_block bb;
 555
 556   /* Taking care of this degenerate case makes the rest of
 557      this code simpler.  */
 558   if (n_basic_blocks == 0)
 559     return;
 560
 561   sched_init (dump_file);
 562
 563   current_sched_info = &ebb_sched_info;
 564
 565   allocate_reg_life_data ();
 566   compute_bb_for_insn ();
 567
 568   /* Schedule every region in the subroutine.  */
 569   FOR_EACH_BB (bb)
 570     {
 571       rtx head = bb->head;
 572       rtx tail;
 573
 574       for (;;)
 575         {
 576           edge e;
 577           tail = bb->end;
 578           if (bb->next_bb == EXIT_BLOCK_PTR
 579               || GET_CODE (bb->next_bb->head) == CODE_LABEL)
 580             break;
 581           for (e = bb->succ; e; e = e->succ_next)
 582             if ((e->flags & EDGE_FALLTHRU) != 0)
 583               break;
 584           if (! e)
 585             break;
 586           if (e->probability < REG_BR_PROB_BASE / 2)
 587             break;
 588           bb = bb->next_bb;
 589         }
 590
 591       /* Blah.  We should fix the rest of the code not to get confused by
 592          a note or two.  */
 593       while (head != tail)
 594         {
 595           if (GET_CODE (head) == NOTE)
 596             head = NEXT_INSN (head);
 597           else if (GET_CODE (tail) == NOTE)
 598             tail = PREV_INSN (tail);
 599           else if (GET_CODE (head) == CODE_LABEL)
 600             head = NEXT_INSN (head);
 601           else
 602             break;
 603         }
 604
 605       bb = schedule_ebb (head, tail);
 606     }
 607
 608   /* Updating life info can be done by local propagation over the modified
 609      superblocks.  */
 610
 611   /* Reposition the prologue and epilogue notes in case we moved the
 612      prologue/epilogue insns.  */
 613   if (reload_completed)
 614     reposition_prologue_and_epilogue_notes (get_insns ());
 615
 616   if (write_symbols != NO_DEBUG)
 617     rm_redundant_line_notes ();
 618
 619   sched_finish ();
 620 }