/* Instruction scheduling pass.
Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000,
- 2001, 2002, 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
+ 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)
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
+Software Foundation; either version 3, or (at your option) any later
version.
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
for more details.
You should have received a copy of the GNU General Public License
-along with GCC; see the file COPYING. If not, write to the Free
-Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
-02110-1301, USA. */
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
/* Instruction scheduling pass. This file, along with sched-deps.c,
contains the generic parts. The actual entry point is found for
static struct spec_info_def spec_info_var;
/* Description of the speculative part of the scheduling.
If NULL - no speculation. */
-static spec_info_t spec_info;
+spec_info_t spec_info;
/* True, if recovery block was added during scheduling of current block.
Used to determine, if we need to fix INSN_TICKs. */
-static bool added_recovery_block_p;
+static bool haifa_recovery_bb_recently_added_p;
+
+/* True, if recovery block was added during this scheduling pass.
+ Used to determine if we should have empty memory pools of dependencies
+ after finishing current region. */
+bool haifa_recovery_bb_ever_added_p;
/* Counters of different types of speculative instructions. */
static int nr_begin_data, nr_be_in_data, nr_begin_control, nr_be_in_control;
/* Number of instructions in current scheduling region. */
static int rgn_n_insns;
-static int may_trap_exp (rtx, int);
+static int may_trap_exp (const_rtx, int);
/* Nonzero iff the address is comprised from at most 1 register. */
#define CONST_BASED_ADDRESS_P(x) \
as found by analyzing insn's expression. */
static int
-may_trap_exp (rtx x, int is_store)
+may_trap_exp (const_rtx x, int is_store)
{
enum rtx_code code;
}
}
-/* Classifies insn for the purpose of verifying that it can be
- moved speculatively, by examining it's patterns, returning:
+/* Classifies rtx X of an insn for the purpose of verifying that X can be
+ executed speculatively (and consequently the insn can be moved
+ speculatively), by examining X, returning:
TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
TRAP_FREE: non-load insn.
IFREE: load from a globally safe location.
PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
being either PFREE or PRISKY. */
-int
-haifa_classify_insn (rtx insn)
+static int
+haifa_classify_rtx (const_rtx x)
{
- rtx pat = PATTERN (insn);
int tmp_class = TRAP_FREE;
int insn_class = TRAP_FREE;
enum rtx_code code;
- if (GET_CODE (pat) == PARALLEL)
+ if (GET_CODE (x) == PARALLEL)
{
- int i, len = XVECLEN (pat, 0);
+ int i, len = XVECLEN (x, 0);
for (i = len - 1; i >= 0; i--)
{
- code = GET_CODE (XVECEXP (pat, 0, i));
- switch (code)
- {
- case CLOBBER:
- /* Test if it is a 'store'. */
- tmp_class = may_trap_exp (XEXP (XVECEXP (pat, 0, i), 0), 1);
- break;
- case SET:
- /* Test if it is a store. */
- tmp_class = may_trap_exp (SET_DEST (XVECEXP (pat, 0, i)), 1);
- if (tmp_class == TRAP_RISKY)
- break;
- /* Test if it is a load. */
- tmp_class
- = WORST_CLASS (tmp_class,
- may_trap_exp (SET_SRC (XVECEXP (pat, 0, i)),
- 0));
- break;
- case COND_EXEC:
- case TRAP_IF:
- tmp_class = TRAP_RISKY;
- break;
- default:
- ;
- }
+ tmp_class = haifa_classify_rtx (XVECEXP (x, 0, i));
insn_class = WORST_CLASS (insn_class, tmp_class);
if (insn_class == TRAP_RISKY || insn_class == IRISKY)
break;
}
else
{
- code = GET_CODE (pat);
+ code = GET_CODE (x);
switch (code)
{
case CLOBBER:
/* Test if it is a 'store'. */
- tmp_class = may_trap_exp (XEXP (pat, 0), 1);
+ tmp_class = may_trap_exp (XEXP (x, 0), 1);
break;
case SET:
/* Test if it is a store. */
- tmp_class = may_trap_exp (SET_DEST (pat), 1);
+ tmp_class = may_trap_exp (SET_DEST (x), 1);
if (tmp_class == TRAP_RISKY)
break;
/* Test if it is a load. */
tmp_class =
WORST_CLASS (tmp_class,
- may_trap_exp (SET_SRC (pat), 0));
+ may_trap_exp (SET_SRC (x), 0));
break;
case COND_EXEC:
+ tmp_class = haifa_classify_rtx (COND_EXEC_CODE (x));
+ if (tmp_class == TRAP_RISKY)
+ break;
+ tmp_class = WORST_CLASS (tmp_class,
+ may_trap_exp (COND_EXEC_TEST (x), 0));
+ break;
case TRAP_IF:
tmp_class = TRAP_RISKY;
break;
return insn_class;
}
+int
+haifa_classify_insn (const_rtx insn)
+{
+ return haifa_classify_rtx (PATTERN (insn));
+}
+
+
/* A typedef for rtx vector. */
typedef VEC(rtx, heap) *rtx_vec_t;
static void swap_sort (rtx *, int);
static void queue_insn (rtx, int);
static int schedule_insn (rtx);
-static int find_set_reg_weight (rtx);
+static int find_set_reg_weight (const_rtx);
static void find_insn_reg_weight (basic_block);
static void find_insn_reg_weight1 (rtx);
static void adjust_priority (rtx);
static void extend_all (rtx);
static void init_h_i_d (rtx);
static void generate_recovery_code (rtx);
-static void process_insn_forw_deps_be_in_spec (deps_list_t, rtx, ds_t);
+static void process_insn_forw_deps_be_in_spec (rtx, rtx, ds_t);
static void begin_speculative_block (rtx);
static void add_to_speculative_block (rtx);
static dw_t dep_weak (ds_t);
#ifdef ENABLE_CHECKING
static int has_edge_p (VEC(edge,gc) *, int);
static void check_cfg (rtx, rtx);
-static void check_sched_flags (void);
#endif
#endif /* INSN_SCHEDULING */
else
{
rtx insn = DEP_PRO (link);
- enum reg_note dep_type = DEP_KIND (link);
+ enum reg_note dep_type = DEP_TYPE (link);
cost = insn_cost (insn);
XEXP (dep_cost_rtx_link, 1) = dep_cost_rtx_link;
/* Targets use only REG_NOTE_KIND of the link. */
- PUT_REG_NOTE_KIND (dep_cost_rtx_link, DEP_KIND (link));
+ PUT_REG_NOTE_KIND (dep_cost_rtx_link, DEP_TYPE (link));
cost = targetm.sched.adjust_cost (used, dep_cost_rtx_link,
insn, cost);
static int
priority (rtx insn)
{
- dep_link_t link;
-
if (! INSN_P (insn))
return 0;
{
int this_priority = 0;
- if (deps_list_empty_p (INSN_FORW_DEPS (insn)))
+ if (sd_lists_empty_p (insn, SD_LIST_FORW))
/* ??? We should set INSN_PRIORITY to insn_cost when and insn has
some forward deps but all of them are ignored by
contributes_to_priority hook. At the moment we set priority of
do
{
- FOR_EACH_DEP_LINK (link, INSN_FORW_DEPS (twin))
+ sd_iterator_def sd_it;
+ dep_t dep;
+
+ FOR_EACH_DEP (twin, SD_LIST_FORW, sd_it, dep)
{
rtx next;
int next_priority;
- dep_t dep = DEP_LINK_DEP (link);
next = DEP_CON (dep);
{
rtx tmp = *(const rtx *) y;
rtx tmp2 = *(const rtx *) x;
- dep_link_t link1, link2;
int tmp_class, tmp2_class;
int val, priority_val, weight_val, info_val;
/* Compare insns based on their relation to the last-scheduled-insn. */
if (INSN_P (last_scheduled_insn))
{
+ dep_t dep1;
+ dep_t dep2;
+
/* Classify the instructions into three classes:
1) Data dependent on last schedule insn.
2) Anti/Output dependent on last scheduled insn.
3) Independent of last scheduled insn, or has latency of one.
Choose the insn from the highest numbered class if different. */
- link1
- = find_link_by_con_in_deps_list (INSN_FORW_DEPS (last_scheduled_insn),
- tmp);
+ dep1 = sd_find_dep_between (last_scheduled_insn, tmp, true);
- if (link1 == NULL || dep_cost (DEP_LINK_DEP (link1)) == 1)
+ if (dep1 == NULL || dep_cost (dep1) == 1)
tmp_class = 3;
else if (/* Data dependence. */
- DEP_LINK_KIND (link1) == REG_DEP_TRUE)
+ DEP_TYPE (dep1) == REG_DEP_TRUE)
tmp_class = 1;
else
tmp_class = 2;
- link2
- = find_link_by_con_in_deps_list (INSN_FORW_DEPS (last_scheduled_insn),
- tmp2);
+ dep2 = sd_find_dep_between (last_scheduled_insn, tmp2, true);
- if (link2 == NULL || dep_cost (DEP_LINK_DEP (link2)) == 1)
+ if (dep2 == NULL || dep_cost (dep2) == 1)
tmp2_class = 3;
else if (/* Data dependence. */
- DEP_LINK_KIND (link2) == REG_DEP_TRUE)
+ DEP_TYPE (dep2) == REG_DEP_TRUE)
tmp2_class = 1;
else
tmp2_class = 2;
This gives the scheduler more freedom when scheduling later
instructions at the expense of added register pressure. */
- link1 = DEPS_LIST_FIRST (INSN_FORW_DEPS (tmp));
- link2 = DEPS_LIST_FIRST (INSN_FORW_DEPS (tmp2));
+ val = (sd_lists_size (tmp2, SD_LIST_FORW)
+ - sd_lists_size (tmp, SD_LIST_FORW));
- while (link1 != NULL && link2 != NULL)
- {
- link1 = DEP_LINK_NEXT (link1);
- link2 = DEP_LINK_NEXT (link2);
- }
-
- if (link1 != NULL && link2 == NULL)
- /* TMP (Y) has more insns that depend on it. */
- return -1;
- if (link1 == NULL && link2 != NULL)
- /* TMP2 (X) has more insns that depend on it. */
- return 1;
+ if (val != 0)
+ return val;
/* If insns are equally good, sort by INSN_LUID (original insn order),
so that we make the sort stable. This minimizes instruction movement,
HAIFA_INLINE static void
advance_one_cycle (void)
{
+ if (targetm.sched.dfa_pre_advance_cycle)
+ targetm.sched.dfa_pre_advance_cycle ();
+
if (targetm.sched.dfa_pre_cycle_insn)
state_transition (curr_state,
targetm.sched.dfa_pre_cycle_insn ());
if (targetm.sched.dfa_post_cycle_insn)
state_transition (curr_state,
targetm.sched.dfa_post_cycle_insn ());
+
+ if (targetm.sched.dfa_post_advance_cycle)
+ targetm.sched.dfa_post_advance_cycle ();
}
/* Clock at which the previous instruction was issued. */
static int
schedule_insn (rtx insn)
{
- dep_link_t link;
+ sd_iterator_def sd_it;
+ dep_t dep;
int advance = 0;
if (sched_verbose >= 1)
/* Scheduling instruction should have all its dependencies resolved and
should have been removed from the ready list. */
- gcc_assert (INSN_DEP_COUNT (insn) == 0
- && deps_list_empty_p (INSN_BACK_DEPS (insn)));
- free_deps_list (INSN_BACK_DEPS (insn));
-
- /* Now we can free INSN_RESOLVED_BACK_DEPS list. */
- delete_deps_list (INSN_RESOLVED_BACK_DEPS (insn));
+ gcc_assert (sd_lists_empty_p (insn, SD_LIST_BACK));
gcc_assert (QUEUE_INDEX (insn) == QUEUE_NOWHERE);
QUEUE_INDEX (insn) = QUEUE_SCHEDULED;
INSN_TICK (insn) = clock_var;
/* Update dependent instructions. */
- FOR_EACH_DEP_LINK (link, INSN_FORW_DEPS (insn))
+ for (sd_it = sd_iterator_start (insn, SD_LIST_FORW);
+ sd_iterator_cond (&sd_it, &dep);)
{
- rtx next = DEP_LINK_CON (link);
-
- /* Resolve the dependence between INSN and NEXT. */
+ rtx next = DEP_CON (dep);
- INSN_DEP_COUNT (next)--;
-
- move_dep_link (DEP_NODE_BACK (DEP_LINK_NODE (link)),
- INSN_RESOLVED_BACK_DEPS (next));
-
- gcc_assert ((INSN_DEP_COUNT (next) == 0)
- == deps_list_empty_p (INSN_BACK_DEPS (next)));
+ /* Resolve the dependence between INSN and NEXT.
+ sd_resolve_dep () moves current dep to another list thus
+ advancing the iterator. */
+ sd_resolve_dep (sd_it);
if (!IS_SPECULATION_BRANCHY_CHECK_P (insn))
{
/* Check always has only one forward dependence (to the first insn in
the recovery block), therefore, this will be executed only once. */
{
- gcc_assert (DEP_LINK_NEXT (link) == NULL);
+ gcc_assert (sd_lists_empty_p (insn, SD_LIST_FORW));
fix_recovery_deps (RECOVERY_BLOCK (insn));
}
}
+ /* This is the place where scheduler doesn't *basically* need backward and
+ forward dependencies for INSN anymore. Nevertheless they are used in
+ heuristics in rank_for_schedule (), early_queue_to_ready () and in
+ some targets (e.g. rs6000). Thus the earliest place where we *can*
+ remove dependencies is after targetm.sched.md_finish () call in
+ schedule_block (). But, on the other side, the safest place to remove
+ dependencies is when we are finishing scheduling entire region. As we
+ don't generate [many] dependencies during scheduling itself, we won't
+ need memory until beginning of next region.
+ Bottom line: Dependencies are removed for all insns in the end of
+ scheduling the region. */
+
/* Annotate the instruction with issue information -- TImode
indicates that the instruction is expected not to be able
to issue on the same cycle as the previous insn. A machine
/* Return nonzero if there are no real insns in the range [ HEAD, TAIL ]. */
int
-no_real_insns_p (rtx head, rtx tail)
+no_real_insns_p (const_rtx head, const_rtx tail)
{
while (head != NEXT_INSN (tail))
{
a new register is not needed. */
static int
-find_set_reg_weight (rtx x)
+find_set_reg_weight (const_rtx x)
{
if (GET_CODE (x) == CLOBBER
&& register_operand (SET_DEST (x), VOIDmode))
{
int cost;
+ if (prev_insn == current_sched_info->prev_head)
+ {
+ prev_insn = NULL;
+ break;
+ }
+
if (!NOTE_P (prev_insn))
{
- dep_link_t dep_link;
+ dep_t dep;
- dep_link = (find_link_by_con_in_deps_list
- (INSN_FORW_DEPS (prev_insn), insn));
+ dep = sd_find_dep_between (prev_insn, insn, true);
- if (dep_link)
+ if (dep != NULL)
{
- dep_t dep = DEP_LINK_DEP (dep_link);
-
cost = dep_cost (dep);
if (targetm.sched.is_costly_dependence (dep, cost,
gcc_assert (BB_END (bb) == last);
}
- set_block_for_insn (insn, bb);
- df_insn_change_bb (insn);
+ df_insn_change_bb (insn, bb);
/* Update BB_END, if needed. */
if (BB_END (bb) == last)
gcc_assert (head != tail || INSN_P (head));
- added_recovery_block_p = false;
+ haifa_recovery_bb_recently_added_p = false;
/* Debug info. */
if (sched_verbose)
}
if (!current_sched_info->queue_must_finish_empty
- || added_recovery_block_p)
+ || haifa_recovery_bb_recently_added_p)
{
/* INSN_TICK (minimum clock tick at which the insn becomes
ready) may be not correct for the insn in the subsequent
}
if (targetm.sched.md_finish)
- targetm.sched.md_finish (sched_dump, sched_verbose);
+ {
+ targetm.sched.md_finish (sched_dump, sched_verbose);
+
+ /* Target might have added some instructions to the scheduled block.
+ in its md_finish () hook. These new insns don't have any data
+ initialized and to identify them we extend h_i_d so that they'll
+ get zero luids.*/
+ extend_h_i_d ();
+ }
/* Update head/tail boundaries. */
head = NEXT_INSN (prev_head);
else
/* So we won't read anything accidentally. */
spec_info = 0;
-#ifdef ENABLE_CHECKING
- check_sched_flags ();
-#endif
}
else
/* So we won't read anything accidentally. */
nr_begin_data = nr_begin_control = nr_be_in_data = nr_be_in_control = 0;
before_recovery = 0;
+ haifa_recovery_bb_ever_added_p = false;
+
#ifdef ENABLE_CHECKING
/* This is used preferably for finding bugs in check_cfg () itself. */
check_cfg (0, 0);
{
/* Set of instructions with corrected INSN_TICK. */
bitmap_head processed;
+ /* ??? It is doubtful if we should assume that cycle advance happens on
+ basic block boundaries. Basically insns that are unconditionally ready
+ on the start of the block are more preferable then those which have
+ a one cycle dependency over insn from the previous block. */
int next_clock = clock_var + 1;
bitmap_initialize (&processed, 0);
if (INSN_P (head))
{
int tick;
- dep_link_t link;
+ sd_iterator_def sd_it;
+ dep_t dep;
tick = INSN_TICK (head);
gcc_assert (tick >= MIN_TICK);
INSN_TICK (head) = tick;
}
- FOR_EACH_DEP_LINK (link, INSN_FORW_DEPS (head))
+ FOR_EACH_DEP (head, SD_LIST_RES_FORW, sd_it, dep)
{
rtx next;
- next = DEP_LINK_CON (link);
+ next = DEP_CON (dep);
tick = INSN_TICK (next);
if (tick != INVALID_TICK
INTER_TICK (next) = tick;
else
tick = INTER_TICK (next);
-
+
INSN_TICK (next) = tick;
}
}
try_ready (rtx next)
{
ds_t old_ts, *ts;
- dep_link_t link;
ts = &TODO_SPEC (next);
old_ts = *ts;
&& ((old_ts & HARD_DEP)
|| (old_ts & SPECULATIVE)));
- if (!(current_sched_info->flags & DO_SPECULATION))
+ if (sd_lists_empty_p (next, SD_LIST_BACK))
+ /* NEXT has all its dependencies resolved. */
{
- if (deps_list_empty_p (INSN_BACK_DEPS (next)))
- *ts &= ~HARD_DEP;
+ /* Remove HARD_DEP bit from NEXT's status. */
+ *ts &= ~HARD_DEP;
+
+ if (current_sched_info->flags & DO_SPECULATION)
+ /* Remove all speculative bits from NEXT's status. */
+ *ts &= ~SPECULATIVE;
}
else
{
+ /* One of the NEXT's dependencies has been resolved.
+ Recalculate NEXT's status. */
+
*ts &= ~SPECULATIVE & ~HARD_DEP;
- link = DEPS_LIST_FIRST (INSN_BACK_DEPS (next));
+ if (sd_lists_empty_p (next, SD_LIST_HARD_BACK))
+ /* Now we've got NEXT with speculative deps only.
+ 1. Look at the deps to see what we have to do.
+ 2. Check if we can do 'todo'. */
+ {
+ sd_iterator_def sd_it;
+ dep_t dep;
+ bool first_p = true;
- if (link != NULL)
- {
- ds_t ds = DEP_LINK_STATUS (link) & SPECULATIVE;
-
- /* Backward dependencies of the insn are maintained sorted.
- So if DEP_STATUS of the first dep is SPECULATIVE,
- than all other deps are speculative too. */
- if (ds != 0)
- {
- /* Now we've got NEXT with speculative deps only.
- 1. Look at the deps to see what we have to do.
- 2. Check if we can do 'todo'. */
- *ts = ds;
-
- while ((link = DEP_LINK_NEXT (link)) != NULL)
+ FOR_EACH_DEP (next, SD_LIST_BACK, sd_it, dep)
+ {
+ ds_t ds = DEP_STATUS (dep) & SPECULATIVE;
+
+ if (first_p)
{
- ds = DEP_LINK_STATUS (link) & SPECULATIVE;
- *ts = ds_merge (*ts, ds);
- }
+ first_p = false;
- if (dep_weak (*ts) < spec_info->weakness_cutoff)
- /* Too few points. */
- *ts = (*ts & ~SPECULATIVE) | HARD_DEP;
+ *ts = ds;
+ }
+ else
+ *ts = ds_merge (*ts, ds);
}
- else
- *ts |= HARD_DEP;
- }
+
+ if (dep_weak (*ts) < spec_info->weakness_cutoff)
+ /* Too few points. */
+ *ts = (*ts & ~SPECULATIVE) | HARD_DEP;
+ }
+ else
+ *ts |= HARD_DEP;
}
if (*ts & HARD_DEP)
{
int tick, delay;
- if (!deps_list_empty_p (INSN_RESOLVED_BACK_DEPS (next)))
+ if (!sd_lists_empty_p (next, SD_LIST_RES_BACK))
{
int full_p;
- dep_link_t link;
+ sd_iterator_def sd_it;
+ dep_t dep;
tick = INSN_TICK (next);
/* if tick is not equal to INVALID_TICK, then update
cost. Otherwise, recalculate from scratch. */
full_p = (tick == INVALID_TICK);
- FOR_EACH_DEP_LINK (link, INSN_RESOLVED_BACK_DEPS (next))
+ FOR_EACH_DEP (next, SD_LIST_RES_BACK, sd_it, dep)
{
- dep_t dep = DEP_LINK_DEP (link);
rtx pro = DEP_PRO (dep);
int tick1;
extend_global (rtx insn)
{
gcc_assert (INSN_P (insn));
+
/* These structures have scheduler scope. */
+
+ /* Init h_i_d. */
extend_h_i_d ();
init_h_i_d (insn);
- extend_dependency_caches (1, 0);
+ /* Init data handled in sched-deps.c. */
+ sd_init_insn (insn);
+
+ /* Extend dependency caches by one element. */
+ extend_dependency_caches (1, false);
}
/* Extends global and local scheduler structures to include information
INSN_TICK (insn) = INVALID_TICK;
INTER_TICK (insn) = INVALID_TICK;
find_insn_reg_weight1 (insn);
-
- /* These two lists will be freed in schedule_insn (). */
- INSN_BACK_DEPS (insn) = create_deps_list (false);
- INSN_RESOLVED_BACK_DEPS (insn) = create_deps_list (false);
-
- /* This one should be allocated on the obstack because it should live till
- the scheduling ends. */
- INSN_FORW_DEPS (insn) = create_deps_list (true);
}
/* Generates recovery code for INSN. */
Tries to add speculative dependencies of type FS between instructions
in deps_list L and TWIN. */
static void
-process_insn_forw_deps_be_in_spec (deps_list_t l, rtx twin, ds_t fs)
+process_insn_forw_deps_be_in_spec (rtx insn, rtx twin, ds_t fs)
{
- dep_link_t link;
+ sd_iterator_def sd_it;
+ dep_t dep;
- FOR_EACH_DEP_LINK (link, l)
+ FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
{
ds_t ds;
rtx consumer;
- consumer = DEP_LINK_CON (link);
+ consumer = DEP_CON (dep);
- ds = DEP_LINK_STATUS (link);
+ ds = DEP_STATUS (dep);
if (/* If we want to create speculative dep. */
fs
due to backend decision. Hence we can't let the
probability of the speculative dep to decrease. */
dep_weak (ds) <= dep_weak (fs))
- /* Transform it to be in speculative. */
- ds = (ds & ~BEGIN_SPEC) | fs;
+ {
+ ds_t new_ds;
+
+ new_ds = (ds & ~BEGIN_SPEC) | fs;
+
+ if (/* consumer can 'be in speculative'. */
+ sched_insn_is_legitimate_for_speculation_p (consumer,
+ new_ds))
+ /* Transform it to be in speculative. */
+ ds = new_ds;
+ }
}
else
/* Mark the dep as 'be in speculative'. */
ds |= fs;
}
- add_back_forw_dep (consumer, twin, DEP_LINK_KIND (link), ds);
+ {
+ dep_def _new_dep, *new_dep = &_new_dep;
+
+ init_dep_1 (new_dep, twin, consumer, DEP_TYPE (dep), ds);
+ sd_add_dep (new_dep, false);
+ }
}
}
add_to_speculative_block (rtx insn)
{
ds_t ts;
- dep_link_t link;
+ sd_iterator_def sd_it;
+ dep_t dep;
rtx twins = NULL;
rtx_vec_t priorities_roots;
DONE_SPEC (insn) |= ts;
/* First we convert all simple checks to branchy. */
- for (link = DEPS_LIST_FIRST (INSN_BACK_DEPS (insn)); link != NULL;)
+ for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
+ sd_iterator_cond (&sd_it, &dep);)
{
- rtx check = DEP_LINK_PRO (link);
+ rtx check = DEP_PRO (dep);
if (IS_SPECULATION_SIMPLE_CHECK_P (check))
{
create_check_block_twin (check, true);
/* Restart search. */
- link = DEPS_LIST_FIRST (INSN_BACK_DEPS (insn));
+ sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
}
else
/* Continue search. */
- link = DEP_LINK_NEXT (link);
+ sd_iterator_next (&sd_it);
}
priorities_roots = NULL;
clear_priorities (insn, &priorities_roots);
-
- do
+
+ while (1)
{
- dep_link_t link;
rtx check, twin;
basic_block rec;
- link = DEPS_LIST_FIRST (INSN_BACK_DEPS (insn));
+ /* Get the first backward dependency of INSN. */
+ sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
+ if (!sd_iterator_cond (&sd_it, &dep))
+ /* INSN has no backward dependencies left. */
+ break;
- gcc_assert ((DEP_LINK_STATUS (link) & BEGIN_SPEC) == 0
- && (DEP_LINK_STATUS (link) & BE_IN_SPEC) != 0
- && (DEP_LINK_STATUS (link) & DEP_TYPES) == DEP_TRUE);
+ gcc_assert ((DEP_STATUS (dep) & BEGIN_SPEC) == 0
+ && (DEP_STATUS (dep) & BE_IN_SPEC) != 0
+ && (DEP_STATUS (dep) & DEP_TYPES) == DEP_TRUE);
- check = DEP_LINK_PRO (link);
+ check = DEP_PRO (dep);
gcc_assert (!IS_SPECULATION_CHECK_P (check) && !ORIG_PAT (check)
&& QUEUE_INDEX (check) == QUEUE_NOWHERE);
-
+
rec = BLOCK_FOR_INSN (check);
-
+
twin = emit_insn_before (copy_insn (PATTERN (insn)), BB_END (rec));
extend_global (twin);
- copy_deps_list_change_con (INSN_RESOLVED_BACK_DEPS (twin),
- INSN_RESOLVED_BACK_DEPS (insn),
- twin);
+ sd_copy_back_deps (twin, insn, true);
if (sched_verbose && spec_info->dump)
/* INSN_BB (insn) isn't determined for twin insns yet.
/* Add dependences between TWIN and all appropriate
instructions from REC. */
- do
- {
- add_back_forw_dep (twin, check, REG_DEP_TRUE, DEP_TRUE);
-
- do
- {
- link = DEP_LINK_NEXT (link);
+ FOR_EACH_DEP (insn, SD_LIST_SPEC_BACK, sd_it, dep)
+ {
+ rtx pro = DEP_PRO (dep);
- if (link != NULL)
- {
- check = DEP_LINK_PRO (link);
- if (BLOCK_FOR_INSN (check) == rec)
- break;
- }
- else
- break;
+ gcc_assert (DEP_TYPE (dep) == REG_DEP_TRUE);
+
+ /* INSN might have dependencies from the instructions from
+ several recovery blocks. At this iteration we process those
+ producers that reside in REC. */
+ if (BLOCK_FOR_INSN (pro) == rec)
+ {
+ dep_def _new_dep, *new_dep = &_new_dep;
+
+ init_dep (new_dep, pro, twin, REG_DEP_TRUE);
+ sd_add_dep (new_dep, false);
}
- while (1);
}
- while (link != NULL);
- process_insn_forw_deps_be_in_spec (INSN_FORW_DEPS (insn), twin, ts);
+ process_insn_forw_deps_be_in_spec (insn, twin, ts);
/* Remove all dependencies between INSN and insns in REC. */
- for (link = DEPS_LIST_FIRST (INSN_BACK_DEPS (insn)); link != NULL;)
+ for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
+ sd_iterator_cond (&sd_it, &dep);)
{
- check = DEP_LINK_PRO (link);
-
- if (BLOCK_FOR_INSN (check) == rec)
- {
- delete_back_forw_dep (link);
+ rtx pro = DEP_PRO (dep);
- /* Restart search. */
- link = DEPS_LIST_FIRST (INSN_BACK_DEPS (insn));
- }
+ if (BLOCK_FOR_INSN (pro) == rec)
+ sd_delete_dep (sd_it);
else
- /* Continue search. */
- link = DEP_LINK_NEXT (link);
+ sd_iterator_next (&sd_it);
}
}
- while (!deps_list_empty_p (INSN_BACK_DEPS (insn)));
/* We couldn't have added the dependencies between INSN and TWINS earlier
because that would make TWINS appear in the INSN_BACK_DEPS (INSN). */
rtx twin;
twin = XEXP (twins, 0);
- add_back_forw_dep (twin, insn, REG_DEP_OUTPUT, DEP_OUTPUT);
+
+ {
+ dep_def _new_dep, *new_dep = &_new_dep;
+
+ init_dep (new_dep, insn, twin, REG_DEP_OUTPUT);
+ sd_add_dep (new_dep, false);
+ }
twin = XEXP (twins, 1);
free_INSN_LIST_node (twins);
rtx barrier;
basic_block rec;
- added_recovery_block_p = true;
+ haifa_recovery_bb_recently_added_p = true;
+ haifa_recovery_bb_ever_added_p = true;
if (!before_recovery)
init_before_recovery ();
{
basic_block rec;
rtx label, check, twin;
- dep_link_t link;
ds_t fs;
+ sd_iterator_def sd_it;
+ dep_t dep;
+ dep_def _new_dep, *new_dep = &_new_dep;
gcc_assert (ORIG_PAT (insn)
&& (!mutate_p
in the recovery block). */
if (rec != EXIT_BLOCK_PTR)
{
- FOR_EACH_DEP_LINK (link, INSN_RESOLVED_BACK_DEPS (insn))
- if ((DEP_LINK_STATUS (link) & DEP_OUTPUT) != 0)
+ sd_iterator_def sd_it;
+ dep_t dep;
+
+ FOR_EACH_DEP (insn, SD_LIST_RES_BACK, sd_it, dep)
+ if ((DEP_STATUS (dep) & DEP_OUTPUT) != 0)
{
- struct _dep _dep, *dep = &_dep;
+ struct _dep _dep2, *dep2 = &_dep2;
- init_dep (dep, DEP_LINK_PRO (link), check, REG_DEP_TRUE);
+ init_dep (dep2, DEP_PRO (dep), check, REG_DEP_TRUE);
- add_back_dep_to_deps_list (INSN_RESOLVED_BACK_DEPS (check), dep);
+ sd_add_dep (dep2, true);
}
twin = emit_insn_after (ORIG_PAT (insn), BB_END (rec));
(TRUE | OUTPUT). */
}
- copy_deps_list_change_con (INSN_RESOLVED_BACK_DEPS (twin),
- INSN_RESOLVED_BACK_DEPS (insn),
- twin);
+ /* Copy all resolved back dependencies of INSN to TWIN. This will
+ provide correct value for INSN_TICK (TWIN). */
+ sd_copy_back_deps (twin, insn, true);
if (rec != EXIT_BLOCK_PTR)
/* In case of branchy check, fix CFG. */
/* Move backward dependences from INSN to CHECK and
move forward dependences from INSN to TWIN. */
- FOR_EACH_DEP_LINK (link, INSN_BACK_DEPS (insn))
+
+ /* First, create dependencies between INSN's producers and CHECK & TWIN. */
+ FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
{
- rtx pro = DEP_LINK_PRO (link);
- enum reg_note dk = DEP_LINK_KIND (link);
+ rtx pro = DEP_PRO (dep);
ds_t ds;
/* If BEGIN_DATA: [insn ~~TRUE~~> producer]:
twin ~~TRUE~~> producer
twin --ANTI--> check */
- ds = DEP_LINK_STATUS (link);
+ ds = DEP_STATUS (dep);
if (ds & BEGIN_SPEC)
{
ds &= ~BEGIN_SPEC;
}
+ init_dep_1 (new_dep, pro, check, DEP_TYPE (dep), ds);
+ sd_add_dep (new_dep, false);
+
if (rec != EXIT_BLOCK_PTR)
{
- add_back_forw_dep (check, pro, dk, ds);
- add_back_forw_dep (twin, pro, dk, ds);
+ DEP_CON (new_dep) = twin;
+ sd_add_dep (new_dep, false);
}
- else
- add_back_forw_dep (check, pro, dk, ds);
}
- for (link = DEPS_LIST_FIRST (INSN_BACK_DEPS (insn)); link != NULL;)
- if ((DEP_LINK_STATUS (link) & BEGIN_SPEC)
- || mutate_p)
- /* We can delete this dep only if we totally overcome it with
- BEGIN_SPECULATION. */
- {
- delete_back_forw_dep (link);
-
- /* Restart search. */
- link = DEPS_LIST_FIRST (INSN_BACK_DEPS (insn));
- }
- else
- /* Continue search. */
- link = DEP_LINK_NEXT (link);
+ /* Second, remove backward dependencies of INSN. */
+ for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
+ sd_iterator_cond (&sd_it, &dep);)
+ {
+ if ((DEP_STATUS (dep) & BEGIN_SPEC)
+ || mutate_p)
+ /* We can delete this dep because we overcome it with
+ BEGIN_SPECULATION. */
+ sd_delete_dep (sd_it);
+ else
+ sd_iterator_next (&sd_it);
+ }
+ /* Future Speculations. Determine what BE_IN speculations will be like. */
fs = 0;
/* Fields (DONE_SPEC (x) & BEGIN_SPEC) and CHECK_SPEC (x) are set only
DONE_SPEC (insn) = ts & BEGIN_SPEC;
CHECK_SPEC (check) = ts & BEGIN_SPEC;
+ /* Luckiness of future speculations solely depends upon initial
+ BEGIN speculation. */
if (ts & BEGIN_DATA)
fs = set_dep_weak (fs, BE_IN_DATA, get_dep_weak (ts, BEGIN_DATA));
if (ts & BEGIN_CONTROL)
- fs = set_dep_weak (fs, BE_IN_CONTROL, get_dep_weak (ts, BEGIN_CONTROL));
+ fs = set_dep_weak (fs, BE_IN_CONTROL,
+ get_dep_weak (ts, BEGIN_CONTROL));
}
else
CHECK_SPEC (check) = CHECK_SPEC (insn);
/* Future speculations: call the helper. */
- process_insn_forw_deps_be_in_spec (INSN_FORW_DEPS (insn), twin, fs);
+ process_insn_forw_deps_be_in_spec (insn, twin, fs);
if (rec != EXIT_BLOCK_PTR)
{
if (!mutate_p)
{
- add_back_forw_dep (check, insn, REG_DEP_TRUE, DEP_TRUE);
- add_back_forw_dep (twin, insn, REG_DEP_OUTPUT, DEP_OUTPUT);
+ init_dep (new_dep, insn, check, REG_DEP_TRUE);
+ sd_add_dep (new_dep, false);
+
+ init_dep (new_dep, insn, twin, REG_DEP_OUTPUT);
+ sd_add_dep (new_dep, false);
}
else
{
- dep_link_t link;
-
if (spec_info->dump)
fprintf (spec_info->dump, ";;\t\tRemoved simple check : %s\n",
(*current_sched_info->print_insn) (insn, 0));
- /* Remove all forward dependencies of the INSN. */
- link = DEPS_LIST_FIRST (INSN_FORW_DEPS (insn));
- while (link != NULL)
- {
- delete_back_forw_dep (link);
- link = DEPS_LIST_FIRST (INSN_FORW_DEPS (insn));
- }
+ /* Remove all dependencies of the INSN. */
+ {
+ sd_it = sd_iterator_start (insn, (SD_LIST_FORW
+ | SD_LIST_BACK
+ | SD_LIST_RES_BACK));
+ while (sd_iterator_cond (&sd_it, &dep))
+ sd_delete_dep (sd_it);
+ }
+ /* If former check (INSN) already was moved to the ready (or queue)
+ list, add new check (CHECK) there too. */
if (QUEUE_INDEX (insn) != QUEUE_NOWHERE)
try_ready (check);
+ /* Remove old check from instruction stream and free its
+ data. */
sched_remove_insn (insn);
}
- add_back_forw_dep (twin, check, REG_DEP_ANTI, DEP_ANTI);
+ init_dep (new_dep, check, twin, REG_DEP_ANTI);
+ sd_add_dep (new_dep, false);
}
else
- add_back_forw_dep (check, insn, REG_DEP_TRUE, DEP_TRUE | DEP_OUTPUT);
+ {
+ init_dep_1 (new_dep, insn, check, REG_DEP_TRUE, DEP_TRUE | DEP_OUTPUT);
+ sd_add_dep (new_dep, false);
+ }
if (!mutate_p)
/* Fix priorities. If MUTATE_P is nonzero, this is not necessary,
static void
fix_recovery_deps (basic_block rec)
{
- dep_link_t link;
rtx note, insn, jump, ready_list = 0;
bitmap_head in_ready;
- rtx link1;
+ rtx link;
bitmap_initialize (&in_ready, 0);
insn = PREV_INSN (insn);
do
- {
- for (link = DEPS_LIST_FIRST (INSN_FORW_DEPS (insn)); link != NULL;)
- {
- rtx consumer;
+ {
+ sd_iterator_def sd_it;
+ dep_t dep;
- consumer = DEP_LINK_CON (link);
+ for (sd_it = sd_iterator_start (insn, SD_LIST_FORW);
+ sd_iterator_cond (&sd_it, &dep);)
+ {
+ rtx consumer = DEP_CON (dep);
if (BLOCK_FOR_INSN (consumer) != rec)
{
- delete_back_forw_dep (link);
+ sd_delete_dep (sd_it);
if (!bitmap_bit_p (&in_ready, INSN_LUID (consumer)))
{
ready_list = alloc_INSN_LIST (consumer, ready_list);
bitmap_set_bit (&in_ready, INSN_LUID (consumer));
}
-
- /* Restart search. */
- link = DEPS_LIST_FIRST (INSN_FORW_DEPS (insn));
}
else
{
- gcc_assert ((DEP_LINK_STATUS (link) & DEP_TYPES) == DEP_TRUE);
+ gcc_assert ((DEP_STATUS (dep) & DEP_TYPES) == DEP_TRUE);
- /* Continue search. */
- link = DEP_LINK_NEXT (link);
+ sd_iterator_next (&sd_it);
}
}
bitmap_clear (&in_ready);
/* Try to add instructions to the ready or queue list. */
- for (link1 = ready_list; link1; link1 = XEXP (link1, 1))
- try_ready (XEXP (link1, 0));
+ for (link = ready_list; link; link = XEXP (link, 1))
+ try_ready (XEXP (link, 0));
free_INSN_LIST_list (&ready_list);
/* Fixing jump's dependences. */
dfa_clear_single_insn_cache (insn);
}
+/* Return true if INSN can potentially be speculated with type DS. */
+bool
+sched_insn_is_legitimate_for_speculation_p (const_rtx insn, ds_t ds)
+{
+ if (HAS_INTERNAL_DEP (insn))
+ return false;
+
+ if (!NONJUMP_INSN_P (insn))
+ return false;
+
+ if (SCHED_GROUP_P (insn))
+ return false;
+
+ if (IS_SPECULATION_CHECK_P (insn))
+ return false;
+
+ if (side_effects_p (PATTERN (insn)))
+ return false;
+
+ if ((ds & BE_IN_SPEC)
+ && may_trap_p (PATTERN (insn)))
+ return false;
+
+ return true;
+}
/* -1 - can't speculate,
0 - for speculation with REQUEST mode it is OK to use
speculate_insn (rtx insn, ds_t request, rtx *new_pat)
{
gcc_assert (current_sched_info->flags & DO_SPECULATION
- && (request & SPECULATIVE));
+ && (request & SPECULATIVE)
+ && sched_insn_is_legitimate_for_speculation_p (insn, request));
- if (!NONJUMP_INSN_P (insn)
- || HAS_INTERNAL_DEP (insn)
- || SCHED_GROUP_P (insn)
- || side_effects_p (PATTERN (insn))
- || (request & spec_info->mask) != request)
+ if ((request & spec_info->mask) != request)
return -1;
-
- gcc_assert (!IS_SPECULATION_CHECK_P (insn));
- if (request & BE_IN_SPEC)
- {
- if (may_trap_p (PATTERN (insn)))
- return -1;
-
- if (!(request & BEGIN_SPEC))
- return 0;
- }
+ if (request & BE_IN_SPEC
+ && !(request & BEGIN_SPEC))
+ return 0;
return targetm.sched.speculate_insn (insn, request & BEGIN_SPEC, new_pat);
}
static void
sched_remove_insn (rtx insn)
{
+ sd_finish_insn (insn);
+
change_queue_index (insn, QUEUE_NOWHERE);
current_sched_info->add_remove_insn (insn, 1);
remove_insn (insn);
static void
clear_priorities (rtx insn, rtx_vec_t *roots_ptr)
{
- dep_link_t link;
+ sd_iterator_def sd_it;
+ dep_t dep;
bool insn_is_root_p = true;
gcc_assert (QUEUE_INDEX (insn) != QUEUE_SCHEDULED);
- FOR_EACH_DEP_LINK (link, INSN_BACK_DEPS (insn))
+ FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
{
- dep_t dep = DEP_LINK_DEP (link);
rtx pro = DEP_PRO (dep);
if (INSN_PRIORITY_STATUS (pro) >= 0
if (insn == jump)
break;
- if (deps_list_empty_p (INSN_FORW_DEPS (insn)))
- add_back_forw_dep (jump, insn, REG_DEP_ANTI, DEP_ANTI);
+ if (sd_lists_empty_p (insn, SD_LIST_FORW))
+ {
+ dep_def _new_dep, *new_dep = &_new_dep;
+
+ init_dep (new_dep, insn, jump, REG_DEP_ANTI);
+ sd_add_dep (new_dep, false);
+ }
}
while (1);
- gcc_assert (!deps_list_empty_p (INSN_BACK_DEPS (jump)));
+ gcc_assert (!sd_lists_empty_p (jump, SD_LIST_BACK));
}
/* Return the NOTE_INSN_BASIC_BLOCK of BB. */
}
#ifdef ENABLE_CHECKING
-extern void debug_spec_status (ds_t);
-
-/* Dump information about the dependence status S. */
-void
-debug_spec_status (ds_t s)
-{
- FILE *f = stderr;
-
- if (s & BEGIN_DATA)
- fprintf (f, "BEGIN_DATA: %d; ", get_dep_weak (s, BEGIN_DATA));
- if (s & BE_IN_DATA)
- fprintf (f, "BE_IN_DATA: %d; ", get_dep_weak (s, BE_IN_DATA));
- if (s & BEGIN_CONTROL)
- fprintf (f, "BEGIN_CONTROL: %d; ", get_dep_weak (s, BEGIN_CONTROL));
- if (s & BE_IN_CONTROL)
- fprintf (f, "BE_IN_CONTROL: %d; ", get_dep_weak (s, BE_IN_CONTROL));
-
- if (s & HARD_DEP)
- fprintf (f, "HARD_DEP; ");
-
- if (s & DEP_TRUE)
- fprintf (f, "DEP_TRUE; ");
- if (s & DEP_ANTI)
- fprintf (f, "DEP_ANTI; ");
- if (s & DEP_OUTPUT)
- fprintf (f, "DEP_OUTPUT; ");
-
- fprintf (f, "\n");
-}
-
/* Helper function for check_cfg.
Return nonzero, if edge vector pointed to by EL has edge with TYPE in
its flags. */
gcc_assert (bb == 0);
}
-
-/* Perform a few consistency checks of flags in different data structures. */
-static void
-check_sched_flags (void)
-{
- unsigned int f = current_sched_info->flags;
-
- if (flag_sched_stalled_insns)
- gcc_assert (!(f & DO_SPECULATION));
- if (f & DO_SPECULATION)
- gcc_assert (!flag_sched_stalled_insns
- && spec_info
- && spec_info->mask);
-}
#endif /* ENABLE_CHECKING */
#endif /* INSN_SCHEDULING */
OSDN Git Service
