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 GNU CC.
   8
   9 GNU CC is free software; you can redistribute it and/or modify it
  10 under the terms of the GNU General Public License as published by the
  11 Free Software Foundation; either version 2, or (at your option) any
  12 later version.
  13
  14 GNU CC is distributed in the hope that it will be useful, but WITHOUT
  15 ANY 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 GNU CC; see the file COPYING.  If not, write to the Free
  21 the Free 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
 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
 241      FIXME: Probably the same thing should be done with REG_SAVE_NOTEs
 242      referencing NOTE_INSN_SETJMP at the end of the block.  */
 243   if (INSN_P (head))
 244     {
 245       rtx note;
 246
 247       for (note = REG_NOTES (head); note; note = XEXP (note, 1))
 248         if (REG_NOTE_KIND (note) == REG_SAVE_NOTE)
 249           {
 250             if (INTVAL (XEXP (note, 0)) != NOTE_INSN_SETJMP)
 251               {
 252                 remove_note (head, note);
 253                 note = XEXP (note, 1);
 254                 remove_note (head, note);
 255               }
 256             else
 257               note = XEXP (note, 1);
 258           }
 259     }
 260
 261   /* Remove remaining note insns from the block, save them in
 262      note_list.  These notes are restored at the end of
 263      schedule_block ().  */
 264   rm_other_notes (head, tail);
 265
 266   current_sched_info->queue_must_finish_empty = 1;
 267
 268   schedule_block (-1, n_insns);
 269
 270   /* Sanity check: verify that all region insns were scheduled.  */
 271   if (sched_n_insns != n_insns)
 272     abort ();
 273   head = current_sched_info->head;
 274   tail = current_sched_info->tail;
 275
 276   if (write_symbols != NO_DEBUG)
 277     restore_line_notes (head, tail);
 278
 279   finish_deps_global ();
 280 }
 281
 282 /* The one entry point in this file.  DUMP_FILE is the dump file for
 283    this pass.  */
 284
 285 void
 286 schedule_ebbs (dump_file)
 287      FILE *dump_file;
 288 {
 289   int i;
 290
 291   /* Taking care of this degenerate case makes the rest of
 292      this code simpler.  */
 293   if (n_basic_blocks == 0)
 294     return;
 295
 296   sched_init (dump_file);
 297
 298   current_sched_info = &ebb_sched_info;
 299
 300   allocate_reg_life_data ();
 301   compute_bb_for_insn (get_max_uid ());
 302
 303   /* Schedule every region in the subroutine.  */
 304   for (i = 0; i < n_basic_blocks; i++)
 305     {
 306       rtx head = BASIC_BLOCK (i)->head;
 307       rtx tail;
 308
 309       for (;;)
 310         {
 311           basic_block b = BASIC_BLOCK (i);
 312           edge e;
 313           tail = b->end;
 314           if (i + 1 == n_basic_blocks
 315               || GET_CODE (BLOCK_HEAD (i + 1)) == CODE_LABEL)
 316             break;
 317           for (e = b->succ; e; e = e->succ_next)
 318             if ((e->flags & EDGE_FALLTHRU) != 0)
 319               break;
 320           if (! e)
 321             break;
 322           if (GET_CODE (tail) == JUMP_INSN)
 323             {
 324               rtx x = find_reg_note (tail, REG_BR_PROB, 0);
 325               if (x)
 326                 {
 327                   int pred_val = INTVAL (XEXP (x, 0));
 328                   if (pred_val > REG_BR_PROB_BASE / 2)
 329                     break;
 330                 }
 331             }
 332
 333           i++;
 334         }
 335
 336       /* Blah.  We should fix the rest of the code not to get confused by
 337          a note or two.  */
 338       while (head != tail)
 339         {
 340           if (GET_CODE (head) == NOTE)
 341             head = NEXT_INSN (head);
 342           else if (GET_CODE (tail) == NOTE)
 343             tail = PREV_INSN (tail);
 344           else if (GET_CODE (head) == CODE_LABEL)
 345             head = NEXT_INSN (head);
 346           else
 347             break;
 348         }
 349
 350       schedule_ebb (head, tail);
 351     }
 352
 353   /* It doesn't make much sense to try and update life information here - we
 354      probably messed up even the flow graph.  */
 355
 356   /* Reposition the prologue and epilogue notes in case we moved the
 357      prologue/epilogue insns.  */
 358   if (reload_completed)
 359     reposition_prologue_and_epilogue_notes (get_insns ());
 360
 361   if (write_symbols != NO_DEBUG)
 362     rm_redundant_line_notes ();
 363
 364   sched_finish ();
 365 }