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   int i;
 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   scope_to_insns_initialize ();
 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 (get_max_uid ());
 297
 298   /* Schedule every region in the subroutine.  */
 299   for (i = 0; i < n_basic_blocks; i++)
 300     {
 301       rtx head = BASIC_BLOCK (i)->head;
 302       rtx tail;
 303
 304       for (;;)
 305         {
 306           basic_block b = BASIC_BLOCK (i);
 307           edge e;
 308           tail = b->end;
 309           if (i + 1 == n_basic_blocks
 310               || GET_CODE (BLOCK_HEAD (i + 1)) == CODE_LABEL)
 311             break;
 312           for (e = b->succ; e; e = e->succ_next)
 313             if ((e->flags & EDGE_FALLTHRU) != 0)
 314               break;
 315           if (! e)
 316             break;
 317           if (GET_CODE (tail) == JUMP_INSN)
 318             {
 319               rtx x = find_reg_note (tail, REG_BR_PROB, 0);
 320               if (x)
 321                 {
 322                   int pred_val = INTVAL (XEXP (x, 0));
 323                   if (pred_val > REG_BR_PROB_BASE / 2)
 324                     break;
 325                 }
 326             }
 327
 328           i++;
 329         }
 330
 331       /* Blah.  We should fix the rest of the code not to get confused by
 332          a note or two.  */
 333       while (head != tail)
 334         {
 335           if (GET_CODE (head) == NOTE)
 336             head = NEXT_INSN (head);
 337           else if (GET_CODE (tail) == NOTE)
 338             tail = PREV_INSN (tail);
 339           else if (GET_CODE (head) == CODE_LABEL)
 340             head = NEXT_INSN (head);
 341           else
 342             break;
 343         }
 344
 345       schedule_ebb (head, tail);
 346     }
 347
 348   /* It doesn't make much sense to try and update life information here - we
 349      probably messed up even the flow graph.  */
 350
 351   /* Reposition the prologue and epilogue notes in case we moved the
 352      prologue/epilogue insns.  */
 353   if (reload_completed)
 354     reposition_prologue_and_epilogue_notes (get_insns ());
 355
 356   if (write_symbols != NO_DEBUG)
 357     rm_redundant_line_notes ();
 358
 359   scope_to_insns_finalize ();
 360
 361   sched_finish ();
 362 }