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 \f
  44 /* The number of insns to be scheduled in total.  */
  45 static int target_n_insns;
  46 /* The number of insns scheduled so far.  */
  47 static int sched_n_insns;
  48
  49 /* Implementations of the sched_info functions for region scheduling.  */
  50 static void init_ready_list PARAMS ((struct ready_list *));
  51 static int can_schedule_ready_p PARAMS ((rtx));
  52 static int new_ready PARAMS ((rtx));
  53 static int schedule_more_p PARAMS ((void));
  54 static const char *ebb_print_insn PARAMS ((rtx, int));
  55 static int rank PARAMS ((rtx, rtx));
  56 static int contributes_to_priority PARAMS ((rtx, rtx));
  57 static void compute_jump_reg_dependencies PARAMS ((rtx, regset));
  58 static void schedule_ebb PARAMS ((rtx, rtx));
  59
  60 /* Return nonzero if there are more insns that should be scheduled.  */
  61
  62 static int
  63 schedule_more_p ()
  64 {
  65   return sched_n_insns < target_n_insns;
  66 }
  67
  68 /* Add all insns that are initially ready to the ready list READY.  Called
  69    once before scheduling a set of insns.  */
  70
  71 static void
  72 init_ready_list (ready)
  73      struct ready_list *ready;
  74 {
  75   rtx prev_head = current_sched_info->prev_head;
  76   rtx next_tail = current_sched_info->next_tail;
  77   rtx insn;
  78
  79   target_n_insns = 0;
  80   sched_n_insns = 0;
  81
  82 #if 0
  83   /* Print debugging information.  */
  84   if (sched_verbose >= 5)
  85     debug_dependencies ();
  86 #endif
  87
  88   /* Initialize ready list with all 'ready' insns in target block.
  89      Count number of insns in the target block being scheduled.  */
  90   for (insn = NEXT_INSN (prev_head); insn != next_tail; insn = NEXT_INSN (insn))
  91     {
  92       rtx next;
  93
  94       if (! INSN_P (insn))
  95         continue;
  96       next = NEXT_INSN (insn);
  97
  98       if (INSN_DEP_COUNT (insn) == 0
  99           && (! INSN_P (next) || SCHED_GROUP_P (next) == 0))
 100         ready_add (ready, insn);
 101       if (!(SCHED_GROUP_P (insn)))
 102         target_n_insns++;
 103     }
 104 }
 105
 106 /* Called after taking INSN from the ready list.  Returns nonzero if this
 107    insn can be scheduled, nonzero if we should silently discard it.  */
 108
 109 static int
 110 can_schedule_ready_p (insn)
 111      rtx insn ATTRIBUTE_UNUSED;
 112 {
 113   sched_n_insns++;
 114   return 1;
 115 }
 116
 117 /* Called after INSN has all its dependencies resolved.  Return nonzero
 118    if it should be moved to the ready list or the queue, or zero if we
 119    should silently discard it.  */
 120 static int
 121 new_ready (next)
 122      rtx next ATTRIBUTE_UNUSED;
 123 {
 124   return 1;
 125 }
 126
 127 /* Return a string that contains the insn uid and optionally anything else
 128    necessary to identify this insn in an output.  It's valid to use a
 129    static buffer for this.  The ALIGNED parameter should cause the string
 130    to be formatted so that multiple output lines will line up nicely.  */
 131
 132 static const char *
 133 ebb_print_insn (insn, aligned)
 134      rtx insn;
 135      int aligned ATTRIBUTE_UNUSED;
 136 {
 137   static char tmp[80];
 138
 139   sprintf (tmp, "%4d", INSN_UID (insn));
 140   return tmp;
 141 }
 142
 143 /* Compare priority of two insns.  Return a positive number if the second
 144    insn is to be preferred for scheduling, and a negative one if the first
 145    is to be preferred.  Zero if they are equally good.  */
 146
 147 static int
 148 rank (insn1, insn2)
 149      rtx insn1 ATTRIBUTE_UNUSED, insn2 ATTRIBUTE_UNUSED;
 150 {
 151   return 0;
 152 }
 153
 154 /* NEXT is an instruction that depends on INSN (a backward dependence);
 155    return nonzero if we should include this dependence in priority
 156    calculations.  */
 157
 158 static int
 159 contributes_to_priority (next, insn)
 160      rtx next ATTRIBUTE_UNUSED, insn ATTRIBUTE_UNUSED;
 161 {
 162   return 1;
 163 }
 164
 165 /* INSN is a JUMP_INSN.  Store the set of registers that must be considered
 166    to be set by this jump in SET.  */
 167
 168 static void
 169 compute_jump_reg_dependencies (insn, set)
 170      rtx insn;
 171      regset set;
 172 {
 173   basic_block b = BLOCK_FOR_INSN (insn);
 174   edge e;
 175   for (e = b->succ; e; e = e->succ_next)
 176     if ((e->flags & EDGE_FALLTHRU) == 0)
 177       {
 178         bitmap_operation (set, set, e->dest->global_live_at_start,
 179                           BITMAP_IOR);
 180       }
 181 }
 182
 183 /* Used in schedule_insns to initialize current_sched_info for scheduling
 184    regions (or single basic blocks).  */
 185
 186 static struct sched_info ebb_sched_info =
 187 {
 188   init_ready_list,
 189   can_schedule_ready_p,
 190   schedule_more_p,
 191   new_ready,
 192   rank,
 193   ebb_print_insn,
 194   contributes_to_priority,
 195   compute_jump_reg_dependencies,
 196
 197   NULL, NULL,
 198   NULL, NULL,
 199   0, 1
 200 };
 201 \f
 202 /* Schedule a single extended basic block, defined by the boundaries HEAD
 203    and TAIL.  */
 204
 205 static void
 206 schedule_ebb (head, tail)
 207      rtx head, tail;
 208 {
 209   int n_insns;
 210   struct deps tmp_deps;
 211
 212   if (no_real_insns_p (head, tail))
 213     return;
 214
 215   init_deps_global ();
 216
 217   /* Compute LOG_LINKS.  */
 218   init_deps (&tmp_deps);
 219   sched_analyze (&tmp_deps, head, tail);
 220   free_deps (&tmp_deps);
 221
 222   /* Compute INSN_DEPEND.  */
 223   compute_forward_dependences (head, tail);
 224
 225   /* Set priorities.  */
 226   n_insns = set_priorities (head, tail);
 227
 228   current_sched_info->prev_head = PREV_INSN (head);
 229   current_sched_info->next_tail = NEXT_INSN (tail);
 230
 231   if (write_symbols != NO_DEBUG)
 232     {
 233       save_line_notes (0, head, tail);
 234       rm_line_notes (head, tail);
 235     }
 236
 237   /* rm_other_notes only removes notes which are _inside_ the
 238      block---that is, it won't remove notes before the first real insn
 239      or after the last real insn of the block.  So if the first insn
 240      has a REG_SAVE_NOTE which would otherwise be emitted before the
 241      insn, it is redundant with the note before the start of the
 242      block, and so we have to take it out.  */
 243   if (INSN_P (head))
 244     {
 245       rtx note;
 246
 247       for (note = REG_NOTES (head); note; note = XEXP (note, 1))
 248         if (REG_NOTE_KIND (note) == REG_SAVE_NOTE)
 249           {
 250             remove_note (head, note);
 251             note = XEXP (note, 1);
 252             remove_note (head, note);
 253           }
 254     }
 255
 256   /* Remove remaining note insns from the block, save them in
 257      note_list.  These notes are restored at the end of
 258      schedule_block ().  */
 259   rm_other_notes (head, tail);
 260
 261   current_sched_info->queue_must_finish_empty = 1;
 262
 263   schedule_block (-1, n_insns);
 264
 265   /* Sanity check: verify that all region insns were scheduled.  */
 266   if (sched_n_insns != n_insns)
 267     abort ();
 268   head = current_sched_info->head;
 269   tail = current_sched_info->tail;
 270
 271   if (write_symbols != NO_DEBUG)
 272     restore_line_notes (head, tail);
 273
 274   finish_deps_global ();
 275 }
 276
 277 /* The one entry point in this file.  DUMP_FILE is the dump file for
 278    this pass.  */
 279
 280 void
 281 schedule_ebbs (dump_file)
 282      FILE *dump_file;
 283 {
 284   basic_block bb;
 285
 286   /* Taking care of this degenerate case makes the rest of
 287      this code simpler.  */
 288   if (n_basic_blocks == 0)
 289     return;
 290
 291   sched_init (dump_file);
 292
 293   current_sched_info = &ebb_sched_info;
 294
 295   allocate_reg_life_data ();
 296   compute_bb_for_insn ();
 297
 298   /* Schedule every region in the subroutine.  */
 299   FOR_EACH_BB (bb)
 300     {
 301       rtx head = bb->head;
 302       rtx tail;
 303
 304       for (;;)
 305         {
 306           edge e;
 307           tail = bb->end;
 308           if (bb->next_bb == EXIT_BLOCK_PTR
 309               || GET_CODE (bb->next_bb->head) == CODE_LABEL)
 310             break;
 311           for (e = bb->succ; e; e = e->succ_next)
 312             if ((e->flags & EDGE_FALLTHRU) != 0)
 313               break;
 314           if (! e)
 315             break;
 316           if (GET_CODE (tail) == JUMP_INSN)
 317             {
 318               rtx x = find_reg_note (tail, REG_BR_PROB, 0);
 319               if (x)
 320                 {
 321                   int pred_val = INTVAL (XEXP (x, 0));
 322                   if (pred_val > REG_BR_PROB_BASE / 2)
 323                     break;
 324                 }
 325             }
 326
 327           bb = bb->next_bb;
 328         }
 329
 330       /* Blah.  We should fix the rest of the code not to get confused by
 331          a note or two.  */
 332       while (head != tail)
 333         {
 334           if (GET_CODE (head) == NOTE)
 335             head = NEXT_INSN (head);
 336           else if (GET_CODE (tail) == NOTE)
 337             tail = PREV_INSN (tail);
 338           else if (GET_CODE (head) == CODE_LABEL)
 339             head = NEXT_INSN (head);
 340           else
 341             break;
 342         }
 343
 344       schedule_ebb (head, tail);
 345     }
 346
 347   /* It doesn't make much sense to try and update life information here - we
 348      probably messed up even the flow graph.  */
 349
 350   /* Reposition the prologue and epilogue notes in case we moved the
 351      prologue/epilogue insns.  */
 352   if (reload_completed)
 353     reposition_prologue_and_epilogue_notes (get_insns ());
 354
 355   if (write_symbols != NO_DEBUG)
 356     rm_redundant_line_notes ();
 357
 358   sched_finish ();
 359 }