/* Instruction scheduling pass.
- Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999,
- 2000, 2001, 2002, 2003, 2004, 2005, 2006 Free Software Foundation, Inc.
+ Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 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)
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
compute_block_backward_dependences ().
Dependencies set up by memory references are treated in exactly the
- same way as other dependencies, by using LOG_LINKS backward
- dependences. LOG_LINKS are translated into INSN_DEPEND forward
- dependences for the purpose of forward list scheduling.
+ same way as other dependencies, by using insn backward dependences
+ INSN_BACK_DEPS. INSN_BACK_DEPS are translated into forward dependences
+ INSN_FORW_DEPS the purpose of forward list scheduling.
Having optimized the critical path, we may have also unduly
extended the lifetimes of some registers. If an operation requires
#include "target.h"
#include "output.h"
#include "params.h"
+#include "dbgcnt.h"
#ifdef INSN_SCHEDULING
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;
-/* Pointers to GLAT data. See init_glat for more information. */
-regset *glat_start, *glat_end;
-
/* Array used in {unlink, restore}_bb_notes. */
static rtx *bb_header = 0;
sufficient time has passed to make them ready. As time passes,
insns move from the "Queued" set to the "Ready" list.
- The "Pending" list (P) are the insns in the INSN_DEPEND of the unscheduled
- insns, i.e., those that are ready, queued, and pending.
+ The "Pending" list (P) are the insns in the INSN_FORW_DEPS of the
+ unscheduled insns, i.e., those that are ready, queued, and pending.
The "Queued" set (Q) is implemented by the variable `insn_queue'.
The "Ready" list (R) is implemented by the variables `ready' and
`n_ready'.
/* 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;
+
/* Forward declarations. */
-HAIFA_INLINE static int insn_cost1 (rtx, enum reg_note, rtx, rtx);
static int priority (rtx);
static int rank_for_schedule (const void *, const void *);
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 ready_remove_insn (rtx);
static int max_issue (struct ready_list *, int *, int);
-static rtx choose_ready (struct ready_list *);
+static int choose_ready (struct ready_list *, rtx *);
static void fix_inter_tick (rtx, rtx);
static int fix_tick_ready (rtx);
static void change_queue_index (rtx, int);
-static void resolve_dep (rtx, rtx);
/* The following functions are used to implement scheduling of data/control
speculative instructions. */
static void extend_all (rtx);
static void init_h_i_d (rtx);
static void generate_recovery_code (rtx);
-static void process_insn_depend_be_in_spec (rtx, 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);
static void fix_jump_move (rtx);
static void move_block_after_check (rtx);
static void move_succs (VEC(edge,gc) **, basic_block);
-static void init_glat (void);
-static void init_glat1 (basic_block);
-static void attach_life_info1 (basic_block);
-static void free_glat (void);
static void sched_remove_insn (rtx);
-static void clear_priorities (rtx);
+static void clear_priorities (rtx, rtx_vec_t *);
+static void calc_priorities (rtx_vec_t);
static void add_jump_dependencies (rtx, rtx);
-static void calc_priorities (rtx);
#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 */
static rtx last_scheduled_insn;
-/* Compute cost of executing INSN given the dependence LINK on the insn USED.
- This is the number of cycles between instruction issue and
- instruction results. */
+/* Cached cost of the instruction. Use below function to get cost of the
+ insn. -1 here means that the field is not initialized. */
+#define INSN_COST(INSN) (h_i_d[INSN_UID (INSN)].cost)
-HAIFA_INLINE int
-insn_cost (rtx insn, rtx link, rtx used)
-{
- return insn_cost1 (insn, used ? REG_NOTE_KIND (link) : REG_NOTE_MAX,
- link, used);
-}
-
-/* Compute cost of executing INSN given the dependence on the insn USED.
- If LINK is not NULL, then its REG_NOTE_KIND is used as a dependence type.
- Otherwise, dependence between INSN and USED is assumed to be of type
- DEP_TYPE. This function was introduced as a workaround for
- targetm.adjust_cost hook.
+/* Compute cost of executing INSN.
This is the number of cycles between instruction issue and
instruction results. */
-
-HAIFA_INLINE static int
-insn_cost1 (rtx insn, enum reg_note dep_type, rtx link, rtx used)
+HAIFA_INLINE int
+insn_cost (rtx insn)
{
int cost = INSN_COST (insn);
}
}
- /* In this case estimate cost without caring how insn is used. */
- if (used == 0)
- return cost;
+ return cost;
+}
+
+/* Compute cost of dependence LINK.
+ This is the number of cycles between instruction issue and
+ instruction results. */
+int
+dep_cost (dep_t link)
+{
+ rtx used = DEP_CON (link);
+ int cost;
/* A USE insn should never require the value used to be computed.
This allows the computation of a function's result and parameter
cost = 0;
else
{
- gcc_assert (!link || dep_type == REG_NOTE_KIND (link));
+ rtx insn = DEP_PRO (link);
+ enum reg_note dep_type = DEP_TYPE (link);
+
+ cost = insn_cost (insn);
if (INSN_CODE (insn) >= 0)
{
cost = insn_latency (insn, used);
}
- if (targetm.sched.adjust_cost_2)
- cost = targetm.sched.adjust_cost_2 (used, (int) dep_type, insn, cost);
- else
+ if (targetm.sched.adjust_cost != NULL)
{
- gcc_assert (link);
- if (targetm.sched.adjust_cost)
- cost = targetm.sched.adjust_cost (used, link, insn, cost);
+ /* This variable is used for backward compatibility with the
+ targets. */
+ rtx dep_cost_rtx_link = alloc_INSN_LIST (NULL_RTX, NULL_RTX);
+
+ /* Make it self-cycled, so that if some tries to walk over this
+ incomplete list he/she will be caught in an endless loop. */
+ 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_TYPE (link));
+
+ cost = targetm.sched.adjust_cost (used, dep_cost_rtx_link,
+ insn, cost);
+
+ free_INSN_LIST_node (dep_cost_rtx_link);
}
if (cost < 0)
return cost;
}
-/* Compute the priority number for INSN. */
+/* Return 'true' if DEP should be included in priority calculations. */
+static bool
+contributes_to_priority_p (dep_t dep)
+{
+ /* Critical path is meaningful in block boundaries only. */
+ if (!current_sched_info->contributes_to_priority (DEP_CON (dep),
+ DEP_PRO (dep)))
+ return false;
+
+ /* If flag COUNT_SPEC_IN_CRITICAL_PATH is set,
+ then speculative instructions will less likely be
+ scheduled. That is because the priority of
+ their producers will increase, and, thus, the
+ producers will more likely be scheduled, thus,
+ resolving the dependence. */
+ if ((current_sched_info->flags & DO_SPECULATION)
+ && !(spec_info->flags & COUNT_SPEC_IN_CRITICAL_PATH)
+ && (DEP_STATUS (dep) & SPECULATIVE))
+ return false;
+ return true;
+}
+
+/* Compute the priority number for INSN. */
static int
priority (rtx insn)
{
- rtx link;
-
if (! INSN_P (insn))
return 0;
- if (! INSN_PRIORITY_KNOWN (insn))
+ /* We should not be interested in priority of an already scheduled insn. */
+ gcc_assert (QUEUE_INDEX (insn) != QUEUE_SCHEDULED);
+
+ if (!INSN_PRIORITY_KNOWN (insn))
{
int this_priority = 0;
- if (INSN_DEPEND (insn) == 0)
- this_priority = insn_cost (insn, 0, 0);
+ 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
+ such insn to 0. */
+ this_priority = insn_cost (insn);
else
{
rtx prev_first, twin;
/* For recovery check instructions we calculate priority slightly
different than that of normal instructions. Instead of walking
- through INSN_DEPEND (check) list, we walk through INSN_DEPEND list
- of each instruction in the corresponding recovery block. */
+ through INSN_FORW_DEPS (check) list, we walk through
+ INSN_FORW_DEPS list of each instruction in the corresponding
+ recovery block. */
rec = RECOVERY_BLOCK (insn);
if (!rec || rec == EXIT_BLOCK_PTR)
do
{
- for (link = INSN_DEPEND (twin); link; link = XEXP (link, 1))
+ sd_iterator_def sd_it;
+ dep_t dep;
+
+ FOR_EACH_DEP (twin, SD_LIST_FORW, sd_it, dep)
{
rtx next;
int next_priority;
-
- next = XEXP (link, 0);
-
+
+ next = DEP_CON (dep);
+
if (BLOCK_FOR_INSN (next) != rec)
{
- /* Critical path is meaningful in block boundaries
- only. */
- if (! (*current_sched_info->contributes_to_priority)
- (next, insn)
- /* If flag COUNT_SPEC_IN_CRITICAL_PATH is set,
- then speculative instructions will less likely be
- scheduled. That is because the priority of
- their producers will increase, and, thus, the
- producers will more likely be scheduled, thus,
- resolving the dependence. */
- || ((current_sched_info->flags & DO_SPECULATION)
- && (DEP_STATUS (link) & SPECULATIVE)
- && !(spec_info->flags
- & COUNT_SPEC_IN_CRITICAL_PATH)))
+ int cost;
+
+ if (!contributes_to_priority_p (dep))
continue;
-
- next_priority = insn_cost1 (insn,
- twin == insn ?
- REG_NOTE_KIND (link) :
- REG_DEP_ANTI,
- twin == insn ? link : 0,
- next) + priority (next);
+
+ if (twin == insn)
+ cost = dep_cost (dep);
+ else
+ {
+ struct _dep _dep1, *dep1 = &_dep1;
+
+ init_dep (dep1, insn, next, REG_DEP_ANTI);
+
+ cost = dep_cost (dep1);
+ }
+
+ next_priority = cost + priority (next);
if (next_priority > this_priority)
this_priority = next_priority;
while (twin != prev_first);
}
INSN_PRIORITY (insn) = this_priority;
- INSN_PRIORITY_KNOWN (insn) = 1;
+ INSN_PRIORITY_STATUS (insn) = 1;
}
return INSN_PRIORITY (insn);
{
rtx tmp = *(const rtx *) y;
rtx tmp2 = *(const rtx *) x;
- rtx link;
- int tmp_class, tmp2_class, depend_count1, depend_count2;
+ int tmp_class, tmp2_class;
int val, priority_val, weight_val, info_val;
/* The insn in a schedule group should be issued the first. */
if (SCHED_GROUP_P (tmp) != SCHED_GROUP_P (tmp2))
return SCHED_GROUP_P (tmp2) ? 1 : -1;
+ /* Make sure that priority of TMP and TMP2 are initialized. */
+ gcc_assert (INSN_PRIORITY_KNOWN (tmp) && INSN_PRIORITY_KNOWN (tmp2));
+
/* Prefer insn with higher priority. */
priority_val = INSN_PRIORITY (tmp2) - INSN_PRIORITY (tmp);
/* 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. */
- link = find_insn_list (tmp, INSN_DEPEND (last_scheduled_insn));
- if (link == 0 || insn_cost (last_scheduled_insn, link, tmp) == 1)
+ dep1 = sd_find_dep_between (last_scheduled_insn, tmp, true);
+
+ if (dep1 == NULL || dep_cost (dep1) == 1)
tmp_class = 3;
- else if (REG_NOTE_KIND (link) == 0) /* Data dependence. */
+ else if (/* Data dependence. */
+ DEP_TYPE (dep1) == REG_DEP_TRUE)
tmp_class = 1;
else
tmp_class = 2;
- link = find_insn_list (tmp2, INSN_DEPEND (last_scheduled_insn));
- if (link == 0 || insn_cost (last_scheduled_insn, link, tmp2) == 1)
+ dep2 = sd_find_dep_between (last_scheduled_insn, tmp2, true);
+
+ if (dep2 == NULL || dep_cost (dep2) == 1)
tmp2_class = 3;
- else if (REG_NOTE_KIND (link) == 0) /* Data dependence. */
+ else if (/* Data dependence. */
+ DEP_TYPE (dep2) == REG_DEP_TRUE)
tmp2_class = 1;
else
tmp2_class = 2;
/* Prefer the insn which has more later insns that depend on it.
This gives the scheduler more freedom when scheduling later
instructions at the expense of added register pressure. */
- depend_count1 = 0;
- for (link = INSN_DEPEND (tmp); link; link = XEXP (link, 1))
- depend_count1++;
- depend_count2 = 0;
- for (link = INSN_DEPEND (tmp2); link; link = XEXP (link, 1))
- depend_count2++;
+ val = (sd_lists_size (tmp2, SD_LIST_FORW)
+ - sd_lists_size (tmp, SD_LIST_FORW));
- val = depend_count2 - depend_count1;
- if (val)
+ if (val != 0)
return val;
/* If insns are equally good, sort by INSN_LUID (original insn order),
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)
{
- rtx 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);
- gcc_assert (!LOG_LINKS (insn));
- gcc_assert (QUEUE_INDEX (insn) == QUEUE_NOWHERE);
+ gcc_assert (sd_lists_empty_p (insn, SD_LIST_BACK));
+ gcc_assert (QUEUE_INDEX (insn) == QUEUE_NOWHERE);
QUEUE_INDEX (insn) = QUEUE_SCHEDULED;
-
- /* Now we can free RESOLVED_DEPS list. */
- if (current_sched_info->flags & USE_DEPS_LIST)
- free_DEPS_LIST_list (&RESOLVED_DEPS (insn));
- else
- free_INSN_LIST_list (&RESOLVED_DEPS (insn));
-
+
gcc_assert (INSN_TICK (insn) >= MIN_TICK);
if (INSN_TICK (insn) > clock_var)
/* INSN has been prematurely moved from the queue to the ready list.
INSN_TICK (insn) = clock_var;
/* Update dependent instructions. */
- for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
+ for (sd_it = sd_iterator_start (insn, SD_LIST_FORW);
+ sd_iterator_cond (&sd_it, &dep);)
{
- rtx next = XEXP (link, 0);
+ rtx next = DEP_CON (dep);
- resolve_dep (next, insn);
+ /* 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 (XEXP (link, 1) == 0);
+ 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
}
/* See sched_analyze to see how these are handled. */
- if (NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_BEG
- && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_END)
+ if (NOTE_KIND (insn) != NOTE_INSN_EH_REGION_BEG
+ && NOTE_KIND (insn) != NOTE_INSN_EH_REGION_END)
{
/* Insert the note at the end of the notes list. */
PREV_INSN (insn) = note_list;
/* 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))
{
rtx insn;
rtx link;
+ rtx skip_insn;
q_ptr = NEXT_Q (q_ptr);
+ if (dbg_cnt (sched_insn) == false)
+ /* If debug counter is activated do not requeue insn next after
+ last_scheduled_insn. */
+ skip_insn = next_nonnote_insn (last_scheduled_insn);
+ else
+ skip_insn = NULL_RTX;
+
/* Add all pending insns that can be scheduled without stalls to the
ready list. */
for (link = insn_queue[q_ptr]; link; link = XEXP (link, 1))
See the comment in schedule_block for the rationale. */
if (!reload_completed
&& ready->n_ready > MAX_SCHED_READY_INSNS
- && !SCHED_GROUP_P (insn))
+ && !SCHED_GROUP_P (insn)
+ && insn != skip_insn)
{
if (sched_verbose >= 2)
fprintf (sched_dump, "requeued because ready full\n");
{
for ( ; prev_insn; prev_insn = PREV_INSN (prev_insn))
{
- rtx dep_link = 0;
- int dep_cost;
+ int cost;
+
+ if (prev_insn == current_sched_info->prev_head)
+ {
+ prev_insn = NULL;
+ break;
+ }
if (!NOTE_P (prev_insn))
{
- dep_link = find_insn_list (insn, INSN_DEPEND (prev_insn));
- if (dep_link)
+ dep_t dep;
+
+ dep = sd_find_dep_between (prev_insn, insn, true);
+
+ if (dep != NULL)
{
- dep_cost = insn_cost (prev_insn, dep_link, insn) ;
- if (targetm.sched.is_costly_dependence (prev_insn, insn,
- dep_link, dep_cost,
+ cost = dep_cost (dep);
+
+ if (targetm.sched.is_costly_dependence (dep, cost,
flag_sched_stalled_insns_dep - n_cycles))
return false;
}
gcc_assert (BB_END (bb) == last);
}
- set_block_for_insn (insn, bb);
+ df_insn_change_bb (insn, bb);
/* Update BB_END, if needed. */
if (BB_END (bb) == last)
/* The following function chooses insn from READY and modifies
*N_READY and READY. The following function is used only for first
- cycle multipass scheduling. */
-
-static rtx
-choose_ready (struct ready_list *ready)
+ cycle multipass scheduling.
+ Return:
+ -1 if cycle should be advanced,
+ 0 if INSN_PTR is set to point to the desirable insn,
+ 1 if choose_ready () should be restarted without advancing the cycle. */
+static int
+choose_ready (struct ready_list *ready, rtx *insn_ptr)
{
- int lookahead = 0;
+ int lookahead;
+
+ if (dbg_cnt (sched_insn) == false)
+ {
+ rtx insn;
+
+ insn = next_nonnote_insn (last_scheduled_insn);
+
+ if (QUEUE_INDEX (insn) == QUEUE_READY)
+ /* INSN is in the ready_list. */
+ {
+ ready_remove_insn (insn);
+ *insn_ptr = insn;
+ return 0;
+ }
+
+ /* INSN is in the queue. Advance cycle to move it to the ready list. */
+ return -1;
+ }
+
+ lookahead = 0;
if (targetm.sched.first_cycle_multipass_dfa_lookahead)
lookahead = targetm.sched.first_cycle_multipass_dfa_lookahead ();
if (lookahead <= 0 || SCHED_GROUP_P (ready_element (ready, 0)))
- return ready_remove_first (ready);
+ {
+ *insn_ptr = ready_remove_first (ready);
+ return 0;
+ }
else
{
/* Try to choose the better insn. */
}
insn = ready_element (ready, 0);
if (INSN_CODE (insn) < 0)
- return ready_remove_first (ready);
+ {
+ *insn_ptr = ready_remove_first (ready);
+ return 0;
+ }
if (spec_info
&& spec_info->flags & (PREFER_NON_DATA_SPEC
list. */
{
change_queue_index (insn, 1);
- return 0;
+ return 1;
}
max_points = ISSUE_POINTS (insn);
}
if (max_issue (ready, &index, max_points) == 0)
- return ready_remove_first (ready);
+ {
+ *insn_ptr = ready_remove_first (ready);
+ return 0;
+ }
else
- return ready_remove (ready, index);
+ {
+ *insn_ptr = ready_remove (ready, index);
+ return 0;
+ }
}
}
gcc_assert (head != tail || INSN_P (head));
- added_recovery_block_p = false;
+ haifa_recovery_bb_recently_added_p = false;
/* Debug info. */
if (sched_verbose)
";;\t\t before reload => truncated to %d insns\n", i);
}
- /* Delay all insns past it for 1 cycle. */
- while (i < ready.n_ready)
- queue_insn (ready_remove (&ready, i), 1);
+ /* Delay all insns past it for 1 cycle. If debug counter is
+ activated make an exception for the insn right after
+ last_scheduled_insn. */
+ {
+ rtx skip_insn;
+
+ if (dbg_cnt (sched_insn) == false)
+ skip_insn = next_nonnote_insn (last_scheduled_insn);
+ else
+ skip_insn = NULL_RTX;
+
+ while (i < ready.n_ready)
+ {
+ rtx insn;
+
+ insn = ready_remove (&ready, i);
+
+ if (insn != skip_insn)
+ queue_insn (insn, 1);
+ }
+ }
}
/* Now we can restore basic block notes and maintain precise cfg. */
there's nothing better to do (ready list is empty) but
there are still vacant dispatch slots in the current cycle. */
if (sched_verbose >= 6)
- fprintf(sched_dump,";;\t\tSecond chance\n");
+ fprintf (sched_dump,";;\t\tSecond chance\n");
memcpy (temp_state, curr_state, dfa_state_size);
if (early_queue_to_ready (temp_state, &ready))
ready_sort (&ready);
/* Select and remove the insn from the ready list. */
if (sort_p)
{
- insn = choose_ready (&ready);
- if (!insn)
+ int res;
+
+ insn = NULL_RTX;
+ res = choose_ready (&ready, &insn);
+
+ if (res < 0)
+ /* Finish cycle. */
+ break;
+ if (res > 0)
+ /* Restart choose_ready (). */
continue;
+
+ gcc_assert (insn != NULL_RTX);
}
else
insn = ready_remove_first (&ready);
generate_recovery_code (insn);
if (control_flow_insn_p (last_scheduled_insn)
- /* This is used to to switch basic blocks by request
+ /* This is used to switch basic blocks by request
from scheduler front-end (actually, sched-ebb.c only).
This is used to process blocks with single fallthru
edge. If succeeding block has jump, it [jump] will try
}
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
fix_inter_tick (NEXT_INSN (prev_head), last_scheduled_insn);
}
-#ifdef ENABLE_CHECKING
- /* After the reload the ia64 backend doesn't maintain BB_END, so
- if we want to check anything, better do it now.
- And it already clobbered previously scheduled code. */
- if (reload_completed)
- check_cfg (BB_HEAD (BLOCK_FOR_INSN (prev_head)), 0);
-#endif
-
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);
n_insn++;
(void) priority (insn);
- if (INSN_PRIORITY_KNOWN (insn))
- sched_max_insns_priority =
- MAX (sched_max_insns_priority, INSN_PRIORITY (insn));
+ gcc_assert (INSN_PRIORITY_KNOWN (insn));
+
+ sched_max_insns_priority = MAX (sched_max_insns_priority,
+ INSN_PRIORITY (insn));
}
current_sched_info->sched_max_insns_priority = sched_max_insns_priority;
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. */
init_alias_analysis ();
old_last_basic_block = 0;
- glat_start = 0;
- glat_end = 0;
extend_bb ();
- if (current_sched_info->flags & USE_GLAT)
- init_glat ();
-
/* Compute INSN_REG_WEIGHT for all blocks. We must do this before
removing death notes. */
FOR_EACH_BB_REVERSE (b)
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);
dfa_finish ();
free_dependency_caches ();
end_alias_analysis ();
- free_glat ();
if (targetm.sched.md_finish_global)
targetm.sched.md_finish_global (sched_dump, sched_verbose);
{
/* 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;
- rtx link;
+ sd_iterator_def sd_it;
+ dep_t dep;
tick = INSN_TICK (head);
gcc_assert (tick >= MIN_TICK);
INSN_TICK (head) = tick;
}
- for (link = INSN_DEPEND (head); link; link = XEXP (link, 1))
+ FOR_EACH_DEP (head, SD_LIST_RES_FORW, sd_it, dep)
{
rtx next;
- next = XEXP (link, 0);
+ 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;
- rtx 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 (!LOG_LINKS (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
{
- *ts &= ~SPECULATIVE & ~HARD_DEP;
-
- link = LOG_LINKS (next);
- if (link)
- {
- /* LOG_LINKS are maintained sorted.
- So if DEP_STATUS of the first dep is SPECULATIVE,
- than all other deps are speculative too. */
- if (DEP_STATUS (link) & SPECULATIVE)
- {
- /* 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 = DEP_STATUS (link) & SPECULATIVE;
- while ((link = XEXP (link, 1)))
- *ts = ds_merge (*ts, DEP_STATUS (link) & SPECULATIVE);
-
- if (dep_weak (*ts) < spec_info->weakness_cutoff)
- /* Too few points. */
- *ts = (*ts & ~SPECULATIVE) | HARD_DEP;
+ /* One of the NEXT's dependencies has been resolved.
+ Recalculate NEXT's status. */
+
+ *ts &= ~SPECULATIVE & ~HARD_DEP;
+
+ 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;
+
+ FOR_EACH_DEP (next, SD_LIST_BACK, sd_it, dep)
+ {
+ ds_t ds = DEP_STATUS (dep) & SPECULATIVE;
+
+ if (first_p)
+ {
+ first_p = false;
+
+ *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)
gcc_assert (*ts == old_ts
&& QUEUE_INDEX (next) == QUEUE_NOWHERE);
else if (current_sched_info->new_ready)
- *ts = current_sched_info->new_ready (next, *ts);
+ *ts = current_sched_info->new_ready (next, *ts);
- /* * if !(old_ts & SPECULATIVE) (e.g. HARD_DEP or 0), then insn might
+ /* * if !(old_ts & SPECULATIVE) (e.g. HARD_DEP or 0), then insn might
have its original pattern or changed (speculative) one. This is due
to changing ebb in region scheduling.
* But if (old_ts & SPECULATIVE), then we are pretty sure that insn
has speculative pattern.
-
+
We can't assert (!(*ts & HARD_DEP) || *ts == old_ts) here because
control-speculative NEXT could have been discarded by sched-rgn.c
(the same case as when discarded by can_schedule_ready_p ()). */
-
+
if ((*ts & SPECULATIVE)
- /* If (old_ts == *ts), then (old_ts & SPECULATIVE) and we don't
+ /* If (old_ts == *ts), then (old_ts & SPECULATIVE) and we don't
need to change anything. */
&& *ts != old_ts)
{
static int
fix_tick_ready (rtx next)
{
- rtx link;
int tick, delay;
- link = RESOLVED_DEPS (next);
-
- if (link)
+ if (!sd_lists_empty_p (next, SD_LIST_RES_BACK))
{
int full_p;
+ sd_iterator_def sd_it;
+ dep_t dep;
tick = INSN_TICK (next);
/* if tick is not equal to INVALID_TICK, then update
INSN_TICK of NEXT with the most recent resolved dependence
cost. Otherwise, recalculate from scratch. */
- full_p = tick == INVALID_TICK;
- do
- {
- rtx pro;
+ full_p = (tick == INVALID_TICK);
+
+ FOR_EACH_DEP (next, SD_LIST_RES_BACK, sd_it, dep)
+ {
+ rtx pro = DEP_PRO (dep);
int tick1;
- pro = XEXP (link, 0);
gcc_assert (INSN_TICK (pro) >= MIN_TICK);
- tick1 = INSN_TICK (pro) + insn_cost (pro, link, next);
+ tick1 = INSN_TICK (pro) + dep_cost (dep);
if (tick1 > tick)
tick = tick1;
+
+ if (!full_p)
+ break;
}
- while ((link = XEXP (link, 1)) && full_p);
}
else
tick = -1;
}
}
-/* INSN is being scheduled. Resolve the dependence between INSN and NEXT. */
-static void
-resolve_dep (rtx next, rtx insn)
-{
- rtx dep;
-
- INSN_DEP_COUNT (next)--;
-
- dep = remove_list_elem (insn, &LOG_LINKS (next));
- XEXP (dep, 1) = RESOLVED_DEPS (next);
- RESOLVED_DEPS (next) = dep;
-
- gcc_assert ((INSN_DEP_COUNT (next) != 0 || !LOG_LINKS (next))
- && (LOG_LINKS (next) || INSN_DEP_COUNT (next) == 0));
-}
-
/* Extend H_I_D data. */
static void
extend_h_i_d (void)
{
/* We use LUID 0 for the fake insn (UID 0) which holds dependencies for
pseudos which do not cross calls. */
- int new_max_uid = get_max_uid() + 1;
+ int new_max_uid = get_max_uid () + 1;
h_i_d = xrecalloc (h_i_d, new_max_uid, old_max_uid, sizeof (*h_i_d));
old_max_uid = new_max_uid;
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
QUEUE_INDEX (insn) = QUEUE_NOWHERE;
INSN_TICK (insn) = INVALID_TICK;
INTER_TICK (insn) = INVALID_TICK;
- find_insn_reg_weight1 (insn);
+ find_insn_reg_weight1 (insn);
}
/* Generates recovery code for INSN. */
/* Helper function.
Tries to add speculative dependencies of type FS between instructions
- in LINK list and TWIN. */
+ in deps_list L and TWIN. */
static void
-process_insn_depend_be_in_spec (rtx link, rtx twin, ds_t fs)
+process_insn_forw_deps_be_in_spec (rtx insn, rtx twin, ds_t fs)
{
- for (; link; link = XEXP (link, 1))
+ sd_iterator_def sd_it;
+ dep_t dep;
+
+ FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
{
ds_t ds;
rtx consumer;
- consumer = XEXP (link, 0);
+ consumer = DEP_CON (dep);
- ds = DEP_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, REG_NOTE_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;
- rtx link, twins = NULL;
+ sd_iterator_def sd_it;
+ dep_t dep;
+ rtx twins = NULL;
+ rtx_vec_t priorities_roots;
ts = TODO_SPEC (insn);
gcc_assert (!(ts & ~BE_IN_SPEC));
DONE_SPEC (insn) |= ts;
/* First we convert all simple checks to branchy. */
- for (link = LOG_LINKS (insn); link;)
+ for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
+ sd_iterator_cond (&sd_it, &dep);)
{
- rtx check;
-
- check = XEXP (link, 0);
+ rtx check = DEP_PRO (dep);
if (IS_SPECULATION_SIMPLE_CHECK_P (check))
{
create_check_block_twin (check, true);
- link = LOG_LINKS (insn);
+
+ /* Restart search. */
+ sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
}
else
- link = XEXP (link, 1);
+ /* Continue search. */
+ sd_iterator_next (&sd_it);
}
- clear_priorities (insn);
-
- do
+ priorities_roots = NULL;
+ clear_priorities (insn, &priorities_roots);
+
+ while (1)
{
- rtx link, check, twin;
+ rtx check, twin;
basic_block rec;
- link = LOG_LINKS (insn);
- gcc_assert (!(DEP_STATUS (link) & BEGIN_SPEC)
- && (DEP_STATUS (link) & BE_IN_SPEC)
- && (DEP_STATUS (link) & DEP_TYPES) == DEP_TRUE);
+ /* 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_STATUS (dep) & BEGIN_SPEC) == 0
+ && (DEP_STATUS (dep) & BE_IN_SPEC) != 0
+ && (DEP_STATUS (dep) & DEP_TYPES) == DEP_TRUE);
- check = XEXP (link, 0);
+ 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_rtx (PATTERN (insn)), BB_END (rec));
+
+ twin = emit_insn_before (copy_insn (PATTERN (insn)), BB_END (rec));
extend_global (twin);
- RESOLVED_DEPS (twin) = copy_DEPS_LIST_list (RESOLVED_DEPS (insn));
+ 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 = XEXP (link, 1);
- if (link)
- {
- check = XEXP (link, 0);
- if (BLOCK_FOR_INSN (check) == rec)
- break;
- }
- else
- break;
+ FOR_EACH_DEP (insn, SD_LIST_SPEC_BACK, sd_it, dep)
+ {
+ rtx pro = DEP_PRO (dep);
+
+ 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);
- process_insn_depend_be_in_spec (INSN_DEPEND (insn), twin, ts);
+ process_insn_forw_deps_be_in_spec (insn, twin, ts);
- for (link = LOG_LINKS (insn); link;)
+ /* Remove all dependencies between INSN and insns in REC. */
+ for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
+ sd_iterator_cond (&sd_it, &dep);)
{
- check = XEXP (link, 0);
+ rtx pro = DEP_PRO (dep);
- if (BLOCK_FOR_INSN (check) == rec)
- {
- delete_back_forw_dep (insn, check);
- link = LOG_LINKS (insn);
- }
+ if (BLOCK_FOR_INSN (pro) == rec)
+ sd_delete_dep (sd_it);
else
- link = XEXP (link, 1);
+ sd_iterator_next (&sd_it);
}
}
- while (LOG_LINKS (insn));
- /* We can't add the dependence between insn and twin earlier because
- that would make twin appear in the INSN_DEPEND (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). */
while (twins)
{
rtx twin;
twin = XEXP (twins, 0);
- calc_priorities (twin);
- 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);
twins = twin;
}
+
+ calc_priorities (priorities_roots);
+ VEC_free (rtx, heap, priorities_roots);
}
/* Extends and fills with zeros (only the new part) array pointed to by P. */
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 ();
create_check_block_twin (rtx insn, bool mutate_p)
{
basic_block rec;
- rtx label, check, twin, link;
+ rtx label, check, twin;
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)
{
- rtx link;
+ sd_iterator_def sd_it;
+ dep_t dep;
- for (link = RESOLVED_DEPS (insn); link; link = XEXP (link, 1))
- if (DEP_STATUS (link) & DEP_OUTPUT)
+ FOR_EACH_DEP (insn, SD_LIST_RES_BACK, sd_it, dep)
+ if ((DEP_STATUS (dep) & DEP_OUTPUT) != 0)
{
- RESOLVED_DEPS (check) =
- alloc_DEPS_LIST (XEXP (link, 0), RESOLVED_DEPS (check), DEP_TRUE);
- PUT_REG_NOTE_KIND (RESOLVED_DEPS (check), REG_DEP_TRUE);
+ struct _dep _dep2, *dep2 = &_dep2;
+
+ init_dep (dep2, DEP_PRO (dep), check, REG_DEP_TRUE);
+
+ sd_add_dep (dep2, true);
}
twin = emit_insn_after (ORIG_PAT (insn), BB_END (rec));
(TRUE | OUTPUT). */
}
- RESOLVED_DEPS (twin) = copy_DEPS_LIST_list (RESOLVED_DEPS (insn));
+ /* 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 (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
+
+ /* First, create dependencies between INSN's producers and CHECK & TWIN. */
+ FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
{
+ rtx pro = DEP_PRO (dep);
ds_t ds;
/* If BEGIN_DATA: [insn ~~TRUE~~> producer]:
twin ~~TRUE~~> producer
twin --ANTI--> check */
- ds = DEP_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, XEXP (link, 0), REG_NOTE_KIND (link), ds);
- add_back_forw_dep (twin, XEXP (link, 0), REG_NOTE_KIND (link), ds);
+ DEP_CON (new_dep) = twin;
+ sd_add_dep (new_dep, false);
}
- else
- add_back_forw_dep (check, XEXP (link, 0), REG_NOTE_KIND (link), ds);
}
- for (link = LOG_LINKS (insn); link;)
- if ((DEP_STATUS (link) & BEGIN_SPEC)
- || mutate_p)
- /* We can delete this dep only if we totally overcome it with
- BEGIN_SPECULATION. */
- {
- delete_back_forw_dep (insn, XEXP (link, 0));
- link = LOG_LINKS (insn);
- }
- else
- link = XEXP (link, 1);
+ /* 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_depend_be_in_spec (INSN_DEPEND (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
{
fprintf (spec_info->dump, ";;\t\tRemoved simple check : %s\n",
(*current_sched_info->print_insn) (insn, 0));
- for (link = INSN_DEPEND (insn); link; link = INSN_DEPEND (insn))
- delete_back_forw_dep (XEXP (link, 0), 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,
because it'll be done later in add_to_speculative_block. */
{
- clear_priorities (twin);
- calc_priorities (twin);
+ rtx_vec_t priorities_roots = NULL;
+
+ clear_priorities (twin, &priorities_roots);
+ calc_priorities (priorities_roots);
+ VEC_free (rtx, heap, priorities_roots);
}
}
static void
fix_recovery_deps (basic_block rec)
{
- rtx note, insn, link, jump, ready_list = 0;
+ rtx note, insn, jump, ready_list = 0;
bitmap_head in_ready;
+ rtx link;
bitmap_initialize (&in_ready, 0);
insn = PREV_INSN (insn);
do
- {
- for (link = INSN_DEPEND (insn); link;)
- {
- rtx consumer;
+ {
+ sd_iterator_def sd_it;
+ dep_t dep;
- consumer = XEXP (link, 0);
+ 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 (consumer, insn);
+ 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));
}
-
- link = INSN_DEPEND (insn);
}
else
{
- gcc_assert ((DEP_STATUS (link) & DEP_TYPES) == DEP_TRUE);
+ gcc_assert ((DEP_STATUS (dep) & DEP_TYPES) == DEP_TRUE);
- link = XEXP (link, 1);
+ sd_iterator_next (&sd_it);
}
}
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);
}
old_last_basic_block = last_basic_block;
- if (current_sched_info->flags & USE_GLAT)
- {
- glat_start = xrealloc (glat_start,
- last_basic_block * sizeof (*glat_start));
- glat_end = xrealloc (glat_end, last_basic_block * sizeof (*glat_end));
- }
-
/* The following is done to keep current_sched_info->next_tail non null. */
insn = BB_END (EXIT_BLOCK_PTR->prev_bb);
/* Don't emit a NOTE if it would end up before a BARRIER. */
&& !BARRIER_P (NEXT_INSN (insn))))
{
- emit_note_after (NOTE_INSN_DELETED, insn);
- /* Make insn to appear outside BB. */
+ rtx note = emit_note_after (NOTE_INSN_DELETED, insn);
+ /* Make insn appear outside BB. */
+ set_block_for_insn (note, NULL);
BB_END (EXIT_BLOCK_PTR->prev_bb) = insn;
}
}
void
add_block (basic_block bb, basic_block ebb)
{
- gcc_assert (current_sched_info->flags & DETACH_LIFE_INFO
- && bb->il.rtl->global_live_at_start == 0
- && bb->il.rtl->global_live_at_end == 0);
+ gcc_assert (current_sched_info->flags & NEW_BBS);
extend_bb ();
- glat_start[bb->index] = 0;
- glat_end[bb->index] = 0;
-
if (current_sched_info->add_block)
/* This changes only data structures of the front-end. */
current_sched_info->add_block (bb, ebb);
move_succs (&(jump_bb->succs), bb);
move_succs (&(jump_bb_next->succs), jump_bb);
move_succs (&t, jump_bb_next);
+
+ df_mark_solutions_dirty ();
if (current_sched_info->fix_recovery_cfg)
current_sched_info->fix_recovery_cfg
*succsp = 0;
}
-/* Initialize GLAT (global_live_at_{start, end}) structures.
- GLAT structures are used to substitute global_live_{start, end}
- regsets during scheduling. This is necessary to use such functions as
- split_block (), as they assume consistency of register live information. */
-static void
-init_glat (void)
-{
- basic_block bb;
-
- FOR_ALL_BB (bb)
- init_glat1 (bb);
-}
-
-/* Helper function for init_glat. */
-static void
-init_glat1 (basic_block bb)
-{
- gcc_assert (bb->il.rtl->global_live_at_start != 0
- && bb->il.rtl->global_live_at_end != 0);
-
- glat_start[bb->index] = bb->il.rtl->global_live_at_start;
- glat_end[bb->index] = bb->il.rtl->global_live_at_end;
-
- if (current_sched_info->flags & DETACH_LIFE_INFO)
- {
- bb->il.rtl->global_live_at_start = 0;
- bb->il.rtl->global_live_at_end = 0;
- }
-}
-
-/* Attach reg_live_info back to basic blocks.
- Also save regsets, that should not have been changed during scheduling,
- for checking purposes (see check_reg_live). */
-void
-attach_life_info (void)
-{
- basic_block bb;
-
- FOR_ALL_BB (bb)
- attach_life_info1 (bb);
-}
-
-/* Helper function for attach_life_info. */
-static void
-attach_life_info1 (basic_block bb)
-{
- gcc_assert (bb->il.rtl->global_live_at_start == 0
- && bb->il.rtl->global_live_at_end == 0);
-
- if (glat_start[bb->index])
- {
- gcc_assert (glat_end[bb->index]);
-
- bb->il.rtl->global_live_at_start = glat_start[bb->index];
- bb->il.rtl->global_live_at_end = glat_end[bb->index];
-
- /* Make them NULL, so they won't be freed in free_glat. */
- glat_start[bb->index] = 0;
- glat_end[bb->index] = 0;
-
-#ifdef ENABLE_CHECKING
- if (bb->index < NUM_FIXED_BLOCKS
- || current_sched_info->region_head_or_leaf_p (bb, 0))
- {
- glat_start[bb->index] = ALLOC_REG_SET (®_obstack);
- COPY_REG_SET (glat_start[bb->index],
- bb->il.rtl->global_live_at_start);
- }
-
- if (bb->index < NUM_FIXED_BLOCKS
- || current_sched_info->region_head_or_leaf_p (bb, 1))
- {
- glat_end[bb->index] = ALLOC_REG_SET (®_obstack);
- COPY_REG_SET (glat_end[bb->index], bb->il.rtl->global_live_at_end);
- }
-#endif
- }
- else
- {
- gcc_assert (!glat_end[bb->index]);
-
- bb->il.rtl->global_live_at_start = ALLOC_REG_SET (®_obstack);
- bb->il.rtl->global_live_at_end = ALLOC_REG_SET (®_obstack);
- }
-}
-
-/* Free GLAT information. */
-static void
-free_glat (void)
-{
-#ifdef ENABLE_CHECKING
- if (current_sched_info->flags & DETACH_LIFE_INFO)
- {
- basic_block bb;
-
- FOR_ALL_BB (bb)
- {
- if (glat_start[bb->index])
- FREE_REG_SET (glat_start[bb->index]);
- if (glat_end[bb->index])
- FREE_REG_SET (glat_end[bb->index]);
- }
- }
-#endif
-
- free (glat_start);
- free (glat_end);
-}
-
/* Remove INSN from the instruction stream.
INSN should have any dependencies. */
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);
}
-/* Clear priorities of all instructions, that are
- forward dependent on INSN. */
+/* Clear priorities of all instructions, that are forward dependent on INSN.
+ Store in vector pointed to by ROOTS_PTR insns on which priority () should
+ be invoked to initialize all cleared priorities. */
static void
-clear_priorities (rtx insn)
+clear_priorities (rtx insn, rtx_vec_t *roots_ptr)
{
- rtx link;
+ sd_iterator_def sd_it;
+ dep_t dep;
+ bool insn_is_root_p = true;
- for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
+ gcc_assert (QUEUE_INDEX (insn) != QUEUE_SCHEDULED);
+
+ FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
{
- rtx pro;
+ rtx pro = DEP_PRO (dep);
- pro = XEXP (link, 0);
- if (INSN_PRIORITY_KNOWN (pro))
+ if (INSN_PRIORITY_STATUS (pro) >= 0
+ && QUEUE_INDEX (insn) != QUEUE_SCHEDULED)
{
- INSN_PRIORITY_KNOWN (pro) = 0;
- clear_priorities (pro);
+ /* If DEP doesn't contribute to priority then INSN itself should
+ be added to priority roots. */
+ if (contributes_to_priority_p (dep))
+ insn_is_root_p = false;
+
+ INSN_PRIORITY_STATUS (pro) = -1;
+ clear_priorities (pro, roots_ptr);
}
}
+
+ if (insn_is_root_p)
+ VEC_safe_push (rtx, heap, *roots_ptr, insn);
}
/* Recompute priorities of instructions, whose priorities might have been
- changed due to changes in INSN. */
+ changed. ROOTS is a vector of instructions whose priority computation will
+ trigger initialization of all cleared priorities. */
static void
-calc_priorities (rtx insn)
+calc_priorities (rtx_vec_t roots)
{
- rtx link;
-
- for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
- {
- rtx pro;
+ int i;
+ rtx insn;
- pro = XEXP (link, 0);
- if (!INSN_PRIORITY_KNOWN (pro))
- {
- priority (pro);
- calc_priorities (pro);
- }
- }
+ for (i = 0; VEC_iterate (rtx, roots, i, insn); i++)
+ priority (insn);
}
if (insn == jump)
break;
- if (!INSN_DEPEND (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 (LOG_LINKS (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
- && (f & DETACH_LIFE_INFO)
- && spec_info
- && spec_info->mask);
- if (f & DETACH_LIFE_INFO)
- gcc_assert (f & USE_GLAT);
-}
-
-/* Check global_live_at_{start, end} regsets.
- If FATAL_P is TRUE, then abort execution at the first failure.
- Otherwise, print diagnostics to STDERR (this mode is for calling
- from debugger). */
-void
-check_reg_live (bool fatal_p)
-{
- basic_block bb;
-
- FOR_ALL_BB (bb)
- {
- int i;
-
- i = bb->index;
-
- if (glat_start[i])
- {
- bool b = bitmap_equal_p (bb->il.rtl->global_live_at_start,
- glat_start[i]);
-
- if (!b)
- {
- gcc_assert (!fatal_p);
-
- fprintf (stderr, ";; check_reg_live_at_start (%d) failed.\n", i);
- }
- }
-
- if (glat_end[i])
- {
- bool b = bitmap_equal_p (bb->il.rtl->global_live_at_end,
- glat_end[i]);
-
- if (!b)
- {
- gcc_assert (!fatal_p);
-
- fprintf (stderr, ";; check_reg_live_at_end (%d) failed.\n", i);
- }
- }
- }
-}
#endif /* ENABLE_CHECKING */
#endif /* INSN_SCHEDULING */
OSDN Git Service
