gcc/sched-ebb.c

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