/* Instruction scheduling pass.
Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
- 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007
+ 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008
Free Software Foundation, Inc.
Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
and currently maintained by, Jim Wilson (wilson@cygnus.com)
#include "output.h"
\f
-/* The number of insns scheduled so far. */
-static int sched_n_insns;
+#ifdef INSN_SCHEDULING
/* The number of insns to be scheduled in total. */
-static int n_insns;
+static int rgn_n_insns;
+
+/* The number of insns scheduled so far. */
+static int sched_rgn_n_insns;
/* Set of blocks, that already have their dependencies calculated. */
static bitmap_head dont_calc_deps;
static void init_ready_list (void);
static void begin_schedule_ready (rtx, rtx);
static int schedule_more_p (void);
-static const char *ebb_print_insn (rtx, int);
+static const char *ebb_print_insn (const_rtx, int);
static int rank (rtx, rtx);
-static int contributes_to_priority (rtx, rtx);
-static void compute_jump_reg_dependencies (rtx, regset, regset, regset);
+static int ebb_contributes_to_priority (rtx, rtx);
static basic_block earliest_block_with_similiar_load (basic_block, rtx);
static void add_deps_for_risky_insns (rtx, rtx);
static basic_block schedule_ebb (rtx, rtx);
+static void debug_ebb_dependencies (rtx, rtx);
-static void add_remove_insn (rtx, int);
-static void add_block1 (basic_block, basic_block);
+static void ebb_add_remove_insn (rtx, int);
+static void ebb_add_block (basic_block, basic_block);
static basic_block advance_target_bb (basic_block, rtx);
-static void fix_recovery_cfg (int, int, int);
+static void ebb_fix_recovery_cfg (int, int, int);
/* Return nonzero if there are more insns that should be scheduled. */
static int
schedule_more_p (void)
{
- return sched_n_insns < n_insns;
+ return sched_rgn_n_insns < rgn_n_insns;
}
/* Print dependency information about ebb between HEAD and TAIL. */
rtx next_tail = current_sched_info->next_tail;
rtx insn;
- sched_n_insns = 0;
+ sched_rgn_n_insns = 0;
/* Print debugging information. */
if (sched_verbose >= 5)
n++;
}
- gcc_assert (n == n_insns);
+ gcc_assert (n == rgn_n_insns);
}
/* INSN is being scheduled after LAST. Update counters. */
static void
begin_schedule_ready (rtx insn, rtx last)
{
- sched_n_insns++;
+ sched_rgn_n_insns++;
if (BLOCK_FOR_INSN (insn) == last_bb
/* INSN is a jump in the last block, ... */
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. */
-
+
FOR_EACH_EDGE (e, ei, last_bb->succs)
if (e->flags & EDGE_FALLTHRU)
break;
#ifdef ENABLE_CHECKING
- gcc_assert (!e || !(e->flags & EDGE_COMPLEX));
+ gcc_assert (!e || !(e->flags & EDGE_COMPLEX));
gcc_assert (BLOCK_FOR_INSN (insn) == last_bb
&& !IS_SPECULATION_CHECK_P (insn)
else
/* Create an empty unreachable block after the INSN. */
bb = create_basic_block (NEXT_INSN (insn), NULL_RTX, last_bb);
-
+
/* split_edge () creates BB before E->DEST. Keep in mind, that
this operation extends scheduling region till the end of BB.
Hence, we need to shift NEXT_TAIL, so haifa-sched.c won't go out
current_sched_info->next_tail = NEXT_INSN (BB_END (bb));
gcc_assert (current_sched_info->next_tail);
- add_block (bb, last_bb);
+ /* Append new basic block to the end of the ebb. */
+ sched_init_only_bb (bb, last_bb);
gcc_assert (last_bb == bb);
}
}
to be formatted so that multiple output lines will line up nicely. */
static const char *
-ebb_print_insn (rtx insn, int aligned ATTRIBUTE_UNUSED)
+ebb_print_insn (const_rtx insn, int aligned ATTRIBUTE_UNUSED)
{
static char tmp[80];
- sprintf (tmp, "%4d", INSN_UID (insn));
+ /* '+' before insn means it is a new cycle start. */
+ if (GET_MODE (insn) == TImode)
+ sprintf (tmp, "+ %4d", INSN_UID (insn));
+ else
+ sprintf (tmp, " %4d", INSN_UID (insn));
+
return tmp;
}
calculations. */
static int
-contributes_to_priority (rtx next ATTRIBUTE_UNUSED,
- rtx insn ATTRIBUTE_UNUSED)
+ebb_contributes_to_priority (rtx next ATTRIBUTE_UNUSED,
+ rtx insn ATTRIBUTE_UNUSED)
{
return 1;
}
must be considered as used by this jump in USED and that of
registers that must be considered as set in SET. */
-static void
-compute_jump_reg_dependencies (rtx insn, regset cond_set, regset used,
- regset set)
+void
+ebb_compute_jump_reg_dependencies (rtx insn, regset cond_set, regset used,
+ regset set)
{
basic_block b = BLOCK_FOR_INSN (insn);
edge e;
/* Used in schedule_insns to initialize current_sched_info for scheduling
regions (or single basic blocks). */
-static struct sched_info ebb_sched_info =
+static struct common_sched_info_def ebb_common_sched_info;
+
+static struct sched_deps_info_def ebb_sched_deps_info =
+ {
+ ebb_compute_jump_reg_dependencies,
+ NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
+ NULL,
+ 1, 0, 0
+ };
+
+static struct haifa_sched_info ebb_sched_info =
{
init_ready_list,
NULL,
NULL,
rank,
ebb_print_insn,
- contributes_to_priority,
- compute_jump_reg_dependencies,
+ ebb_contributes_to_priority,
+ NULL, /* insn_finishes_block_p */
NULL, NULL,
NULL, NULL,
- 0, 1, 0,
+ 1, 0,
- add_remove_insn,
+ ebb_add_remove_insn,
begin_schedule_ready,
- add_block1,
advance_target_bb,
- fix_recovery_cfg,
SCHED_EBB
/* We can create new blocks in begin_schedule_ready (). */
| NEW_BBS
static basic_block
earliest_block_with_similiar_load (basic_block last_block, rtx load_insn)
{
- dep_link_t back_link;
+ sd_iterator_def back_sd_it;
+ dep_t back_dep;
basic_block bb, earliest_block = NULL;
- FOR_EACH_DEP_LINK (back_link, INSN_BACK_DEPS (load_insn))
+ FOR_EACH_DEP (load_insn, SD_LIST_BACK, back_sd_it, back_dep)
{
- rtx insn1 = DEP_LINK_PRO (back_link);
+ rtx insn1 = DEP_PRO (back_dep);
- if (DEP_LINK_KIND (back_link) == REG_DEP_TRUE)
+ if (DEP_TYPE (back_dep) == REG_DEP_TRUE)
+ /* Found a DEF-USE dependence (insn1, load_insn). */
{
- /* Found a DEF-USE dependence (insn1, load_insn). */
- dep_link_t fore_link;
+ sd_iterator_def fore_sd_it;
+ dep_t fore_dep;
- FOR_EACH_DEP_LINK (fore_link, INSN_FORW_DEPS (insn1))
+ FOR_EACH_DEP (insn1, SD_LIST_FORW, fore_sd_it, fore_dep)
{
- rtx insn2 = DEP_LINK_CON (fore_link);
+ rtx insn2 = DEP_CON (fore_dep);
basic_block insn2_block = BLOCK_FOR_INSN (insn2);
- if (DEP_LINK_KIND (fore_link) == REG_DEP_TRUE)
+ if (DEP_TYPE (fore_dep) == REG_DEP_TRUE)
{
if (earliest_block != NULL
&& earliest_block->index < insn2_block->index)
/* insn2 not guaranteed to be a 1 base reg load. */
continue;
- for (bb = last_block; bb; bb = bb->aux)
+ for (bb = last_block; bb; bb = (basic_block) bb->aux)
if (insn2_block == bb)
break;
add_deps_for_risky_insns (rtx head, rtx tail)
{
rtx insn, prev;
- int class;
+ int classification;
rtx last_jump = NULL_RTX;
rtx next_tail = NEXT_INSN (tail);
basic_block last_block = NULL, bb;
}
else if (INSN_P (insn) && last_jump != NULL_RTX)
{
- class = haifa_classify_insn (insn);
+ classification = haifa_classify_insn (insn);
prev = last_jump;
- switch (class)
+ switch (classification)
{
case PFREE_CANDIDATE:
if (flag_schedule_speculative_load)
bb = earliest_block_with_similiar_load (last_block, insn);
if (bb)
{
- bb = bb->aux;
+ bb = (basic_block) bb->aux;
if (!bb)
break;
prev = BB_END (bb);
rank. */
if (! sched_insns_conditions_mutex_p (insn, prev))
{
- if (!(current_sched_info->flags & DO_SPECULATION))
+ dep_def _dep, *dep = &_dep;
+
+ init_dep (dep, prev, insn, REG_DEP_ANTI);
+
+ if (!(current_sched_info->flags & USE_DEPS_LIST))
{
enum DEPS_ADJUST_RESULT res;
-
- res = add_or_update_back_dep (insn, prev,
- REG_DEP_ANTI, DEP_ANTI);
-
- if (res == DEP_CREATED)
- add_forw_dep (DEPS_LIST_FIRST (INSN_BACK_DEPS (insn)));
- else
- gcc_assert (res != DEP_CHANGED);
+
+ res = sd_add_or_update_dep (dep, false);
+
+ /* We can't change an existing dependency with
+ DEP_ANTI. */
+ gcc_assert (res != DEP_CHANGED);
}
else
- add_or_update_back_forw_dep (insn, prev, REG_DEP_ANTI,
- set_dep_weak (DEP_ANTI,
- BEGIN_CONTROL,
- MAX_DEP_WEAK));
+ {
+ if ((current_sched_info->flags & DO_SPECULATION)
+ && (spec_info->mask & BEGIN_CONTROL))
+ DEP_STATUS (dep) = set_dep_weak (DEP_ANTI, BEGIN_CONTROL,
+ MAX_DEP_WEAK);
+
+ sd_add_or_update_dep (dep, false);
+
+ /* Dep_status could have been changed.
+ No assertion here. */
+ }
}
break;
/* Maintain the invariant that bb->aux is clear after use. */
while (last_block)
{
- bb = last_block->aux;
+ bb = (basic_block) last_block->aux;
last_block->aux = NULL;
last_block = bb;
}
{
basic_block first_bb, target_bb;
struct deps tmp_deps;
-
+
first_bb = BLOCK_FOR_INSN (head);
last_bb = BLOCK_FOR_INSN (tail);
{
init_deps_global ();
- /* Compute backward dependencies. */
- init_deps (&tmp_deps);
+ /* Compute dependencies. */
+ init_deps (&tmp_deps, false);
sched_analyze (&tmp_deps, head, tail);
free_deps (&tmp_deps);
- /* Compute forward dependencies. */
- compute_forward_dependences (head, tail);
-
add_deps_for_risky_insns (head, tail);
if (targetm.sched.dependencies_evaluation_hook)
}
else
/* Only recovery blocks can have their dependencies already calculated,
- and they always are single block ebbs. */
+ and they always are single block ebbs. */
gcc_assert (first_bb == last_bb);
/* Set priorities. */
current_sched_info->sched_max_insns_priority = 0;
- n_insns = set_priorities (head, tail);
+ rgn_n_insns = set_priorities (head, tail);
current_sched_info->sched_max_insns_priority++;
current_sched_info->prev_head = PREV_INSN (head);
current_sched_info->next_tail = NEXT_INSN (tail);
- /* rm_other_notes only removes notes which are _inside_ the
- block---that is, it won't remove notes before the first real insn
- or after the last real insn of the block. So if the first insn
- has a REG_SAVE_NOTE which would otherwise be emitted before the
- insn, it is redundant with the note before the start of the
- block, and so we have to take it out. */
- if (INSN_P (head))
- {
- rtx note;
-
- for (note = REG_NOTES (head); note; note = XEXP (note, 1))
- if (REG_NOTE_KIND (note) == REG_SAVE_NOTE)
- remove_note (head, note);
- }
-
- /* Remove remaining note insns from the block, save them in
- note_list. These notes are restored at the end of
- schedule_block (). */
- rm_other_notes (head, tail);
+ remove_notes (head, tail);
unlink_bb_notes (first_bb, last_bb);
- current_sched_info->queue_must_finish_empty = 1;
-
target_bb = first_bb;
- schedule_block (&target_bb, n_insns);
+
+ /* Make ready list big enough to hold all the instructions from the ebb. */
+ sched_extend_ready_list (rgn_n_insns);
+ schedule_block (&target_bb);
+ /* Free ready list. */
+ sched_finish_ready_list ();
/* We might pack all instructions into fewer blocks,
so we may made some of them empty. Can't assert (b == last_bb). */
-
+
/* Sanity check: verify that all region insns were scheduled. */
- gcc_assert (sched_n_insns == n_insns);
- head = current_sched_info->head;
- tail = current_sched_info->tail;
+ gcc_assert (sched_rgn_n_insns == rgn_n_insns);
+
+ /* Free dependencies. */
+ sched_free_deps (current_sched_info->head, current_sched_info->tail, true);
+
+ gcc_assert (haifa_recovery_bb_ever_added_p
+ || deps_pools_are_empty_p ());
if (EDGE_COUNT (last_bb->preds) == 0)
/* LAST_BB is unreachable. */
if (n_basic_blocks == NUM_FIXED_BLOCKS)
return;
- /* We need current_sched_info in init_dependency_caches, which is
- invoked via sched_init. */
- current_sched_info = &ebb_sched_info;
+ /* Setup infos. */
+ {
+ memcpy (&ebb_common_sched_info, &haifa_common_sched_info,
+ sizeof (ebb_common_sched_info));
+
+ ebb_common_sched_info.fix_recovery_cfg = ebb_fix_recovery_cfg;
+ ebb_common_sched_info.add_block = ebb_add_block;
+ ebb_common_sched_info.sched_pass_id = SCHED_EBB_PASS;
- df_set_flags (DF_LR_RUN_DCE);
- df_note_add_problem ();
- df_analyze ();
- df_clear_flags (DF_LR_RUN_DCE);
- regstat_compute_calls_crossed ();
- sched_init ();
+ common_sched_info = &ebb_common_sched_info;
+ sched_deps_info = &ebb_sched_deps_info;
+ current_sched_info = &ebb_sched_info;
+ }
+
+ haifa_sched_init ();
compute_bb_for_insn ();
a note or two. */
while (head != tail)
{
- if (NOTE_P (head))
+ if (NOTE_P (head) || BOUNDARY_DEBUG_INSN_P (head))
head = NEXT_INSN (head);
- else if (NOTE_P (tail))
+ else if (NOTE_P (tail) || BOUNDARY_DEBUG_INSN_P (tail))
tail = PREV_INSN (tail);
else if (LABEL_P (head))
head = NEXT_INSN (head);
if (reload_completed)
reposition_prologue_and_epilogue_notes ();
- sched_finish ();
- regstat_free_calls_crossed ();
+ haifa_sched_finish ();
}
/* INSN has been added to/removed from current ebb. */
static void
-add_remove_insn (rtx insn ATTRIBUTE_UNUSED, int remove_p)
+ebb_add_remove_insn (rtx insn ATTRIBUTE_UNUSED, int remove_p)
{
if (!remove_p)
- n_insns++;
+ rgn_n_insns++;
else
- n_insns--;
+ rgn_n_insns--;
}
/* BB was added to ebb after AFTER. */
static void
-add_block1 (basic_block bb, basic_block after)
+ebb_add_block (basic_block bb, basic_block after)
{
- /* Recovery blocks are always bounded by BARRIERS,
+ /* Recovery blocks are always bounded by BARRIERS,
therefore, they always form single block EBB,
therefore, we can use rec->index to identify such EBBs. */
if (after == EXIT_BLOCK_PTR)
For parameter meaning please refer to
sched-int.h: struct sched_info: fix_recovery_cfg. */
static void
-fix_recovery_cfg (int bbi ATTRIBUTE_UNUSED, int jump_bbi, int jump_bb_nexti)
+ebb_fix_recovery_cfg (int bbi ATTRIBUTE_UNUSED, int jump_bbi,
+ int jump_bb_nexti)
{
gcc_assert (last_bb->index != bbi);
if (jump_bb_nexti == last_bb->index)
last_bb = BASIC_BLOCK (jump_bbi);
}
+
+#endif /* INSN_SCHEDULING */