gcc/sched-ebb.c

   1 /* Instruction scheduling pass.
   2    Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
   3    1999, 2000, 2001, 2002 Free Software Foundation, Inc.
   4    Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
   5    and currently maintained by, Jim Wilson (wilson@cygnus.com)
   6
   7 This file is part of GCC.
   8
   9 GCC is free software; you can redistribute it and/or modify it under
  10 the terms of the GNU General Public License as published by the Free
  11 Software Foundation; either version 2, or (at your option) any later
  12 version.
  13
  14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  16 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  17 for more details.
  18
  19 You should have received a copy of the GNU General Public License
  20 along with GCC; see the file COPYING.  If not, write to the Free
  21 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  22 02111-1307, USA.  */
  23 \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 PARAMS ((struct ready_list *));
  52 static int can_schedule_ready_p PARAMS ((rtx));
  53 static int new_ready PARAMS ((rtx));
  54 static int schedule_more_p PARAMS ((void));
  55 static const char *ebb_print_insn PARAMS ((rtx, int));
  56 static int rank PARAMS ((rtx, rtx));
  57 static int contributes_to_priority PARAMS ((rtx, rtx));
  58 static void compute_jump_reg_dependencies PARAMS ((rtx, regset));
  59 static basic_block earliest_block_with_similiar_load PARAMS ((basic_block,
  60                                                               rtx));
  61 static void add_deps_for_risky_insns PARAMS ((rtx, rtx));
  62 static basic_block schedule_ebb PARAMS ((rtx, rtx));
  63 static basic_block fix_basic_block_boundaries PARAMS ((basic_block, basic_block, rtx, rtx));
  64 static void add_missing_bbs PARAMS ((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 ()
  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 (ready)
  79      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 (insn)
 109      rtx insn ATTRIBUTE_UNUSED;
 110 {
 111   sched_n_insns++;
 112   return 1;
 113 }
 114
 115 /* Called after INSN has all its dependencies resolved.  Return nonzero
 116    if it should be moved to the ready list or the queue, or zero if we
 117    should silently discard it.  */
 118 static int
 119 new_ready (next)
 120      rtx next ATTRIBUTE_UNUSED;
 121 {
 122   return 1;
 123 }
 124
 125 /* Return a string that contains the insn uid and optionally anything else
 126    necessary to identify this insn in an output.  It's valid to use a
 127    static buffer for this.  The ALIGNED parameter should cause the string
 128    to be formatted so that multiple output lines will line up nicely.  */
 129
 130 static const char *
 131 ebb_print_insn (insn, aligned)
 132      rtx insn;
 133      int aligned ATTRIBUTE_UNUSED;
 134 {
 135   static char tmp[80];
 136
 137   sprintf (tmp, "%4d", INSN_UID (insn));
 138   return tmp;
 139 }
 140
 141 /* Compare priority of two insns.  Return a positive number if the second
 142    insn is to be preferred for scheduling, and a negative one if the first
 143    is to be preferred.  Zero if they are equally good.  */
 144
 145 static int
 146 rank (insn1, insn2)
 147      rtx insn1, insn2;
 148 {
 149   basic_block bb1 = BLOCK_FOR_INSN (insn1);
 150   basic_block bb2 = BLOCK_FOR_INSN (insn2);
 151
 152   if (bb1->count > bb2->count
 153       || bb1->frequency > bb2->frequency)
 154     return -1;
 155   if (bb1->count < bb2->count
 156       || bb1->frequency < bb2->frequency)
 157     return 1;
 158   return 0;
 159 }
 160
 161 /* NEXT is an instruction that depends on INSN (a backward dependence);
 162    return nonzero if we should include this dependence in priority
 163    calculations.  */
 164
 165 static int
 166 contributes_to_priority (next, insn)
 167      rtx next ATTRIBUTE_UNUSED, insn ATTRIBUTE_UNUSED;
 168 {
 169   return 1;
 170 }
 171
 172 /* INSN is a JUMP_INSN.  Store the set of registers that must be considered
 173    to be set by this jump in SET.  */
 174
 175 static void
 176 compute_jump_reg_dependencies (insn, set)
 177      rtx insn;
 178      regset set;
 179 {
 180   basic_block b = BLOCK_FOR_INSN (insn);
 181   edge e;
 182   for (e = b->succ; e; e = e->succ_next)
 183     if ((e->flags & EDGE_FALLTHRU) == 0)
 184       {
 185         bitmap_operation (set, set, e->dest->global_live_at_start,
 186                           BITMAP_IOR);
 187       }
 188 }
 189
 190 /* Used in schedule_insns to initialize current_sched_info for scheduling
 191    regions (or single basic blocks).  */
 192
 193 static struct sched_info ebb_sched_info =
 194 {
 195   init_ready_list,
 196   can_schedule_ready_p,
 197   schedule_more_p,
 198   new_ready,
 199   rank,
 200   ebb_print_insn,
 201   contributes_to_priority,
 202   compute_jump_reg_dependencies,
 203
 204   NULL, NULL,
 205   NULL, NULL,
 206   0, 1
 207 };
 208 \f
 209 /* It is possible that ebb scheduling elliminated some blocks.
 210    Place blocks from FIRST to LAST before BEFORE.  */
 211
 212 static void
 213 add_missing_bbs (before, first, last)
 214      rtx before;
 215      basic_block first, 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       last->head = before;
 222       last->end = 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 (bb, last, head, tail)
 233      basic_block bb, last;
 234      rtx head, tail;
 235 {
 236   rtx insn = head;
 237   rtx last_inside = bb->head;
 238   rtx aftertail = NEXT_INSN (tail);
 239
 240   head = bb->head;
 241
 242   for (; insn != aftertail; insn = NEXT_INSN (insn))
 243     {
 244       if (GET_CODE (insn) == CODE_LABEL)
 245         abort ();
 246       /* Create new basic blocks just before first insn.  */
 247       if (inside_basic_block_p (insn))
 248         {
 249           if (!last_inside)
 250             {
 251               rtx note;
 252
 253               /* Re-emit the basic block note for newly found BB header.  */
 254               if (GET_CODE (insn) == CODE_LABEL)
 255                 {
 256                   note = emit_note_after (NOTE_INSN_BASIC_BLOCK, insn);
 257                   head = insn;
 258                   last_inside = note;
 259                 }
 260               else
 261                 {
 262                   note = emit_note_before (NOTE_INSN_BASIC_BLOCK, insn);
 263                   head = note;
 264                   last_inside = insn;
 265                 }
 266             }
 267           else
 268             last_inside = insn;
 269         }
 270       /* Control flow instruction terminate basic block.  It is possible
 271          that we've elliminated some basic blocks (made them empty).
 272          Find the proper basic block using BLOCK_FOR_INSN and arrange things in
 273          a sensible way by inserting empty basic blocks as needed.  */
 274       if (control_flow_insn_p (insn) || (insn == tail && last_inside))
 275         {
 276           basic_block curr_bb = BLOCK_FOR_INSN (insn);
 277           rtx note;
 278
 279           if (!control_flow_insn_p (insn))
 280             curr_bb = last;
 281           if (bb == last->next_bb)
 282             {
 283               edge f;
 284               rtx h;
 285
 286               /* An obscure special case, where we do have partially dead
 287                  instruction scheduled after last control flow instruction.
 288                  In this case we can create new basic block.  It is
 289                  always exactly one basic block last in the sequence.  Handle
 290                  it by splitting the edge and repositioning the block.
 291                  This is somewhat hackish, but at least avoid cut&paste
 292
 293                  Safter sollution can be to bring the code into sequence,
 294                  do the split and re-emit it back in case this will ever
 295                  trigger problem.  */
 296               f = bb->prev_bb->succ;
 297               while (f && !(f->flags & EDGE_FALLTHRU))
 298                 f = f->succ_next;
 299
 300               if (f)
 301                 {
 302                   last = curr_bb = split_edge (f);
 303                   h = curr_bb->head;
 304                   curr_bb->head = head;
 305                   curr_bb->end = insn;
 306                   /* Edge splitting created missplaced 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 (GET_CODE (next) == BARRIER)
 319                      {
 320                        emit_barrier_after (prev_nonnote_insn (head));
 321                        delete_insn (next);
 322                      }
 323                   insn = NULL;
 324                 }
 325             }
 326           else
 327             {
 328               curr_bb->head = head;
 329               curr_bb->end = insn;
 330               add_missing_bbs (curr_bb->head, bb, curr_bb->prev_bb);
 331             }
 332           note = GET_CODE (head) == CODE_LABEL ? 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 (last->next_bb->head, 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 (last_block, load_insn)
 363      basic_block last_block;
 364      rtx load_insn;
 365 {
 366   rtx back_link;
 367   basic_block bb, earliest_block = NULL;
 368
 369   for (back_link = LOG_LINKS (load_insn);
 370        back_link;
 371        back_link = XEXP (back_link, 1))
 372     {
 373       rtx insn1 = XEXP (back_link, 0);
 374
 375       if (GET_MODE (back_link) == VOIDmode)
 376         {
 377           /* Found a DEF-USE dependence (insn1, load_insn).  */
 378           rtx fore_link;
 379
 380           for (fore_link = INSN_DEPEND (insn1);
 381                fore_link;
 382                fore_link = XEXP (fore_link, 1))
 383             {
 384               rtx insn2 = XEXP (fore_link, 0);
 385               basic_block insn2_block = BLOCK_FOR_INSN (insn2);
 386
 387               if (GET_MODE (fore_link) == VOIDmode)
 388                 {
 389                   if (earliest_block != NULL
 390                       && earliest_block->index < insn2_block->index)
 391                     continue;
 392
 393                   /* Found a DEF-USE dependence (insn1, insn2).  */
 394                   if (haifa_classify_insn (insn2) != PFREE_CANDIDATE)
 395                     /* insn2 not guaranteed to be a 1 base reg load.  */
 396                     continue;
 397
 398                   for (bb = last_block; bb; bb = bb->aux)
 399                     if (insn2_block == bb)
 400                       break;
 401
 402                   if (!bb)
 403                     /* insn2 is the similar load.  */
 404                     earliest_block = insn2_block;
 405                 }
 406             }
 407         }
 408     }
 409
 410   return earliest_block;
 411 }
 412
 413 /* The following function adds dependecies between jumps and risky
 414    insns in given ebb.  */
 415
 416 static void
 417 add_deps_for_risky_insns (head, tail)
 418      rtx head, tail;
 419 {
 420   rtx insn, prev;
 421   int class;
 422   rtx last_jump = NULL_RTX;
 423   rtx next_tail = NEXT_INSN (tail);
 424   basic_block last_block = NULL, bb;
 425
 426   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
 427     if (GET_CODE (insn) == JUMP_INSN)
 428       {
 429         bb = BLOCK_FOR_INSN (insn);
 430         bb->aux = last_block;
 431         last_block = bb;
 432         last_jump = insn;
 433       }
 434     else if (INSN_P (insn) && last_jump != NULL_RTX)
 435       {
 436         class = haifa_classify_insn (insn);
 437         prev = last_jump;
 438         switch (class)
 439           {
 440           case PFREE_CANDIDATE:
 441             if (flag_schedule_speculative_load)
 442               {
 443                 bb = earliest_block_with_similiar_load (last_block, insn);
 444                 if (bb)
 445                   {
 446                     bb = bb->aux;
 447                     if (!bb)
 448                       break;
 449                     prev = bb->end;
 450                   }
 451               }
 452             /* FALLTHRU */
 453           case TRAP_RISKY:
 454           case IRISKY:
 455           case PRISKY_CANDIDATE:
 456             /* ??? We could implement better checking PRISKY_CANDIATEs
 457                analogous to sched-rgn.c.  */
 458             /* We can not change the mode of the backward
 459                dependency because REG_DEP_ANTI has the lowest
 460                rank.  */
 461             if (add_dependence (insn, prev, REG_DEP_ANTI))
 462               add_forward_dependence (prev, insn, REG_DEP_ANTI);
 463             break;
 464
 465           default:
 466             break;
 467           }
 468       }
 469   /* Maintain the invariant that bb->aux is clear after use.  */
 470   while (last_block)
 471     {
 472       bb = last_block->aux;
 473       last_block->aux = NULL;
 474       last_block = bb;
 475     }
 476 }
 477
 478 /* Schedule a single extended basic block, defined by the boundaries HEAD
 479    and TAIL.  */
 480
 481 static basic_block
 482 schedule_ebb (head, tail)
 483      rtx head, tail;
 484 {
 485   int n_insns;
 486   basic_block b;
 487   struct deps tmp_deps;
 488   basic_block first_bb = BLOCK_FOR_INSN (head);
 489   basic_block last_bb = BLOCK_FOR_INSN (tail);
 490
 491   if (no_real_insns_p (head, tail))
 492     return BLOCK_FOR_INSN (tail);
 493
 494   init_deps_global ();
 495
 496   /* Compute LOG_LINKS.  */
 497   init_deps (&tmp_deps);
 498   sched_analyze (&tmp_deps, head, tail);
 499   free_deps (&tmp_deps);
 500
 501   /* Compute INSN_DEPEND.  */
 502   compute_forward_dependences (head, tail);
 503
 504   add_deps_for_risky_insns (head, tail);
 505
 506   if (targetm.sched.dependencies_evaluation_hook)
 507     targetm.sched.dependencies_evaluation_hook (head, tail);
 508
 509   /* Set priorities.  */
 510   n_insns = set_priorities (head, tail);
 511
 512   current_sched_info->prev_head = PREV_INSN (head);
 513   current_sched_info->next_tail = NEXT_INSN (tail);
 514
 515   if (write_symbols != NO_DEBUG)
 516     {
 517       save_line_notes (0, head, tail);
 518       rm_line_notes (head, tail);
 519     }
 520
 521   /* rm_other_notes only removes notes which are _inside_ the
 522      block---that is, it won't remove notes before the first real insn
 523      or after the last real insn of the block.  So if the first insn
 524      has a REG_SAVE_NOTE which would otherwise be emitted before the
 525      insn, it is redundant with the note before the start of the
 526      block, and so we have to take it out.  */
 527   if (INSN_P (head))
 528     {
 529       rtx note;
 530
 531       for (note = REG_NOTES (head); note; note = XEXP (note, 1))
 532         if (REG_NOTE_KIND (note) == REG_SAVE_NOTE)
 533           {
 534             remove_note (head, note);
 535             note = XEXP (note, 1);
 536             remove_note (head, note);
 537           }
 538     }
 539
 540   /* Remove remaining note insns from the block, save them in
 541      note_list.  These notes are restored at the end of
 542      schedule_block ().  */
 543   rm_other_notes (head, tail);
 544
 545   current_sched_info->queue_must_finish_empty = 1;
 546
 547   schedule_block (-1, n_insns);
 548
 549   /* Sanity check: verify that all region insns were scheduled.  */
 550   if (sched_n_insns != n_insns)
 551     abort ();
 552   head = current_sched_info->head;
 553   tail = current_sched_info->tail;
 554
 555   if (write_symbols != NO_DEBUG)
 556     restore_line_notes (head, tail);
 557   b = fix_basic_block_boundaries (first_bb, last_bb, head, tail);
 558
 559   finish_deps_global ();
 560   return b;
 561 }
 562
 563 /* The one entry point in this file.  DUMP_FILE is the dump file for
 564    this pass.  */
 565
 566 void
 567 schedule_ebbs (dump_file)
 568      FILE *dump_file;
 569 {
 570   basic_block bb;
 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   allocate_reg_life_data ();
 582   compute_bb_for_insn ();
 583
 584   /* Schedule every region in the subroutine.  */
 585   FOR_EACH_BB (bb)
 586     {
 587       rtx head = bb->head;
 588       rtx tail;
 589
 590       for (;;)
 591         {
 592           edge e;
 593           tail = bb->end;
 594           if (bb->next_bb == EXIT_BLOCK_PTR
 595               || GET_CODE (bb->next_bb->head) == CODE_LABEL)
 596             break;
 597           for (e = bb->succ; e; e = e->succ_next)
 598             if ((e->flags & EDGE_FALLTHRU) != 0)
 599               break;
 600           if (! e)
 601             break;
 602           if (e->probability < REG_BR_PROB_BASE / 2)
 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 (GET_CODE (head) == NOTE)
 612             head = NEXT_INSN (head);
 613           else if (GET_CODE (tail) == NOTE)
 614             tail = PREV_INSN (tail);
 615           else if (GET_CODE (head) == CODE_LABEL)
 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 }