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 "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 "params.h"
  43 #include "sched-int.h"
  44 #include "target.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_operation (set, e->dest->global_live_at_start, cond_set,
 188                         BITMAP_AND);
 189     else
 190       bitmap_operation (used, used, e->dest->global_live_at_start,
 191                         BITMAP_IOR);
 192 }
 193
 194 /* Used in schedule_insns to initialize current_sched_info for scheduling
 195    regions (or single basic blocks).  */
 196
 197 static struct sched_info ebb_sched_info =
 198 {
 199   init_ready_list,
 200   can_schedule_ready_p,
 201   schedule_more_p,
 202   new_ready,
 203   rank,
 204   ebb_print_insn,
 205   contributes_to_priority,
 206   compute_jump_reg_dependencies,
 207
 208   NULL, NULL,
 209   NULL, NULL,
 210   0, 1, 0
 211 };
 212 \f
 213 /* It is possible that ebb scheduling eliminated some blocks.
 214    Place blocks from FIRST to LAST before BEFORE.  */
 215
 216 static void
 217 add_missing_bbs (rtx before, basic_block first, basic_block last)
 218 {
 219   for (; last != first->prev_bb; last = last->prev_bb)
 220     {
 221       before = emit_note_before (NOTE_INSN_BASIC_BLOCK, before);
 222       NOTE_BASIC_BLOCK (before) = last;
 223       BB_HEAD (last) = before;
 224       BB_END (last) = before;
 225       update_bb_for_insn (last);
 226     }
 227 }
 228
 229 /* Fixup the CFG after EBB scheduling.  Re-recognize the basic
 230    block boundaries in between HEAD and TAIL and update basic block
 231    structures between BB and LAST.  */
 232
 233 static basic_block
 234 fix_basic_block_boundaries (basic_block bb, basic_block last, rtx head,
 235                             rtx tail)
 236 {
 237   rtx insn = head;
 238   rtx last_inside = BB_HEAD (bb);
 239   rtx aftertail = NEXT_INSN (tail);
 240
 241   head = BB_HEAD (bb);
 242
 243   for (; insn != aftertail; insn = NEXT_INSN (insn))
 244     {
 245       gcc_assert (!LABEL_P (insn));
 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 (LABEL_P (insn))
 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 eliminated 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               edge_iterator ei;
 286
 287               /* An obscure special case, where we do have partially dead
 288                  instruction scheduled after last control flow instruction.
 289                  In this case we can create new basic block.  It is
 290                  always exactly one basic block last in the sequence.  Handle
 291                  it by splitting the edge and repositioning the block.
 292                  This is somewhat hackish, but at least avoid cut&paste
 293
 294                  A safer solution can be to bring the code into sequence,
 295                  do the split and re-emit it back in case this will ever
 296                  trigger problem.  */
 297
 298               FOR_EACH_EDGE (f, ei, bb->prev_bb->succs)
 299                 if (f->flags & EDGE_FALLTHRU)
 300                   break;
 301
 302               if (f)
 303                 {
 304                   last = curr_bb = split_edge (f);
 305                   h = BB_HEAD (curr_bb);
 306                   BB_HEAD (curr_bb) = head;
 307                   BB_END (curr_bb) = insn;
 308                   /* Edge splitting created misplaced BASIC_BLOCK note, kill
 309                      it.  */
 310                   delete_insn (h);
 311                 }
 312               /* It may happen that code got moved past unconditional jump in
 313                  case the code is completely dead.  Kill it.  */
 314               else
 315                 {
 316                   rtx next = next_nonnote_insn (insn);
 317                   delete_insn_chain (head, insn);
 318                   /* We keep some notes in the way that may split barrier from the
 319                      jump.  */
 320                   if (BARRIER_P (next))
 321                      {
 322                        emit_barrier_after (prev_nonnote_insn (head));
 323                        delete_insn (next);
 324                      }
 325                   insn = NULL;
 326                 }
 327             }
 328           else
 329             {
 330               BB_HEAD (curr_bb) = head;
 331               BB_END (curr_bb) = insn;
 332               add_missing_bbs (BB_HEAD (curr_bb), bb, curr_bb->prev_bb);
 333             }
 334           note = LABEL_P (head) ? NEXT_INSN (head) : head;
 335           NOTE_BASIC_BLOCK (note) = curr_bb;
 336           update_bb_for_insn (curr_bb);
 337           bb = curr_bb->next_bb;
 338           last_inside = NULL;
 339           if (!insn)
 340              break;
 341         }
 342     }
 343   add_missing_bbs (BB_HEAD (last->next_bb), bb, last);
 344   return bb->prev_bb;
 345 }
 346
 347 /* Returns the earliest block in EBB currently being processed where a
 348    "similar load" 'insn2' is found, and hence LOAD_INSN can move
 349    speculatively into the found block.  All the following must hold:
 350
 351    (1) both loads have 1 base register (PFREE_CANDIDATEs).
 352    (2) load_insn and load2 have a def-use dependence upon
 353    the same insn 'insn1'.
 354
 355    From all these we can conclude that the two loads access memory
 356    addresses that differ at most by a constant, and hence if moving
 357    load_insn would cause an exception, it would have been caused by
 358    load2 anyhow.
 359
 360    The function uses list (given by LAST_BLOCK) of already processed
 361    blocks in EBB.  The list is formed in `add_deps_for_risky_insns'.  */
 362
 363 static basic_block
 364 earliest_block_with_similiar_load (basic_block last_block, 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 dependencies between jumps and risky
 414    insns in given ebb.  */
 415
 416 static void
 417 add_deps_for_risky_insns (rtx head, rtx tail)
 418 {
 419   rtx insn, prev;
 420   int class;
 421   rtx last_jump = NULL_RTX;
 422   rtx next_tail = NEXT_INSN (tail);
 423   basic_block last_block = NULL, bb;
 424
 425   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
 426     if (JUMP_P (insn))
 427       {
 428         bb = BLOCK_FOR_INSN (insn);
 429         bb->aux = last_block;
 430         last_block = bb;
 431         last_jump = insn;
 432       }
 433     else if (INSN_P (insn) && last_jump != NULL_RTX)
 434       {
 435         class = haifa_classify_insn (insn);
 436         prev = last_jump;
 437         switch (class)
 438           {
 439           case PFREE_CANDIDATE:
 440             if (flag_schedule_speculative_load)
 441               {
 442                 bb = earliest_block_with_similiar_load (last_block, insn);
 443                 if (bb)
 444                   {
 445                     bb = bb->aux;
 446                     if (!bb)
 447                       break;
 448                     prev = BB_END (bb);
 449                   }
 450               }
 451             /* Fall through.  */
 452           case TRAP_RISKY:
 453           case IRISKY:
 454           case PRISKY_CANDIDATE:
 455             /* ??? We could implement better checking PRISKY_CANDIDATEs
 456                analogous to sched-rgn.c.  */
 457             /* We can not change the mode of the backward
 458                dependency because REG_DEP_ANTI has the lowest
 459                rank.  */
 460             if (add_dependence (insn, prev, REG_DEP_ANTI))
 461               add_forward_dependence (prev, insn, REG_DEP_ANTI);
 462             break;
 463
 464           default:
 465             break;
 466           }
 467       }
 468   /* Maintain the invariant that bb->aux is clear after use.  */
 469   while (last_block)
 470     {
 471       bb = last_block->aux;
 472       last_block->aux = NULL;
 473       last_block = bb;
 474     }
 475 }
 476
 477 /* Schedule a single extended basic block, defined by the boundaries HEAD
 478    and TAIL.  */
 479
 480 static basic_block
 481 schedule_ebb (rtx head, rtx tail)
 482 {
 483   int n_insns;
 484   basic_block b;
 485   struct deps tmp_deps;
 486   basic_block first_bb = BLOCK_FOR_INSN (head);
 487   basic_block last_bb = BLOCK_FOR_INSN (tail);
 488
 489   if (no_real_insns_p (head, tail))
 490     return BLOCK_FOR_INSN (tail);
 491
 492   init_deps_global ();
 493
 494   /* Compute LOG_LINKS.  */
 495   init_deps (&tmp_deps);
 496   sched_analyze (&tmp_deps, head, tail);
 497   free_deps (&tmp_deps);
 498
 499   /* Compute INSN_DEPEND.  */
 500   compute_forward_dependences (head, tail);
 501
 502   add_deps_for_risky_insns (head, tail);
 503
 504   if (targetm.sched.dependencies_evaluation_hook)
 505     targetm.sched.dependencies_evaluation_hook (head, tail);
 506
 507   /* Set priorities.  */
 508   n_insns = set_priorities (head, tail);
 509
 510   current_sched_info->prev_head = PREV_INSN (head);
 511   current_sched_info->next_tail = NEXT_INSN (tail);
 512
 513   if (write_symbols != NO_DEBUG)
 514     {
 515       save_line_notes (first_bb->index, head, tail);
 516       rm_line_notes (head, tail);
 517     }
 518
 519   /* rm_other_notes only removes notes which are _inside_ the
 520      block---that is, it won't remove notes before the first real insn
 521      or after the last real insn of the block.  So if the first insn
 522      has a REG_SAVE_NOTE which would otherwise be emitted before the
 523      insn, it is redundant with the note before the start of the
 524      block, and so we have to take it out.  */
 525   if (INSN_P (head))
 526     {
 527       rtx note;
 528
 529       for (note = REG_NOTES (head); note; note = XEXP (note, 1))
 530         if (REG_NOTE_KIND (note) == REG_SAVE_NOTE)
 531           {
 532             remove_note (head, note);
 533             note = XEXP (note, 1);
 534             remove_note (head, note);
 535           }
 536     }
 537
 538   /* Remove remaining note insns from the block, save them in
 539      note_list.  These notes are restored at the end of
 540      schedule_block ().  */
 541   rm_other_notes (head, tail);
 542
 543   current_sched_info->queue_must_finish_empty = 1;
 544
 545   schedule_block (-1, n_insns);
 546
 547   /* Sanity check: verify that all region insns were scheduled.  */
 548   gcc_assert (sched_n_insns == n_insns);
 549   head = current_sched_info->head;
 550   tail = current_sched_info->tail;
 551
 552   if (write_symbols != NO_DEBUG)
 553     restore_line_notes (head, tail);
 554   b = fix_basic_block_boundaries (first_bb, last_bb, head, tail);
 555
 556   finish_deps_global ();
 557   return b;
 558 }
 559
 560 /* The one entry point in this file.  DUMP_FILE is the dump file for
 561    this pass.  */
 562
 563 void
 564 schedule_ebbs (FILE *dump_file)
 565 {
 566   basic_block bb;
 567   int probability_cutoff;
 568
 569   if (profile_info && flag_branch_probabilities)
 570     probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY_FEEDBACK);
 571   else
 572     probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY);
 573   probability_cutoff = REG_BR_PROB_BASE / 100 * probability_cutoff;
 574
 575   /* Taking care of this degenerate case makes the rest of
 576      this code simpler.  */
 577   if (n_basic_blocks == 0)
 578     return;
 579
 580   sched_init (dump_file);
 581
 582   current_sched_info = &ebb_sched_info;
 583
 584   compute_bb_for_insn ();
 585
 586   /* Schedule every region in the subroutine.  */
 587   FOR_EACH_BB (bb)
 588     {
 589       rtx head = BB_HEAD (bb);
 590       rtx tail;
 591
 592       for (;;)
 593         {
 594           edge e;
 595           edge_iterator ei;
 596           tail = BB_END (bb);
 597           if (bb->next_bb == EXIT_BLOCK_PTR
 598               || LABEL_P (BB_HEAD (bb->next_bb)))
 599             break;
 600           FOR_EACH_EDGE (e, ei, bb->succs)
 601             if ((e->flags & EDGE_FALLTHRU) != 0)
 602               break;
 603           if (! e)
 604             break;
 605           if (e->probability <= probability_cutoff)
 606             break;
 607           bb = bb->next_bb;
 608         }
 609
 610       /* Blah.  We should fix the rest of the code not to get confused by
 611          a note or two.  */
 612       while (head != tail)
 613         {
 614           if (NOTE_P (head))
 615             head = NEXT_INSN (head);
 616           else if (NOTE_P (tail))
 617             tail = PREV_INSN (tail);
 618           else if (LABEL_P (head))
 619             head = NEXT_INSN (head);
 620           else
 621             break;
 622         }
 623
 624       bb = schedule_ebb (head, tail);
 625     }
 626
 627   /* Updating life info can be done by local propagation over the modified
 628      superblocks.  */
 629
 630   /* Reposition the prologue and epilogue notes in case we moved the
 631      prologue/epilogue insns.  */
 632   if (reload_completed)
 633     reposition_prologue_and_epilogue_notes (get_insns ());
 634
 635   if (write_symbols != NO_DEBUG)
 636     rm_redundant_line_notes ();
 637
 638   sched_finish ();
 639 }