/* Instruction scheduling pass.
Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
- 1999, 2000, 2001 Free Software Foundation, Inc.
+ 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
and currently maintained by, Jim Wilson (wilson@cygnus.com)
-This file is part of GNU CC.
+This file is part of GCC.
-GNU CC is free software; you can redistribute it and/or modify it
-under the terms of the GNU General Public License as published by the
-Free Software Foundation; either version 2, or (at your option) any
-later version.
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 2, or (at your option) any later
+version.
-GNU CC is distributed in the hope that it will be useful, but WITHOUT
-ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
for more details.
You should have received a copy of the GNU General Public License
-along with GNU CC; see the file COPYING. If not, write to the Free
-the Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+along with GCC; see the file COPYING. If not, write to the Free
+Software Foundation, 59 Temple Place - Suite 330, Boston, MA
02111-1307, USA. */
\f
#include "config.h"
#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
#include "toplev.h"
#include "rtl.h"
#include "tm_p.h"
#include "except.h"
#include "toplev.h"
#include "recog.h"
+#include "cfglayout.h"
#include "sched-int.h"
+#include "target.h"
\f
/* The number of insns to be scheduled in total. */
static int target_n_insns;
static int can_schedule_ready_p PARAMS ((rtx));
static int new_ready PARAMS ((rtx));
static int schedule_more_p PARAMS ((void));
-static const char *print_insn PARAMS ((rtx, int));
+static const char *ebb_print_insn PARAMS ((rtx, int));
static int rank PARAMS ((rtx, rtx));
static int contributes_to_priority PARAMS ((rtx, rtx));
static void compute_jump_reg_dependencies PARAMS ((rtx, regset));
-static void schedule_ebb PARAMS ((rtx, rtx));
+static basic_block schedule_ebb PARAMS ((rtx, rtx));
+static basic_block fix_basic_block_boundaries PARAMS ((basic_block, basic_block, rtx, rtx));
+static void add_missing_bbs PARAMS ((rtx, basic_block, basic_block));
/* Return nonzero if there are more insns that should be scheduled. */
Count number of insns in the target block being scheduled. */
for (insn = NEXT_INSN (prev_head); insn != next_tail; insn = NEXT_INSN (insn))
{
- rtx next;
-
- if (! INSN_P (insn))
- continue;
- next = NEXT_INSN (insn);
-
- if (INSN_DEP_COUNT (insn) == 0
- && (SCHED_GROUP_P (next) == 0 || ! INSN_P (next)))
+ if (INSN_DEP_COUNT (insn) == 0)
ready_add (ready, insn);
- if (!(SCHED_GROUP_P (insn)))
- target_n_insns++;
+ target_n_insns++;
}
}
to be formatted so that multiple output lines will line up nicely. */
static const char *
-print_insn (insn, aligned)
+ebb_print_insn (insn, aligned)
rtx insn;
int aligned ATTRIBUTE_UNUSED;
{
static int
rank (insn1, insn2)
- rtx insn1 ATTRIBUTE_UNUSED, insn2 ATTRIBUTE_UNUSED;
+ rtx insn1, insn2;
{
+ basic_block bb1 = BLOCK_FOR_INSN (insn1);
+ basic_block bb2 = BLOCK_FOR_INSN (insn2);
+
+ if (bb1->count > bb2->count
+ || bb1->frequency > bb2->frequency)
+ return -1;
+ if (bb1->count < bb2->count
+ || bb1->frequency < bb2->frequency)
+ return 1;
return 0;
}
schedule_more_p,
new_ready,
rank,
- print_insn,
+ ebb_print_insn,
contributes_to_priority,
compute_jump_reg_dependencies,
NULL, NULL,
NULL, NULL,
- 0
+ 0, 1
};
\f
+/* It is possible that ebb scheduling elliminated some blocks.
+ Place blocks from FIRST to LAST before BEFORE. */
+
+static void
+add_missing_bbs (before, first, last)
+ rtx before;
+ basic_block first, last;
+{
+ for (; last != first->prev_bb; last = last->prev_bb)
+ {
+ before = emit_note_before (NOTE_INSN_BASIC_BLOCK, before);
+ NOTE_BASIC_BLOCK (before) = last;
+ last->head = before;
+ last->end = before;
+ update_bb_for_insn (last);
+ }
+}
+
+/* Fixup the CFG after EBB scheduling. Re-recognize the basic
+ block boundaries in between HEAD and TAIL and update basic block
+ structures between BB and LAST. */
+
+static basic_block
+fix_basic_block_boundaries (bb, last, head, tail)
+ basic_block bb, last;
+ rtx head, tail;
+{
+ rtx insn = head;
+ rtx last_inside = bb->head;
+ rtx aftertail = NEXT_INSN (tail);
+
+ head = bb->head;
+
+ for (; insn != aftertail; insn = NEXT_INSN (insn))
+ {
+ if (GET_CODE (insn) == CODE_LABEL)
+ abort ();
+ /* Create new basic blocks just before first insn. */
+ if (inside_basic_block_p (insn))
+ {
+ if (!last_inside)
+ {
+ rtx note;
+
+ /* Re-emit the basic block note for newly found BB header. */
+ if (GET_CODE (insn) == CODE_LABEL)
+ {
+ note = emit_note_after (NOTE_INSN_BASIC_BLOCK, insn);
+ head = insn;
+ last_inside = note;
+ }
+ else
+ {
+ note = emit_note_before (NOTE_INSN_BASIC_BLOCK, insn);
+ head = note;
+ last_inside = insn;
+ }
+ }
+ else
+ last_inside = insn;
+ }
+ /* Control flow instruction terminate basic block. It is possible
+ that we've elliminated some basic blocks (made them empty).
+ Find the proper basic block using BLOCK_FOR_INSN and arrange things in
+ a sensible way by inserting empty basic blocks as needed. */
+ if (control_flow_insn_p (insn) || (insn == tail && last_inside))
+ {
+ basic_block curr_bb = BLOCK_FOR_INSN (insn);
+ rtx note;
+
+ if (!control_flow_insn_p (insn))
+ curr_bb = last;
+ if (bb == last->next_bb)
+ {
+ edge f;
+ rtx h;
+
+ /* An obscure special case, where we do have partially dead
+ instruction scheduled after last control flow instruction.
+ In this case we can create new basic block. It is
+ always exactly one basic block last in the sequence. Handle
+ it by splitting the edge and repositioning the block.
+ This is somewhat hackish, but at least avoid cut&paste
+
+ Safter sollution can be to bring the code into sequence,
+ do the split and re-emit it back in case this will ever
+ trigger problem. */
+ f = bb->prev_bb->succ;
+ while (f && !(f->flags & EDGE_FALLTHRU))
+ f = f->succ_next;
+
+ if (f)
+ {
+ last = curr_bb = split_edge (f);
+ h = curr_bb->head;
+ curr_bb->head = head;
+ curr_bb->end = insn;
+ /* Edge splitting created missplaced BASIC_BLOCK note, kill
+ it. */
+ delete_insn (h);
+ }
+ /* It may happen that code got moved past unconditional jump in
+ case the code is completely dead. Kill it. */
+ else
+ {
+ rtx next = next_nonnote_insn (insn);
+ delete_insn_chain (head, insn);
+ /* We keep some notes in the way that may split barrier from the
+ jump. */
+ if (GET_CODE (next) == BARRIER)
+ {
+ emit_barrier_after (prev_nonnote_insn (head));
+ delete_insn (next);
+ }
+ insn = NULL;
+ }
+ }
+ else
+ {
+ curr_bb->head = head;
+ curr_bb->end = insn;
+ add_missing_bbs (curr_bb->head, bb, curr_bb->prev_bb);
+ }
+ note = GET_CODE (head) == CODE_LABEL ? NEXT_INSN (head) : head;
+ NOTE_BASIC_BLOCK (note) = curr_bb;
+ update_bb_for_insn (curr_bb);
+ bb = curr_bb->next_bb;
+ last_inside = NULL;
+ if (!insn)
+ break;
+ }
+ }
+ add_missing_bbs (last->next_bb->head, bb, last);
+ return bb->prev_bb;
+}
+
/* Schedule a single extended basic block, defined by the boundaries HEAD
and TAIL. */
-static void
+static basic_block
schedule_ebb (head, tail)
rtx head, tail;
{
int n_insns;
+ basic_block b;
struct deps tmp_deps;
+ basic_block first_bb = BLOCK_FOR_INSN (head);
+ basic_block last_bb = BLOCK_FOR_INSN (tail);
if (no_real_insns_p (head, tail))
- return;
+ return BLOCK_FOR_INSN (tail);
init_deps_global ();
/* Compute INSN_DEPEND. */
compute_forward_dependences (head, tail);
+ if (targetm.sched.dependencies_evaluation_hook)
+ targetm.sched.dependencies_evaluation_hook (head, tail);
+
/* Set priorities. */
n_insns = set_priorities (head, tail);
if (write_symbols != NO_DEBUG)
restore_line_notes (head, tail);
+ b = fix_basic_block_boundaries (first_bb, last_bb, head, tail);
finish_deps_global ();
+ return b;
}
/* The one entry point in this file. DUMP_FILE is the dump file for
schedule_ebbs (dump_file)
FILE *dump_file;
{
- int i;
+ basic_block bb;
/* Taking care of this degenerate case makes the rest of
this code simpler. */
current_sched_info = &ebb_sched_info;
allocate_reg_life_data ();
- compute_bb_for_insn (get_max_uid ());
+ compute_bb_for_insn ();
/* Schedule every region in the subroutine. */
- for (i = 0; i < n_basic_blocks; i++)
- {
- rtx head = BASIC_BLOCK (i)->head;
+ FOR_EACH_BB (bb)
+ {
+ rtx head = bb->head;
rtx tail;
for (;;)
{
- basic_block b = BASIC_BLOCK (i);
edge e;
- tail = b->end;
- if (i + 1 == n_basic_blocks
- || GET_CODE (BLOCK_HEAD (i + 1)) == CODE_LABEL)
+ tail = bb->end;
+ if (bb->next_bb == EXIT_BLOCK_PTR
+ || GET_CODE (bb->next_bb->head) == CODE_LABEL)
break;
- for (e = b->succ; e; e = e->succ_next)
+ for (e = bb->succ; e; e = e->succ_next)
if ((e->flags & EDGE_FALLTHRU) != 0)
break;
if (! e)
break;
- if (GET_CODE (tail) == JUMP_INSN)
- {
- rtx x = find_reg_note (tail, REG_BR_PROB, 0);
- if (x)
- {
- int pred_val = INTVAL (XEXP (x, 0));
- if (pred_val > REG_BR_PROB_BASE / 2)
- break;
- }
- }
-
- i++;
+ if (e->probability < REG_BR_PROB_BASE / 2)
+ break;
+ bb = bb->next_bb;
}
/* Blah. We should fix the rest of the code not to get confused by
break;
}
- schedule_ebb (head, tail);
+ bb = schedule_ebb (head, tail);
}
- /* It doesn't make much sense to try and update life information here - we
- probably messed up even the flow graph. */
+ /* Updating life info can be done by local propagation over the modified
+ superblocks. */
/* Reposition the prologue and epilogue notes in case we moved the
prologue/epilogue insns. */