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       if (INSN_DEP_COUNT (insn) == 0)
  94         ready_add (ready, insn);
  95       if (!(SCHED_GROUP_P (insn)))
  96         target_n_insns++;
  97     }
  98 }
  99
 100 /* Called after taking INSN from the ready list.  Returns nonzero if this
 101    insn can be scheduled, nonzero if we should silently discard it.  */
 102
 103 static int
 104 can_schedule_ready_p (insn)
 105      rtx insn ATTRIBUTE_UNUSED;
 106 {
 107   sched_n_insns++;
 108   return 1;
 109 }
 110
 111 /* Called after INSN has all its dependencies resolved.  Return nonzero
 112    if it should be moved to the ready list or the queue, or zero if we
 113    should silently discard it.  */
 114 static int
 115 new_ready (next)
 116      rtx next ATTRIBUTE_UNUSED;
 117 {
 118   return 1;
 119 }
 120
 121 /* Return a string that contains the insn uid and optionally anything else
 122    necessary to identify this insn in an output.  It's valid to use a
 123    static buffer for this.  The ALIGNED parameter should cause the string
 124    to be formatted so that multiple output lines will line up nicely.  */
 125
 126 static const char *
 127 ebb_print_insn (insn, aligned)
 128      rtx insn;
 129      int aligned ATTRIBUTE_UNUSED;
 130 {
 131   static char tmp[80];
 132
 133   sprintf (tmp, "%4d", INSN_UID (insn));
 134   return tmp;
 135 }
 136
 137 /* Compare priority of two insns.  Return a positive number if the second
 138    insn is to be preferred for scheduling, and a negative one if the first
 139    is to be preferred.  Zero if they are equally good.  */
 140
 141 static int
 142 rank (insn1, insn2)
 143      rtx insn1 ATTRIBUTE_UNUSED, insn2 ATTRIBUTE_UNUSED;
 144 {
 145   return 0;
 146 }
 147
 148 /* NEXT is an instruction that depends on INSN (a backward dependence);
 149    return nonzero if we should include this dependence in priority
 150    calculations.  */
 151
 152 static int
 153 contributes_to_priority (next, insn)
 154      rtx next ATTRIBUTE_UNUSED, insn ATTRIBUTE_UNUSED;
 155 {
 156   return 1;
 157 }
 158
 159 /* INSN is a JUMP_INSN.  Store the set of registers that must be considered
 160    to be set by this jump in SET.  */
 161
 162 static void
 163 compute_jump_reg_dependencies (insn, set)
 164      rtx insn;
 165      regset set;
 166 {
 167   basic_block b = BLOCK_FOR_INSN (insn);
 168   edge e;
 169   for (e = b->succ; e; e = e->succ_next)
 170     if ((e->flags & EDGE_FALLTHRU) == 0)
 171       {
 172         bitmap_operation (set, set, e->dest->global_live_at_start,
 173                           BITMAP_IOR);
 174       }
 175 }
 176
 177 /* Used in schedule_insns to initialize current_sched_info for scheduling
 178    regions (or single basic blocks).  */
 179
 180 static struct sched_info ebb_sched_info =
 181 {
 182   init_ready_list,
 183   can_schedule_ready_p,
 184   schedule_more_p,
 185   new_ready,
 186   rank,
 187   ebb_print_insn,
 188   contributes_to_priority,
 189   compute_jump_reg_dependencies,
 190
 191   NULL, NULL,
 192   NULL, NULL,
 193   0, 1
 194 };
 195 \f
 196 /* Schedule a single extended basic block, defined by the boundaries HEAD
 197    and TAIL.  */
 198
 199 static void
 200 schedule_ebb (head, tail)
 201      rtx head, tail;
 202 {
 203   int n_insns;
 204   struct deps tmp_deps;
 205
 206   if (no_real_insns_p (head, tail))
 207     return;
 208
 209   init_deps_global ();
 210
 211   /* Compute LOG_LINKS.  */
 212   init_deps (&tmp_deps);
 213   sched_analyze (&tmp_deps, head, tail);
 214   free_deps (&tmp_deps);
 215
 216   /* Compute INSN_DEPEND.  */
 217   compute_forward_dependences (head, tail);
 218
 219   if (targetm.sched.dependencies_evaluation_hook)
 220     targetm.sched.dependencies_evaluation_hook (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   basic_block bb;
 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 ();
 294
 295   /* Schedule every region in the subroutine.  */
 296   FOR_EACH_BB (bb)
 297     {
 298       rtx head = bb->head;
 299       rtx tail;
 300
 301       for (;;)
 302         {
 303           edge e;
 304           tail = bb->end;
 305           if (bb->next_bb == EXIT_BLOCK_PTR
 306               || GET_CODE (bb->next_bb->head) == CODE_LABEL)
 307             break;
 308           for (e = bb->succ; e; e = e->succ_next)
 309             if ((e->flags & EDGE_FALLTHRU) != 0)
 310               break;
 311           if (! e)
 312             break;
 313           if (GET_CODE (tail) == JUMP_INSN)
 314             {
 315               rtx x = find_reg_note (tail, REG_BR_PROB, 0);
 316               if (x)
 317                 {
 318                   int pred_val = INTVAL (XEXP (x, 0));
 319                   if (pred_val > REG_BR_PROB_BASE / 2)
 320                     break;
 321                 }
 322             }
 323
 324           bb = bb->next_bb;
 325         }
 326
 327       /* Blah.  We should fix the rest of the code not to get confused by
 328          a note or two.  */
 329       while (head != tail)
 330         {
 331           if (GET_CODE (head) == NOTE)
 332             head = NEXT_INSN (head);
 333           else if (GET_CODE (tail) == NOTE)
 334             tail = PREV_INSN (tail);
 335           else if (GET_CODE (head) == CODE_LABEL)
 336             head = NEXT_INSN (head);
 337           else
 338             break;
 339         }
 340
 341       schedule_ebb (head, tail);
 342     }
 343
 344   /* It doesn't make much sense to try and update life information here - we
 345      probably messed up even the flow graph.  */
 346
 347   /* Reposition the prologue and epilogue notes in case we moved the
 348      prologue/epilogue insns.  */
 349   if (reload_completed)
 350     reposition_prologue_and_epilogue_notes (get_insns ());
 351
 352   if (write_symbols != NO_DEBUG)
 353     rm_redundant_line_notes ();
 354
 355   sched_finish ();
 356 }