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