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