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