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   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 (control_flow_insn_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 (! sched_insns_conditions_mutex_p (insn, prev))
 461               {
 462                 if (!(current_sched_info->flags & DO_SPECULATION))
 463                   {
 464                     enum DEPS_ADJUST_RESULT res;
 465
 466                     res = add_or_update_back_dep (insn, prev,
 467                                                   REG_DEP_ANTI, DEP_ANTI);
 468
 469                     if (res == DEP_CREATED)
 470                       add_forw_dep (insn, LOG_LINKS (insn));
 471                     else
 472                       gcc_assert (res != DEP_CHANGED);
 473                   }
 474                 else
 475                   add_or_update_back_forw_dep (insn, prev, REG_DEP_ANTI,
 476                                                set_dep_weak (DEP_ANTI,
 477                                                              BEGIN_CONTROL,
 478                                                              MAX_DEP_WEAK));
 479               }
 480
 481             break;
 482
 483           default:
 484             break;
 485           }
 486       }
 487   /* Maintain the invariant that bb->aux is clear after use.  */
 488   while (last_block)
 489     {
 490       bb = last_block->aux;
 491       last_block->aux = NULL;
 492       last_block = bb;
 493     }
 494 }
 495
 496 /* Schedule a single extended basic block, defined by the boundaries HEAD
 497    and TAIL.  */
 498
 499 static basic_block
 500 schedule_ebb (rtx head, rtx tail)
 501 {
 502   int n_insns;
 503   basic_block b;
 504   struct deps tmp_deps;
 505   basic_block first_bb = BLOCK_FOR_INSN (head);
 506   basic_block last_bb = BLOCK_FOR_INSN (tail);
 507
 508   if (no_real_insns_p (head, tail))
 509     return BLOCK_FOR_INSN (tail);
 510
 511   init_deps_global ();
 512
 513   /* Compute LOG_LINKS.  */
 514   init_deps (&tmp_deps);
 515   sched_analyze (&tmp_deps, head, tail);
 516   free_deps (&tmp_deps);
 517
 518   /* Compute INSN_DEPEND.  */
 519   compute_forward_dependences (head, tail);
 520
 521   add_deps_for_risky_insns (head, tail);
 522
 523   if (targetm.sched.dependencies_evaluation_hook)
 524     targetm.sched.dependencies_evaluation_hook (head, tail);
 525
 526   /* Set priorities.  */
 527   n_insns = set_priorities (head, tail);
 528
 529   current_sched_info->prev_head = PREV_INSN (head);
 530   current_sched_info->next_tail = NEXT_INSN (tail);
 531
 532   if (write_symbols != NO_DEBUG)
 533     {
 534       save_line_notes (first_bb->index, head, tail);
 535       rm_line_notes (head, tail);
 536     }
 537
 538   /* rm_other_notes only removes notes which are _inside_ the
 539      block---that is, it won't remove notes before the first real insn
 540      or after the last real insn of the block.  So if the first insn
 541      has a REG_SAVE_NOTE which would otherwise be emitted before the
 542      insn, it is redundant with the note before the start of the
 543      block, and so we have to take it out.  */
 544   if (INSN_P (head))
 545     {
 546       rtx note;
 547
 548       for (note = REG_NOTES (head); note; note = XEXP (note, 1))
 549         if (REG_NOTE_KIND (note) == REG_SAVE_NOTE)
 550           remove_note (head, note);
 551     }
 552
 553   /* Remove remaining note insns from the block, save them in
 554      note_list.  These notes are restored at the end of
 555      schedule_block ().  */
 556   rm_other_notes (head, tail);
 557
 558   current_sched_info->queue_must_finish_empty = 1;
 559
 560   schedule_block (-1, n_insns);
 561
 562   /* Sanity check: verify that all region insns were scheduled.  */
 563   gcc_assert (sched_n_insns == n_insns);
 564   head = current_sched_info->head;
 565   tail = current_sched_info->tail;
 566
 567   if (write_symbols != NO_DEBUG)
 568     restore_line_notes (head, tail);
 569   b = fix_basic_block_boundaries (first_bb, last_bb, head, tail);
 570
 571   finish_deps_global ();
 572   return b;
 573 }
 574
 575 /* The one entry point in this file.  */
 576
 577 void
 578 schedule_ebbs (void)
 579 {
 580   basic_block bb;
 581   int probability_cutoff;
 582
 583   if (profile_info && flag_branch_probabilities)
 584     probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY_FEEDBACK);
 585   else
 586     probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY);
 587   probability_cutoff = REG_BR_PROB_BASE / 100 * probability_cutoff;
 588
 589   /* Taking care of this degenerate case makes the rest of
 590      this code simpler.  */
 591   if (n_basic_blocks == NUM_FIXED_BLOCKS)
 592     return;
 593
 594   /* We need current_sched_info in init_dependency_caches, which is
 595      invoked via sched_init.  */
 596   current_sched_info = &ebb_sched_info;
 597
 598   sched_init ();
 599
 600   compute_bb_for_insn ();
 601
 602   /* Schedule every region in the subroutine.  */
 603   FOR_EACH_BB (bb)
 604     {
 605       rtx head = BB_HEAD (bb);
 606       rtx tail;
 607
 608       for (;;)
 609         {
 610           edge e;
 611           edge_iterator ei;
 612           tail = BB_END (bb);
 613           if (bb->next_bb == EXIT_BLOCK_PTR
 614               || LABEL_P (BB_HEAD (bb->next_bb)))
 615             break;
 616           FOR_EACH_EDGE (e, ei, bb->succs)
 617             if ((e->flags & EDGE_FALLTHRU) != 0)
 618               break;
 619           if (! e)
 620             break;
 621           if (e->probability <= probability_cutoff)
 622             break;
 623           bb = bb->next_bb;
 624         }
 625
 626       /* Blah.  We should fix the rest of the code not to get confused by
 627          a note or two.  */
 628       while (head != tail)
 629         {
 630           if (NOTE_P (head))
 631             head = NEXT_INSN (head);
 632           else if (NOTE_P (tail))
 633             tail = PREV_INSN (tail);
 634           else if (LABEL_P (head))
 635             head = NEXT_INSN (head);
 636           else
 637             break;
 638         }
 639
 640       bb = schedule_ebb (head, tail);
 641     }
 642
 643   /* Updating life info can be done by local propagation over the modified
 644      superblocks.  */
 645
 646   /* Reposition the prologue and epilogue notes in case we moved the
 647      prologue/epilogue insns.  */
 648   if (reload_completed)
 649     reposition_prologue_and_epilogue_notes (get_insns ());
 650
 651   if (write_symbols != NO_DEBUG)
 652     rm_redundant_line_notes ();
 653
 654   sched_finish ();
 655 }