/* Swing Modulo Scheduling implementation.
- Copyright (C) 2004, 2005
+ Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010
Free Software Foundation, Inc.
Contributed by Ayal Zaks and Mustafa Hagog <zaks,mustafa@il.ibm.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, 59 Temple Place - Suite 330, Boston, MA
-02111-1307, USA. */
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
-#include "toplev.h"
+#include "diagnostic-core.h"
#include "rtl.h"
#include "tm_p.h"
#include "hard-reg-set.h"
#include "insn-config.h"
#include "insn-attr.h"
#include "except.h"
-#include "toplev.h"
#include "recog.h"
#include "sched-int.h"
#include "target.h"
#include "expr.h"
#include "params.h"
#include "gcov-io.h"
-#include "df.h"
#include "ddg.h"
+#include "timevar.h"
+#include "tree-pass.h"
+#include "dbgcnt.h"
+#include "df.h"
#ifdef INSN_SCHEDULING
perform modulo variable expansion for live ranges that span more than
II cycles (i.e. use register copies to prevent a def from overwriting
itself before reaching the use).
-*/
+ SMS works with countable loops (1) whose control part can be easily
+ decoupled from the rest of the loop and (2) whose loop count can
+ be easily adjusted. This is because we peel a constant number of
+ iterations into a prologue and epilogue for which we want to avoid
+ emitting the control part, and a kernel which is to iterate that
+ constant number of iterations less than the original loop. So the
+ control part should be a set of insns clearly identified and having
+ its own iv, not otherwise used in the loop (at-least for now), which
+ initializes a register before the loop to the number of iterations.
+ Currently SMS relies on the do-loop pattern to recognize such loops,
+ where (1) the control part comprises of all insns defining and/or
+ using a certain 'count' register and (2) the loop count can be
+ adjusted by modifying this register prior to the loop.
+ TODO: Rely on cfgloop analysis instead. */
\f
/* This page defines partial-schedule structures and functions for
modulo scheduling. */
#define PS_STAGE_COUNT(ps) ((PS_MAX_CYCLE (ps) - PS_MIN_CYCLE (ps) \
+ 1 + (ps)->ii - 1) / (ps)->ii)
-#define CFG_HOOKS cfg_layout_rtl_cfg_hooks
-
/* A single instruction in the partial schedule. */
struct ps_insn
{
ddg_ptr g; /* The DDG of the insns in the partial schedule. */
};
+/* We use this to record all the register replacements we do in
+ the kernel so we can undo SMS if it is not profitable. */
+struct undo_replace_buff_elem
+{
+ rtx insn;
+ rtx orig_reg;
+ rtx new_reg;
+ struct undo_replace_buff_elem *next;
+};
+
+
static partial_schedule_ptr create_partial_schedule (int ii, ddg_ptr, int history);
static void free_partial_schedule (partial_schedule_ptr);
static void reset_partial_schedule (partial_schedule_ptr, int new_ii);
void print_partial_schedule (partial_schedule_ptr, FILE *);
+static void verify_partial_schedule (partial_schedule_ptr, sbitmap);
static ps_insn_ptr ps_add_node_check_conflicts (partial_schedule_ptr,
ddg_node_ptr node, int cycle,
sbitmap must_precede,
sbitmap must_follow);
static void rotate_partial_schedule (partial_schedule_ptr, int);
+void set_row_column_for_ps (partial_schedule_ptr);
+static void ps_insert_empty_row (partial_schedule_ptr, int, sbitmap);
+static int compute_split_row (sbitmap, int, int, int, ddg_node_ptr);
+
\f
/* This page defines constants and structures for the modulo scheduling
driver. */
-/* As in haifa-sched.c: */
-/* issue_rate is the number of insns that can be scheduled in the same
- machine cycle. It can be defined in the config/mach/mach.h file,
- otherwise we set it to 1. */
-
-static int issue_rate;
-
-/* For printing statistics. */
-static FILE *stats_file;
-
-static int sms_order_nodes (ddg_ptr, int, int * result);
+static int sms_order_nodes (ddg_ptr, int, int *, int *);
static void set_node_sched_params (ddg_ptr);
-static partial_schedule_ptr sms_schedule_by_order (ddg_ptr, int, int,
- int *, FILE*);
-static void permute_partial_schedule (partial_schedule_ptr ps, rtx last);
-static void generate_prolog_epilog (partial_schedule_ptr, rtx, rtx, int);
-static void duplicate_insns_of_cycles (partial_schedule_ptr ps,
- int from_stage, int to_stage,
- int is_prolog);
-
+static partial_schedule_ptr sms_schedule_by_order (ddg_ptr, int, int, int *);
+static void permute_partial_schedule (partial_schedule_ptr, rtx);
+static void generate_prolog_epilog (partial_schedule_ptr, struct loop *,
+ rtx, rtx);
+static void duplicate_insns_of_cycles (partial_schedule_ptr,
+ int, int, int, rtx);
#define SCHED_ASAP(x) (((node_sched_params_ptr)(x)->aux.info)->asap)
#define SCHED_TIME(x) (((node_sched_params_ptr)(x)->aux.info)->time)
code in order to use sched_analyze() for computing the dependencies.
They are used when initializing the sched_info structure. */
static const char *
-sms_print_insn (rtx insn, int aligned ATTRIBUTE_UNUSED)
+sms_print_insn (const_rtx insn, int aligned ATTRIBUTE_UNUSED)
{
static char tmp[80];
return tmp;
}
-static int
-contributes_to_priority (rtx next, rtx insn)
-{
- return BLOCK_NUM (next) == BLOCK_NUM (insn);
-}
-
static void
compute_jump_reg_dependencies (rtx insn ATTRIBUTE_UNUSED,
regset cond_exec ATTRIBUTE_UNUSED,
{
}
-static struct sched_info sms_sched_info =
+static struct common_sched_info_def sms_common_sched_info;
+
+static struct sched_deps_info_def sms_sched_deps_info =
+ {
+ compute_jump_reg_dependencies,
+ NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
+ NULL,
+ 0, 0, 0
+ };
+
+static struct haifa_sched_info sms_sched_info =
{
NULL,
NULL,
NULL,
NULL,
sms_print_insn,
- contributes_to_priority,
- compute_jump_reg_dependencies,
+ NULL,
+ NULL, /* insn_finishes_block_p */
NULL, NULL,
NULL, NULL,
- 0, 0, 0
-};
+ 0, 0,
+ NULL, NULL, NULL,
+ 0
+};
-/* Return the register decremented and tested or zero if it is not a decrement
- and branch jump insn (similar to doloop_condition_get). */
+/* Given HEAD and TAIL which are the first and last insns in a loop;
+ return the register which controls the loop. Return zero if it has
+ more than one occurrence in the loop besides the control part or the
+ do-loop pattern is not of the form we expect. */
static rtx
-doloop_register_get (rtx insn, rtx *comp)
+doloop_register_get (rtx head ATTRIBUTE_UNUSED, rtx tail ATTRIBUTE_UNUSED)
{
- rtx pattern, cmp, inc, reg, condition;
+#ifdef HAVE_doloop_end
+ rtx reg, condition, insn, first_insn_not_to_check;
- if (!JUMP_P (insn))
+ if (!JUMP_P (tail))
return NULL_RTX;
- pattern = PATTERN (insn);
- /* The canonical doloop pattern we expect is:
-
- (parallel [(set (pc) (if_then_else (condition)
- (label_ref (label))
- (pc)))
- (set (reg) (plus (reg) (const_int -1)))
- (additional clobbers and uses)])
-
- where condition is further restricted to be
- (ne (reg) (const_int 1)). */
-
- if (GET_CODE (pattern) != PARALLEL)
+ /* TODO: Free SMS's dependence on doloop_condition_get. */
+ condition = doloop_condition_get (tail);
+ if (! condition)
return NULL_RTX;
- cmp = XVECEXP (pattern, 0, 0);
- inc = XVECEXP (pattern, 0, 1);
- /* Return the compare rtx. */
- *comp = cmp;
-
- /* Check for (set (reg) (something)). */
- if (GET_CODE (inc) != SET || ! REG_P (SET_DEST (inc)))
- return NULL_RTX;
-
- /* Extract loop counter register. */
- reg = SET_DEST (inc);
-
- /* Check if something = (plus (reg) (const_int -1)). */
- if (GET_CODE (SET_SRC (inc)) != PLUS
- || XEXP (SET_SRC (inc), 0) != reg
- || XEXP (SET_SRC (inc), 1) != constm1_rtx)
- return NULL_RTX;
-
- /* Check for (set (pc) (if_then_else (condition)
- (label_ref (label))
- (pc))). */
- if (GET_CODE (cmp) != SET
- || SET_DEST (cmp) != pc_rtx
- || GET_CODE (SET_SRC (cmp)) != IF_THEN_ELSE
- || GET_CODE (XEXP (SET_SRC (cmp), 1)) != LABEL_REF
- || XEXP (SET_SRC (cmp), 2) != pc_rtx)
- return NULL_RTX;
+ if (REG_P (XEXP (condition, 0)))
+ reg = XEXP (condition, 0);
+ else if (GET_CODE (XEXP (condition, 0)) == PLUS
+ && REG_P (XEXP (XEXP (condition, 0), 0)))
+ reg = XEXP (XEXP (condition, 0), 0);
+ else
+ gcc_unreachable ();
- /* Extract loop termination condition. */
- condition = XEXP (SET_SRC (cmp), 0);
+ /* Check that the COUNT_REG has no other occurrences in the loop
+ until the decrement. We assume the control part consists of
+ either a single (parallel) branch-on-count or a (non-parallel)
+ branch immediately preceded by a single (decrement) insn. */
+ first_insn_not_to_check = (GET_CODE (PATTERN (tail)) == PARALLEL ? tail
+ : PREV_INSN (tail));
- /* Check if condition = (ne (reg) (const_int 1)), which is more
- restrictive than the check in doloop_condition_get:
- if ((GET_CODE (condition) != GE && GET_CODE (condition) != NE)
- || GET_CODE (XEXP (condition, 1)) != CONST_INT). */
- if (GET_CODE (condition) != NE
- || XEXP (condition, 1) != const1_rtx)
- return NULL_RTX;
+ for (insn = head; insn != first_insn_not_to_check; insn = NEXT_INSN (insn))
+ if (reg_mentioned_p (reg, insn))
+ {
+ if (dump_file)
+ {
+ fprintf (dump_file, "SMS count_reg found ");
+ print_rtl_single (dump_file, reg);
+ fprintf (dump_file, " outside control in insn:\n");
+ print_rtl_single (dump_file, insn);
+ }
- if (XEXP (condition, 0) == reg)
- return reg;
+ return NULL_RTX;
+ }
+ return reg;
+#else
return NULL_RTX;
+#endif
}
/* Check if COUNT_REG is set to a constant in the PRE_HEADER block, so
{
rtx insn;
rtx head, tail;
- get_block_head_tail (pre_header->index, &head, &tail);
+
+ if (! pre_header)
+ return NULL_RTX;
+
+ get_ebb_head_tail (pre_header, pre_header, &head, &tail);
for (insn = tail; insn != PREV_INSN (head); insn = PREV_INSN (insn))
- if (INSN_P (insn) && single_set (insn) &&
+ if (NONDEBUG_INSN_P (insn) && single_set (insn) &&
rtx_equal_p (count_reg, SET_DEST (single_set (insn))))
{
rtx pat = single_set (insn);
- if (GET_CODE (SET_SRC (pat)) == CONST_INT)
+ if (CONST_INT_P (SET_SRC (pat)))
{
*count = INTVAL (SET_SRC (pat));
return insn;
static int
res_MII (ddg_ptr g)
{
- return (g->num_nodes / issue_rate);
+ if (targetm.sched.sms_res_mii)
+ return targetm.sched.sms_res_mii (g);
+
+ return ((g->num_nodes - g->num_debug) / issue_rate);
}
}
static void
-print_node_sched_params (FILE * dump_file, int num_nodes)
+print_node_sched_params (FILE *file, int num_nodes, ddg_ptr g)
{
int i;
+ if (! file)
+ return;
for (i = 0; i < num_nodes; i++)
{
node_sched_params_ptr nsp = &node_sched_params[i];
rtx reg_move = nsp->first_reg_move;
int j;
- fprintf (dump_file, "Node %d:\n", i);
- fprintf (dump_file, " asap = %d:\n", nsp->asap);
- fprintf (dump_file, " time = %d:\n", nsp->time);
- fprintf (dump_file, " nreg_moves = %d:\n", nsp->nreg_moves);
+ fprintf (file, "Node = %d; INSN = %d\n", i,
+ (INSN_UID (g->nodes[i].insn)));
+ fprintf (file, " asap = %d:\n", nsp->asap);
+ fprintf (file, " time = %d:\n", nsp->time);
+ fprintf (file, " nreg_moves = %d:\n", nsp->nreg_moves);
for (j = 0; j < nsp->nreg_moves; j++)
{
- fprintf (dump_file, " reg_move = ");
- print_rtl_single (dump_file, reg_move);
+ fprintf (file, " reg_move = ");
+ print_rtl_single (file, reg_move);
reg_move = PREV_INSN (reg_move);
}
}
}
-/* Calculate an upper bound for II. SMS should not schedule the loop if it
- requires more cycles than this bound. Currently set to the sum of the
- longest latency edge for each node. Reset based on experiments. */
-static int
-calculate_maxii (ddg_ptr g)
-{
- int i;
- int maxii = 0;
-
- for (i = 0; i < g->num_nodes; i++)
- {
- ddg_node_ptr u = &g->nodes[i];
- ddg_edge_ptr e;
- int max_edge_latency = 0;
-
- for (e = u->out; e; e = e->next_out)
- max_edge_latency = MAX (max_edge_latency, e->latency);
-
- maxii += max_edge_latency;
- }
- return maxii;
-}
-
-
-/* Given the partial schedule, generate register moves when the length
- of the register live range is more than ii; the number of moves is
- determined according to the following equation:
- SCHED_TIME (use) - SCHED_TIME (def) { 1 broken loop-carried
- nreg_moves = ----------------------------------- - { dependence.
- ii { 0 if not.
- This handles the modulo-variable-expansions (mve's) needed for the ps. */
-static void
-generate_reg_moves (partial_schedule_ptr ps)
+/*
+ Breaking intra-loop register anti-dependences:
+ Each intra-loop register anti-dependence implies a cross-iteration true
+ dependence of distance 1. Therefore, we can remove such false dependencies
+ and figure out if the partial schedule broke them by checking if (for a
+ true-dependence of distance 1): SCHED_TIME (def) < SCHED_TIME (use) and
+ if so generate a register move. The number of such moves is equal to:
+ SCHED_TIME (use) - SCHED_TIME (def) { 0 broken
+ nreg_moves = ----------------------------------- + 1 - { dependence.
+ ii { 1 if not.
+*/
+static struct undo_replace_buff_elem *
+generate_reg_moves (partial_schedule_ptr ps, bool rescan)
{
ddg_ptr g = ps->g;
int ii = ps->ii;
int i;
+ struct undo_replace_buff_elem *reg_move_replaces = NULL;
for (i = 0; i < g->num_nodes; i++)
{
{
int nreg_moves4e = (SCHED_TIME (e->dest) - SCHED_TIME (e->src)) / ii;
+ if (e->distance == 1)
+ nreg_moves4e = (SCHED_TIME (e->dest) - SCHED_TIME (e->src) + ii) / ii;
+
/* If dest precedes src in the schedule of the kernel, then dest
will read before src writes and we can save one reg_copy. */
if (SCHED_ROW (e->dest) == SCHED_ROW (e->src)
{
int dest_copy = (SCHED_TIME (e->dest) - SCHED_TIME (e->src)) / ii;
+ if (e->distance == 1)
+ dest_copy = (SCHED_TIME (e->dest) - SCHED_TIME (e->src) + ii) / ii;
+
if (SCHED_ROW (e->dest) == SCHED_ROW (e->src)
&& SCHED_COLUMN (e->dest) < SCHED_COLUMN (e->src))
dest_copy--;
/* Now generate the reg_moves, attaching relevant uses to them. */
SCHED_NREG_MOVES (u) = nreg_moves;
old_reg = prev_reg = copy_rtx (SET_DEST (single_set (u->insn)));
- last_reg_move = u->insn;
+ /* Insert the reg-moves right before the notes which precede
+ the insn they relates to. */
+ last_reg_move = u->first_note;
for (i_reg_move = 0; i_reg_move < nreg_moves; i_reg_move++)
{
- int i_use;
+ unsigned int i_use = 0;
rtx new_reg = gen_reg_rtx (GET_MODE (prev_reg));
rtx reg_move = gen_move_insn (new_reg, prev_reg);
+ sbitmap_iterator sbi;
- add_insn_before (reg_move, last_reg_move);
+ add_insn_before (reg_move, last_reg_move, NULL);
last_reg_move = reg_move;
if (!SCHED_FIRST_REG_MOVE (u))
SCHED_FIRST_REG_MOVE (u) = reg_move;
- EXECUTE_IF_SET_IN_SBITMAP (uses_of_defs[i_reg_move], 0, i_use,
- replace_rtx (g->nodes[i_use].insn, old_reg, new_reg));
+ EXECUTE_IF_SET_IN_SBITMAP (uses_of_defs[i_reg_move], 0, i_use, sbi)
+ {
+ struct undo_replace_buff_elem *rep;
+
+ rep = (struct undo_replace_buff_elem *)
+ xcalloc (1, sizeof (struct undo_replace_buff_elem));
+ rep->insn = g->nodes[i_use].insn;
+ rep->orig_reg = old_reg;
+ rep->new_reg = new_reg;
+
+ if (! reg_move_replaces)
+ reg_move_replaces = rep;
+ else
+ {
+ rep->next = reg_move_replaces;
+ reg_move_replaces = rep;
+ }
+
+ replace_rtx (g->nodes[i_use].insn, old_reg, new_reg);
+ if (rescan)
+ df_insn_rescan (g->nodes[i_use].insn);
+ }
prev_reg = new_reg;
}
+ sbitmap_vector_free (uses_of_defs);
+ }
+ return reg_move_replaces;
+}
+
+/* Free memory allocated for the undo buffer. */
+static void
+free_undo_replace_buff (struct undo_replace_buff_elem *reg_move_replaces)
+{
+
+ while (reg_move_replaces)
+ {
+ struct undo_replace_buff_elem *rep = reg_move_replaces;
+
+ reg_move_replaces = reg_move_replaces->next;
+ free (rep);
}
}
static void
normalize_sched_times (partial_schedule_ptr ps)
{
- int i;
- ddg_ptr g = ps->g;
+ int row;
int amount = PS_MIN_CYCLE (ps);
int ii = ps->ii;
+ ps_insn_ptr crr_insn;
- for (i = 0; i < g->num_nodes; i++)
- {
- ddg_node_ptr u = &g->nodes[i];
- int normalized_time = SCHED_TIME (u) - amount;
-
- if (normalized_time < 0)
- abort ();
-
- SCHED_TIME (u) = normalized_time;
- SCHED_ROW (u) = normalized_time % ii;
- SCHED_STAGE (u) = normalized_time / ii;
- }
+ for (row = 0; row < ii; row++)
+ for (crr_insn = ps->rows[row]; crr_insn; crr_insn = crr_insn->next_in_row)
+ {
+ ddg_node_ptr u = crr_insn->node;
+ int normalized_time = SCHED_TIME (u) - amount;
+
+ if (dump_file)
+ fprintf (dump_file, "crr_insn->node=%d, crr_insn->cycle=%d,\
+ min_cycle=%d\n", crr_insn->node->cuid, SCHED_TIME
+ (u), ps->min_cycle);
+ gcc_assert (SCHED_TIME (u) >= ps->min_cycle);
+ gcc_assert (SCHED_TIME (u) <= ps->max_cycle);
+ SCHED_TIME (u) = normalized_time;
+ SCHED_ROW (u) = normalized_time % ii;
+ SCHED_STAGE (u) = normalized_time / ii;
+ }
}
/* Set SCHED_COLUMN of each node according to its position in PS. */
PREV_INSN (last));
}
-/* Used to generate the prologue & epilogue. Duplicate the subset of
- nodes whose stages are between FROM_STAGE and TO_STAGE (inclusive
- of both), together with a prefix/suffix of their reg_moves. */
static void
duplicate_insns_of_cycles (partial_schedule_ptr ps, int from_stage,
- int to_stage, int for_prolog)
+ int to_stage, int for_prolog, rtx count_reg)
{
int row;
ps_insn_ptr ps_ij;
int j, i_reg_moves;
rtx reg_move = NULL_RTX;
+ /* Do not duplicate any insn which refers to count_reg as it
+ belongs to the control part.
+ TODO: This should be done by analyzing the control part of
+ the loop. */
+ if (reg_mentioned_p (count_reg, u_node->insn))
+ continue;
+
if (for_prolog)
{
/* SCHED_STAGE (u_node) >= from_stage == 0. Generate increasing
number of reg_moves starting with the second occurrence of
u_node, which is generated if its SCHED_STAGE <= to_stage. */
- i_reg_moves = to_stage - SCHED_STAGE (u_node);
+ i_reg_moves = to_stage - SCHED_STAGE (u_node) + 1;
i_reg_moves = MAX (i_reg_moves, 0);
i_reg_moves = MIN (i_reg_moves, SCHED_NREG_MOVES (u_node));
for (j = 0; j < i_reg_moves; j++, reg_move = NEXT_INSN (reg_move))
emit_insn (copy_rtx (PATTERN (reg_move)));
-
if (SCHED_STAGE (u_node) >= from_stage
&& SCHED_STAGE (u_node) <= to_stage)
duplicate_insn_chain (u_node->first_note, u_node->insn);
/* Generate the instructions (including reg_moves) for prolog & epilog. */
static void
-generate_prolog_epilog (partial_schedule_ptr ps, rtx orig_loop_beg,
- rtx orig_loop_end, int unknown_count)
+generate_prolog_epilog (partial_schedule_ptr ps, struct loop *loop,
+ rtx count_reg, rtx count_init)
{
int i;
int last_stage = PS_STAGE_COUNT (ps) - 1;
edge e;
- rtx c_reg = NULL_RTX;
- rtx cmp = NULL_RTX;
- rtx precond_jump = NULL_RTX;
- rtx precond_exit_label = NULL_RTX;
- rtx precond_exit_label_insn = NULL_RTX;
- rtx last_epilog_insn = NULL_RTX;
- rtx loop_exit_label = NULL_RTX;
- rtx loop_exit_label_insn = NULL_RTX;
- rtx orig_loop_bct = NULL_RTX;
-
- /* Loop header edge. */
- e = EDGE_PRED (ps->g->bb, 0);
- if (e->src == ps->g->bb)
- e = EDGE_PRED (ps->g->bb, 1);
/* Generate the prolog, inserting its insns on the loop-entry edge. */
start_sequence ();
- /* This is the place where we want to insert the precondition. */
- if (unknown_count)
- precond_jump = emit_note (NOTE_INSN_DELETED);
+ if (!count_init)
+ {
+ /* Generate instructions at the beginning of the prolog to
+ adjust the loop count by STAGE_COUNT. If loop count is constant
+ (count_init), this constant is adjusted by STAGE_COUNT in
+ generate_prolog_epilog function. */
+ rtx sub_reg = NULL_RTX;
+
+ sub_reg = expand_simple_binop (GET_MODE (count_reg), MINUS,
+ count_reg, GEN_INT (last_stage),
+ count_reg, 1, OPTAB_DIRECT);
+ gcc_assert (REG_P (sub_reg));
+ if (REGNO (sub_reg) != REGNO (count_reg))
+ emit_move_insn (count_reg, sub_reg);
+ }
for (i = 0; i < last_stage; i++)
- duplicate_insns_of_cycles (ps, 0, i, 1);
+ duplicate_insns_of_cycles (ps, 0, i, 1, count_reg);
+
+ /* Put the prolog on the entry edge. */
+ e = loop_preheader_edge (loop);
+ split_edge_and_insert (e, get_insns ());
- /* No need to call insert_insn_on_edge; we prepared the sequence. */
- e->insns.r = get_insns ();
end_sequence ();
/* Generate the epilog, inserting its insns on the loop-exit edge. */
start_sequence ();
for (i = 0; i < last_stage; i++)
- duplicate_insns_of_cycles (ps, i + 1, last_stage, 0);
+ duplicate_insns_of_cycles (ps, i + 1, last_stage, 0, count_reg);
- last_epilog_insn = emit_note (NOTE_INSN_DELETED);
+ /* Put the epilogue on the exit edge. */
+ gcc_assert (single_exit (loop));
+ e = single_exit (loop);
+ split_edge_and_insert (e, get_insns ());
+ end_sequence ();
+}
+
+/* Return true if all the BBs of the loop are empty except the
+ loop header. */
+static bool
+loop_single_full_bb_p (struct loop *loop)
+{
+ unsigned i;
+ basic_block *bbs = get_loop_body (loop);
- /* Emit the label where to put the original loop code. */
- if (unknown_count)
+ for (i = 0; i < loop->num_nodes ; i++)
{
- rtx label, cond;
+ rtx head, tail;
+ bool empty_bb = true;
- precond_exit_label = gen_label_rtx ();
- precond_exit_label_insn = emit_label (precond_exit_label);
+ if (bbs[i] == loop->header)
+ continue;
- /* Put the original loop code. */
- reorder_insns_nobb (orig_loop_beg, orig_loop_end, precond_exit_label_insn);
+ /* Make sure that basic blocks other than the header
+ have only notes labels or jumps. */
+ get_ebb_head_tail (bbs[i], bbs[i], &head, &tail);
+ for (; head != NEXT_INSN (tail); head = NEXT_INSN (head))
+ {
+ if (NOTE_P (head) || LABEL_P (head)
+ || (INSN_P (head) && (DEBUG_INSN_P (head) || JUMP_P (head))))
+ continue;
+ empty_bb = false;
+ break;
+ }
+
+ if (! empty_bb)
+ {
+ free (bbs);
+ return false;
+ }
+ }
+ free (bbs);
+ return true;
+}
- /* Change the label of the BCT to be the PRECOND_EXIT_LABEL. */
- orig_loop_bct = get_last_insn ();
- c_reg = doloop_register_get (orig_loop_bct, &cmp);
- label = XEXP (SET_SRC (cmp), 1);
- cond = XEXP (SET_SRC (cmp), 0);
+/* A simple loop from SMS point of view; it is a loop that is composed of
+ either a single basic block or two BBs - a header and a latch. */
+#define SIMPLE_SMS_LOOP_P(loop) ((loop->num_nodes < 3 ) \
+ && (EDGE_COUNT (loop->latch->preds) == 1) \
+ && (EDGE_COUNT (loop->latch->succs) == 1))
- if (! c_reg || GET_CODE (cond) != NE)
- abort ();
+/* Return true if the loop is in its canonical form and false if not.
+ i.e. SIMPLE_SMS_LOOP_P and have one preheader block, and single exit. */
+static bool
+loop_canon_p (struct loop *loop)
+{
+
+ if (loop->inner || !loop_outer (loop))
+ {
+ if (dump_file)
+ fprintf (dump_file, "SMS loop inner or !loop_outer\n");
+ return false;
+ }
- XEXP (label, 0) = precond_exit_label;
- JUMP_LABEL (orig_loop_bct) = precond_exit_label_insn;
- LABEL_NUSES (precond_exit_label_insn)++;
+ if (!single_exit (loop))
+ {
+ if (dump_file)
+ {
+ rtx insn = BB_END (loop->header);
- /* Generate the loop exit label. */
- loop_exit_label = gen_label_rtx ();
- loop_exit_label_insn = emit_label (loop_exit_label);
+ fprintf (dump_file, "SMS loop many exits ");
+ fprintf (dump_file, " %s %d (file, line)\n",
+ insn_file (insn), insn_line (insn));
+ }
+ return false;
}
- e = EDGE_SUCC (ps->g->bb, 0);
- if (e->dest == ps->g->bb)
- e = EDGE_SUCC (ps->g->bb, 1);
+ if (! SIMPLE_SMS_LOOP_P (loop) && ! loop_single_full_bb_p (loop))
+ {
+ if (dump_file)
+ {
+ rtx insn = BB_END (loop->header);
- e->insns.r = get_insns ();
- end_sequence ();
+ fprintf (dump_file, "SMS loop many BBs. ");
+ fprintf (dump_file, " %s %d (file, line)\n",
+ insn_file (insn), insn_line (insn));
+ }
+ return false;
+ }
- commit_edge_insertions ();
+ return true;
+}
- if (unknown_count)
+/* If there are more than one entry for the loop,
+ make it one by splitting the first entry edge and
+ redirecting the others to the new BB. */
+static void
+canon_loop (struct loop *loop)
+{
+ edge e;
+ edge_iterator i;
+
+ /* Avoid annoying special cases of edges going to exit
+ block. */
+ FOR_EACH_EDGE (e, i, EXIT_BLOCK_PTR->preds)
+ if ((e->flags & EDGE_FALLTHRU) && (EDGE_COUNT (e->src->succs) > 1))
+ split_edge (e);
+
+ if (loop->latch == loop->header
+ || EDGE_COUNT (loop->latch->succs) > 1)
{
- rtx precond_insns, epilog_jump, insert_after_insn;
- basic_block loop_exit_bb = BLOCK_FOR_INSN (loop_exit_label_insn);
- basic_block epilog_bb = BLOCK_FOR_INSN (last_epilog_insn);
- basic_block precond_bb = BLOCK_FOR_INSN (precond_jump);
- basic_block orig_loop_bb = BLOCK_FOR_INSN (precond_exit_label_insn);
- edge epilog_exit_edge = EDGE_SUCC (epilog_bb, 0);
-
- /* Do loop preconditioning to take care of cases were the loop count is
- less than the stage count. Update the CFG properly. */
- insert_after_insn = precond_jump;
- start_sequence ();
- c_reg = doloop_register_get (ps->g->closing_branch->insn, &cmp);
- emit_cmp_and_jump_insns (c_reg, GEN_INT (PS_STAGE_COUNT (ps)), LT, NULL,
- GET_MODE (c_reg), 1, precond_exit_label);
- precond_insns = get_insns ();
- precond_jump = get_last_insn ();
- end_sequence ();
- reorder_insns (precond_insns, precond_jump, insert_after_insn);
-
- /* Generate a subtract instruction at the beginning of the prolog to
- adjust the loop count by STAGE_COUNT. */
- emit_insn_after (gen_sub2_insn (c_reg, GEN_INT (PS_STAGE_COUNT (ps) - 1)),
- precond_jump);
- update_bb_for_insn (precond_bb);
- delete_insn (insert_after_insn);
-
- /* Update label info for the precondition jump. */
- JUMP_LABEL (precond_jump) = precond_exit_label_insn;
- LABEL_NUSES (precond_exit_label_insn)++;
-
- /* Update the CFG. */
- split_block (precond_bb, precond_jump);
- make_edge (precond_bb, orig_loop_bb, 0);
-
- /* Add a jump at end of the epilog to the LOOP_EXIT_LABEL to jump over the
- original loop copy and update the CFG. */
- epilog_jump = emit_jump_insn_after (gen_jump (loop_exit_label),
- last_epilog_insn);
- delete_insn (last_epilog_insn);
- JUMP_LABEL (epilog_jump) = loop_exit_label_insn;
- LABEL_NUSES (loop_exit_label_insn)++;
-
- redirect_edge_succ (epilog_exit_edge, loop_exit_bb);
- epilog_exit_edge->flags &= ~EDGE_FALLTHRU;
- emit_barrier_after (BB_END (epilog_bb));
+ FOR_EACH_EDGE (e, i, loop->header->preds)
+ if (e->src == loop->latch)
+ break;
+ split_edge (e);
}
}
-/* Return the line note insn preceding INSN, for debugging. Taken from
- emit-rtl.c. */
-static rtx
-find_line_note (rtx insn)
+/* Setup infos. */
+static void
+setup_sched_infos (void)
{
- for (; insn; insn = PREV_INSN (insn))
- if (NOTE_P (insn)
- && NOTE_LINE_NUMBER (insn) >= 0)
- break;
+ memcpy (&sms_common_sched_info, &haifa_common_sched_info,
+ sizeof (sms_common_sched_info));
+ sms_common_sched_info.sched_pass_id = SCHED_SMS_PASS;
+ common_sched_info = &sms_common_sched_info;
- return insn;
+ sched_deps_info = &sms_sched_deps_info;
+ current_sched_info = &sms_sched_info;
}
+/* Probability in % that the sms-ed loop rolls enough so that optimized
+ version may be entered. Just a guess. */
+#define PROB_SMS_ENOUGH_ITERATIONS 80
+
+/* Used to calculate the upper bound of ii. */
+#define MAXII_FACTOR 2
+
/* Main entry point, perform SMS scheduling on the loops of the function
that consist of single basic blocks. */
-void
-sms_schedule (FILE *dump_file)
+static void
+sms_schedule (void)
{
- static int passes = 0;
rtx insn;
ddg_ptr *g_arr, g;
- basic_block bb, pre_header = NULL;
int * node_order;
- int maxii;
- int i;
+ int maxii, max_asap;
+ loop_iterator li;
partial_schedule_ptr ps;
- int max_bb_index = last_basic_block;
- struct df *df;
-
- stats_file = dump_file;
+ basic_block bb = NULL;
+ struct loop *loop;
+ basic_block condition_bb = NULL;
+ edge latch_edge;
+ gcov_type trip_count = 0;
+
+ loop_optimizer_init (LOOPS_HAVE_PREHEADERS
+ | LOOPS_HAVE_RECORDED_EXITS);
+ if (number_of_loops () <= 1)
+ {
+ loop_optimizer_finalize ();
+ return; /* There are no loops to schedule. */
+ }
/* Initialize issue_rate. */
if (targetm.sched.issue_rate)
int temp = reload_completed;
reload_completed = 1;
- issue_rate = (*targetm.sched.issue_rate) ();
+ issue_rate = targetm.sched.issue_rate ();
reload_completed = temp;
}
else
issue_rate = 1;
/* Initialize the scheduler. */
- current_sched_info = &sms_sched_info;
- sched_init (NULL);
+ setup_sched_infos ();
+ haifa_sched_init ();
- /* Init Data Flow analysis, to be used in interloop dep calculation. */
- df = df_init ();
- df_analyze (df, 0, DF_ALL);
+ /* Allocate memory to hold the DDG array one entry for each loop.
+ We use loop->num as index into this array. */
+ g_arr = XCNEWVEC (ddg_ptr, number_of_loops ());
- /* Allocate memory to hold the DDG array. */
- g_arr = xcalloc (max_bb_index, sizeof (ddg_ptr));
+ if (dump_file)
+ {
+ fprintf (dump_file, "\n\nSMS analysis phase\n");
+ fprintf (dump_file, "===================\n\n");
+ }
/* Build DDGs for all the relevant loops and hold them in G_ARR
- indexed by the loop BB index. */
- FOR_EACH_BB (bb)
+ indexed by the loop index. */
+ FOR_EACH_LOOP (li, loop, 0)
{
rtx head, tail;
- rtx count_reg, comp;
- edge e, pre_header_edge;
+ rtx count_reg;
- if (bb->index < 0)
- continue;
+ /* For debugging. */
+ if (dbg_cnt (sms_sched_loop) == false)
+ {
+ if (dump_file)
+ fprintf (dump_file, "SMS reached max limit... \n");
- /* Check if bb has two successors, one being itself. */
- if (EDGE_COUNT (bb->succs) != 2)
- continue;
+ break;
+ }
- if (EDGE_SUCC (bb, 0)->dest != bb && EDGE_SUCC (bb, 1)->dest != bb)
- continue;
+ if (dump_file)
+ {
+ rtx insn = BB_END (loop->header);
- if ((EDGE_SUCC (bb, 0)->flags & EDGE_COMPLEX)
- || (EDGE_SUCC (bb, 1)->flags & EDGE_COMPLEX))
- continue;
+ fprintf (dump_file, "SMS loop num: %d, file: %s, line: %d\n",
+ loop->num, insn_file (insn), insn_line (insn));
- /* Check if bb has two predecessors, one being itself. */
- if (EDGE_COUNT (bb->preds) != 2)
- continue;
+ }
- if (EDGE_PRED (bb, 0)->src != bb && EDGE_PRED (bb, 1)->src != bb)
- continue;
+ if (! loop_canon_p (loop))
+ continue;
- if ((EDGE_PRED (bb, 0)->flags & EDGE_COMPLEX)
- || (EDGE_PRED (bb, 1)->flags & EDGE_COMPLEX))
+ if (! loop_single_full_bb_p (loop))
+ {
+ if (dump_file)
+ fprintf (dump_file, "SMS not loop_single_full_bb_p\n");
continue;
+ }
- /* For debugging. */
- if ((passes++ > MAX_SMS_LOOP_NUMBER) && (MAX_SMS_LOOP_NUMBER != -1))
- {
- if (dump_file)
- fprintf (dump_file, "SMS reached MAX_PASSES... \n");
- break;
- }
+ bb = loop->header;
- get_block_head_tail (bb->index, &head, &tail);
- pre_header_edge = EDGE_PRED (bb, 0);
- if (EDGE_PRED (bb, 0)->src != bb)
- pre_header_edge = EDGE_PRED (bb, 1);
+ get_ebb_head_tail (bb, bb, &head, &tail);
+ latch_edge = loop_latch_edge (loop);
+ gcc_assert (single_exit (loop));
+ if (single_exit (loop)->count)
+ trip_count = latch_edge->count / single_exit (loop)->count;
- /* Perfrom SMS only on loops that their average count is above threshold. */
- if (bb->count < pre_header_edge->count * SMS_LOOP_AVERAGE_COUNT_THRESHOLD)
- {
- if (stats_file)
- {
- rtx line_note = find_line_note (tail);
+ /* Perform SMS only on loops that their average count is above threshold. */
- if (line_note)
- {
- expanded_location xloc;
- NOTE_EXPANDED_LOCATION (xloc, line_note);
- fprintf (stats_file, "SMS bb %s %d (file, line)\n",
- xloc.file, xloc.line);
- }
- fprintf (stats_file, "SMS single-bb-loop\n");
+ if ( latch_edge->count
+ && (latch_edge->count < single_exit (loop)->count * SMS_LOOP_AVERAGE_COUNT_THRESHOLD))
+ {
+ if (dump_file)
+ {
+ fprintf (dump_file, " %s %d (file, line)\n",
+ insn_file (tail), insn_line (tail));
+ fprintf (dump_file, "SMS single-bb-loop\n");
if (profile_info && flag_branch_probabilities)
{
- fprintf (stats_file, "SMS loop-count ");
- fprintf (stats_file, HOST_WIDEST_INT_PRINT_DEC,
+ fprintf (dump_file, "SMS loop-count ");
+ fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
(HOST_WIDEST_INT) bb->count);
- fprintf (stats_file, "\n");
- fprintf (stats_file, "SMS preheader-count ");
- fprintf (stats_file, HOST_WIDEST_INT_PRINT_DEC,
- (HOST_WIDEST_INT) pre_header_edge->count);
- fprintf (stats_file, "\n");
- fprintf (stats_file, "SMS profile-sum-max ");
- fprintf (stats_file, HOST_WIDEST_INT_PRINT_DEC,
+ fprintf (dump_file, "\n");
+ fprintf (dump_file, "SMS trip-count ");
+ fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
+ (HOST_WIDEST_INT) trip_count);
+ fprintf (dump_file, "\n");
+ fprintf (dump_file, "SMS profile-sum-max ");
+ fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
(HOST_WIDEST_INT) profile_info->sum_max);
- fprintf (stats_file, "\n");
+ fprintf (dump_file, "\n");
}
}
continue;
}
/* Make sure this is a doloop. */
- if ( !(count_reg = doloop_register_get (tail, &comp)))
+ if ( !(count_reg = doloop_register_get (head, tail)))
+ {
+ if (dump_file)
+ fprintf (dump_file, "SMS doloop_register_get failed\n");
continue;
+ }
- e = EDGE_PRED (bb, 0);
- if (e->src == bb)
- pre_header = EDGE_PRED (bb, 1)->src;
- else
- pre_header = e->src;
-
- /* Don't handle BBs with calls or barriers, or !single_set insns. */
- for (insn = head; insn != NEXT_INSN (tail); insn = NEXT_INSN (insn))
- if (CALL_P (insn)
- || BARRIER_P (insn)
- || (INSN_P (insn) && !JUMP_P (insn)
- && !single_set (insn) && GET_CODE (PATTERN (insn)) != USE))
- break;
+ /* Don't handle BBs with calls or barriers, or !single_set insns,
+ or auto-increment insns (to avoid creating invalid reg-moves
+ for the auto-increment insns).
+ ??? Should handle auto-increment insns.
+ ??? Should handle insns defining subregs. */
+ for (insn = head; insn != NEXT_INSN (tail); insn = NEXT_INSN (insn))
+ {
+ rtx set;
+
+ if (CALL_P (insn)
+ || BARRIER_P (insn)
+ || (NONDEBUG_INSN_P (insn) && !JUMP_P (insn)
+ && !single_set (insn) && GET_CODE (PATTERN (insn)) != USE)
+ || (FIND_REG_INC_NOTE (insn, NULL_RTX) != 0)
+ || (INSN_P (insn) && (set = single_set (insn))
+ && GET_CODE (SET_DEST (set)) == SUBREG))
+ break;
+ }
if (insn != NEXT_INSN (tail))
{
- if (stats_file)
+ if (dump_file)
{
if (CALL_P (insn))
- fprintf (stats_file, "SMS loop-with-call\n");
+ fprintf (dump_file, "SMS loop-with-call\n");
else if (BARRIER_P (insn))
- fprintf (stats_file, "SMS loop-with-barrier\n");
- else
- fprintf (stats_file, "SMS loop-with-not-single-set\n");
- print_rtl_single (stats_file, insn);
+ fprintf (dump_file, "SMS loop-with-barrier\n");
+ else if (FIND_REG_INC_NOTE (insn, NULL_RTX) != 0)
+ fprintf (dump_file, "SMS reg inc\n");
+ else if ((NONDEBUG_INSN_P (insn) && !JUMP_P (insn)
+ && !single_set (insn) && GET_CODE (PATTERN (insn)) != USE))
+ fprintf (dump_file, "SMS loop-with-not-single-set\n");
+ else
+ fprintf (dump_file, "SMS loop with subreg in lhs\n");
+ print_rtl_single (dump_file, insn);
}
continue;
}
- if (! (g = create_ddg (bb, df, 0)))
+ if (! (g = create_ddg (bb, 0)))
{
- if (stats_file)
- fprintf (stats_file, "SMS doloop\n");
+ if (dump_file)
+ fprintf (dump_file, "SMS create_ddg failed\n");
continue;
}
- g_arr[bb->index] = g;
- }
-
- /* Release Data Flow analysis data structures. */
- df_finish (df);
+ g_arr[loop->num] = g;
+ if (dump_file)
+ fprintf (dump_file, "...OK\n");
- /* Go over the built DDGs and perfrom SMS for each one of them. */
- for (i = 0; i < max_bb_index; i++)
+ }
+ if (dump_file)
+ {
+ fprintf (dump_file, "\nSMS transformation phase\n");
+ fprintf (dump_file, "=========================\n\n");
+ }
+
+ /* We don't want to perform SMS on new loops - created by versioning. */
+ FOR_EACH_LOOP (li, loop, 0)
{
rtx head, tail;
- rtx count_reg, count_init, comp;
- edge pre_header_edge;
+ rtx count_reg, count_init;
int mii, rec_mii;
- int stage_count = 0;
+ unsigned stage_count = 0;
HOST_WIDEST_INT loop_count = 0;
- if (! (g = g_arr[i]))
+ if (! (g = g_arr[loop->num]))
continue;
if (dump_file)
- print_ddg (dump_file, g);
+ {
+ rtx insn = BB_END (loop->header);
- get_block_head_tail (g->bb->index, &head, &tail);
+ fprintf (dump_file, "SMS loop num: %d, file: %s, line: %d\n",
+ loop->num, insn_file (insn), insn_line (insn));
- pre_header_edge = EDGE_PRED (g->bb, 0);
- if (EDGE_PRED (g->bb, 0)->src != g->bb)
- pre_header_edge = EDGE_PRED (g->bb, 1);
+ print_ddg (dump_file, g);
+ }
- if (stats_file)
- {
- rtx line_note = find_line_note (tail);
+ get_ebb_head_tail (loop->header, loop->header, &head, &tail);
- if (line_note)
- {
- expanded_location xloc;
- NOTE_EXPANDED_LOCATION (xloc, line_note);
- fprintf (stats_file, "SMS bb %s %d (file, line)\n",
- xloc.file, xloc.line);
- }
- fprintf (stats_file, "SMS single-bb-loop\n");
+ latch_edge = loop_latch_edge (loop);
+ gcc_assert (single_exit (loop));
+ if (single_exit (loop)->count)
+ trip_count = latch_edge->count / single_exit (loop)->count;
+
+ if (dump_file)
+ {
+ fprintf (dump_file, " %s %d (file, line)\n",
+ insn_file (tail), insn_line (tail));
+ fprintf (dump_file, "SMS single-bb-loop\n");
if (profile_info && flag_branch_probabilities)
{
- fprintf (stats_file, "SMS loop-count ");
- fprintf (stats_file, HOST_WIDEST_INT_PRINT_DEC,
+ fprintf (dump_file, "SMS loop-count ");
+ fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
(HOST_WIDEST_INT) bb->count);
- fprintf (stats_file, "\n");
- fprintf (stats_file, "SMS preheader-count ");
- fprintf (stats_file, HOST_WIDEST_INT_PRINT_DEC,
- (HOST_WIDEST_INT) pre_header_edge->count);
- fprintf (stats_file, "\n");
- fprintf (stats_file, "SMS profile-sum-max ");
- fprintf (stats_file, HOST_WIDEST_INT_PRINT_DEC,
+ fprintf (dump_file, "\n");
+ fprintf (dump_file, "SMS profile-sum-max ");
+ fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
(HOST_WIDEST_INT) profile_info->sum_max);
- fprintf (stats_file, "\n");
+ fprintf (dump_file, "\n");
}
- fprintf (stats_file, "SMS doloop\n");
- fprintf (stats_file, "SMS built-ddg %d\n", g->num_nodes);
- fprintf (stats_file, "SMS num-loads %d\n", g->num_loads);
- fprintf (stats_file, "SMS num-stores %d\n", g->num_stores);
+ fprintf (dump_file, "SMS doloop\n");
+ fprintf (dump_file, "SMS built-ddg %d\n", g->num_nodes);
+ fprintf (dump_file, "SMS num-loads %d\n", g->num_loads);
+ fprintf (dump_file, "SMS num-stores %d\n", g->num_stores);
}
- /* Make sure this is a doloop. */
- if ( !(count_reg = doloop_register_get (tail, &comp)))
- abort ();
- /* This should be NULL_RTX if the count is unknown at compile time. */
- count_init = const_iteration_count (count_reg, pre_header, &loop_count);
+ /* In case of th loop have doloop register it gets special
+ handling. */
+ count_init = NULL_RTX;
+ if ((count_reg = doloop_register_get (head, tail)))
+ {
+ basic_block pre_header;
- if (stats_file && count_init)
+ pre_header = loop_preheader_edge (loop)->src;
+ count_init = const_iteration_count (count_reg, pre_header,
+ &loop_count);
+ }
+ gcc_assert (count_reg);
+
+ if (dump_file && count_init)
{
- fprintf (stats_file, "SMS const-doloop ");
- fprintf (stats_file, HOST_WIDEST_INT_PRINT_DEC, loop_count);
- fprintf (stats_file, "\n");
+ fprintf (dump_file, "SMS const-doloop ");
+ fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
+ loop_count);
+ fprintf (dump_file, "\n");
}
- node_order = (int *) xmalloc (sizeof (int) * g->num_nodes);
+ node_order = XNEWVEC (int, g->num_nodes);
mii = 1; /* Need to pass some estimate of mii. */
- rec_mii = sms_order_nodes (g, mii, node_order);
+ rec_mii = sms_order_nodes (g, mii, node_order, &max_asap);
mii = MAX (res_MII (g), rec_mii);
- maxii = (calculate_maxii (g) * SMS_MAX_II_FACTOR) / 100;
+ maxii = MAX (max_asap, MAXII_FACTOR * mii);
- if (stats_file)
- fprintf (stats_file, "SMS iis %d %d %d (rec_mii, mii, maxii)\n",
+ if (dump_file)
+ fprintf (dump_file, "SMS iis %d %d %d (rec_mii, mii, maxii)\n",
rec_mii, mii, maxii);
/* After sms_order_nodes and before sms_schedule_by_order, to copy over
ASAP. */
set_node_sched_params (g);
- ps = sms_schedule_by_order (g, mii, maxii, node_order, dump_file);
+ ps = sms_schedule_by_order (g, mii, maxii, node_order);
- if (ps)
+ if (ps){
stage_count = PS_STAGE_COUNT (ps);
+ gcc_assert(stage_count >= 1);
+ }
- if (stage_count == 0 || (count_init && (stage_count > loop_count)))
+ /* Stage count of 1 means that there is no interleaving between
+ iterations, let the scheduling passes do the job. */
+ if (stage_count <= 1
+ || (count_init && (loop_count <= stage_count))
+ || (flag_branch_probabilities && (trip_count <= stage_count)))
{
if (dump_file)
- fprintf (dump_file, "SMS failed... \n");
- if (stats_file)
- fprintf (stats_file, "SMS sched-failed %d\n", stage_count);
+ {
+ fprintf (dump_file, "SMS failed... \n");
+ fprintf (dump_file, "SMS sched-failed (stage-count=%d, loop-count=", stage_count);
+ fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, loop_count);
+ fprintf (dump_file, ", trip-count=");
+ fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, trip_count);
+ fprintf (dump_file, ")\n");
+ }
+ continue;
}
else
{
- rtx orig_loop_beg = NULL_RTX;
- rtx orig_loop_end = NULL_RTX;
+ struct undo_replace_buff_elem *reg_move_replaces;
- if (stats_file)
+ if (dump_file)
{
- fprintf (stats_file,
+ fprintf (dump_file,
"SMS succeeded %d %d (with ii, sc)\n", ps->ii,
stage_count);
print_partial_schedule (ps, dump_file);
g->closing_branch->cuid, PS_MIN_CYCLE (ps) - 1);
}
- /* Save the original loop if we want to do loop preconditioning in
- case the BCT count is not known. */
- if (! count_init)
- {
- int i;
-
- start_sequence ();
- /* Copy the original loop code before modifying it -
- so we can use it later. */
- for (i = 0; i < ps->g->num_nodes; i++)
- duplicate_insn_chain (ps->g->nodes[i].first_note,
- ps->g->nodes[i].insn);
-
- orig_loop_beg = get_insns ();
- orig_loop_end = get_last_insn ();
- end_sequence ();
- }
/* Set the stage boundaries. If the DDG is built with closing_branch_deps,
the closing_branch was scheduled and should appear in the last (ii-1)
row. Otherwise, we are free to schedule the branch, and we let nodes
that were scheduled at the first PS_MIN_CYCLE cycle appear in the first
- row; this should reduce stage_count to minimum. */
+ row; this should reduce stage_count to minimum.
+ TODO: Revisit the issue of scheduling the insns of the
+ control part relative to the branch when the control part
+ has more than one insn. */
normalize_sched_times (ps);
rotate_partial_schedule (ps, PS_MIN_CYCLE (ps));
set_columns_for_ps (ps);
+ canon_loop (loop);
+
+ /* case the BCT count is not known , Do loop-versioning */
+ if (count_reg && ! count_init)
+ {
+ rtx comp_rtx = gen_rtx_fmt_ee (GT, VOIDmode, count_reg,
+ GEN_INT(stage_count));
+ unsigned prob = (PROB_SMS_ENOUGH_ITERATIONS
+ * REG_BR_PROB_BASE) / 100;
+
+ loop_version (loop, comp_rtx, &condition_bb,
+ prob, prob, REG_BR_PROB_BASE - prob,
+ true);
+ }
+
+ /* Set new iteration count of loop kernel. */
+ if (count_reg && count_init)
+ SET_SRC (single_set (count_init)) = GEN_INT (loop_count
+ - stage_count + 1);
+
+ /* Now apply the scheduled kernel to the RTL of the loop. */
permute_partial_schedule (ps, g->closing_branch->first_note);
/* Mark this loop as software pipelined so the later
scheduling passes doesn't touch it. */
if (! flag_resched_modulo_sched)
g->bb->flags |= BB_DISABLE_SCHEDULE;
+ /* The life-info is not valid any more. */
+ df_set_bb_dirty (g->bb);
- generate_reg_moves (ps);
+ reg_move_replaces = generate_reg_moves (ps, true);
if (dump_file)
- print_node_sched_params (dump_file, g->num_nodes);
-
- /* Set new iteration count of loop kernel. */
- if (count_init)
- SET_SRC (single_set (count_init)) = GEN_INT (loop_count
- - stage_count + 1);
-
+ print_node_sched_params (dump_file, g->num_nodes, g);
/* Generate prolog and epilog. */
- generate_prolog_epilog (ps, orig_loop_beg, orig_loop_end,
- count_init ? 0 : 1);
+ generate_prolog_epilog (ps, loop, count_reg, count_init);
+
+ free_undo_replace_buff (reg_move_replaces);
}
+
free_partial_schedule (ps);
free (node_sched_params);
free (node_order);
free_ddg (g);
}
+ free (g_arr);
+
/* Release scheduler data, needed until now because of DFA. */
- sched_finish ();
+ haifa_sched_finish ();
+ loop_optimizer_finalize ();
}
/* The SMS scheduling algorithm itself
set to 0 to save compile time. */
#define DFA_HISTORY SMS_DFA_HISTORY
+/* A threshold for the number of repeated unsuccessful attempts to insert
+ an empty row, before we flush the partial schedule and start over. */
+#define MAX_SPLIT_NUM 10
+/* Given the partial schedule PS, this function calculates and returns the
+ cycles in which we can schedule the node with the given index I.
+ NOTE: Here we do the backtracking in SMS, in some special cases. We have
+ noticed that there are several cases in which we fail to SMS the loop
+ because the sched window of a node is empty due to tight data-deps. In
+ such cases we want to unschedule some of the predecessors/successors
+ until we get non-empty scheduling window. It returns -1 if the
+ scheduling window is empty and zero otherwise. */
+
+static int
+get_sched_window (partial_schedule_ptr ps, int *nodes_order, int i,
+ sbitmap sched_nodes, int ii, int *start_p, int *step_p, int *end_p)
+{
+ int start, step, end;
+ ddg_edge_ptr e;
+ int u = nodes_order [i];
+ ddg_node_ptr u_node = &ps->g->nodes[u];
+ sbitmap psp = sbitmap_alloc (ps->g->num_nodes);
+ sbitmap pss = sbitmap_alloc (ps->g->num_nodes);
+ sbitmap u_node_preds = NODE_PREDECESSORS (u_node);
+ sbitmap u_node_succs = NODE_SUCCESSORS (u_node);
+ int psp_not_empty;
+ int pss_not_empty;
+
+ /* 1. compute sched window for u (start, end, step). */
+ sbitmap_zero (psp);
+ sbitmap_zero (pss);
+ psp_not_empty = sbitmap_a_and_b_cg (psp, u_node_preds, sched_nodes);
+ pss_not_empty = sbitmap_a_and_b_cg (pss, u_node_succs, sched_nodes);
+
+ if (psp_not_empty && !pss_not_empty)
+ {
+ int early_start = INT_MIN;
+
+ end = INT_MAX;
+ for (e = u_node->in; e != 0; e = e->next_in)
+ {
+ ddg_node_ptr v_node = e->src;
+
+ if (dump_file)
+ {
+ fprintf (dump_file, "\nProcessing edge: ");
+ print_ddg_edge (dump_file, e);
+ fprintf (dump_file,
+ "\nScheduling %d (%d) in psp_not_empty,"
+ " checking p %d (%d): ", u_node->cuid,
+ INSN_UID (u_node->insn), v_node->cuid, INSN_UID
+ (v_node->insn));
+ }
+
+ if (TEST_BIT (sched_nodes, v_node->cuid))
+ {
+ int p_st = SCHED_TIME (v_node);
+
+ early_start =
+ MAX (early_start, p_st + e->latency - (e->distance * ii));
+
+ if (dump_file)
+ fprintf (dump_file,
+ "pred st = %d; early_start = %d; latency: %d",
+ p_st, early_start, e->latency);
+
+ if (e->data_type == MEM_DEP)
+ end = MIN (end, SCHED_TIME (v_node) + ii - 1);
+ }
+ else if (dump_file)
+ fprintf (dump_file, "the node is not scheduled\n");
+ }
+ start = early_start;
+ end = MIN (end, early_start + ii);
+ /* Schedule the node close to it's predecessors. */
+ step = 1;
+
+ if (dump_file)
+ fprintf (dump_file,
+ "\nScheduling %d (%d) in a window (%d..%d) with step %d\n",
+ u_node->cuid, INSN_UID (u_node->insn), start, end, step);
+ }
+
+ else if (!psp_not_empty && pss_not_empty)
+ {
+ int late_start = INT_MAX;
+
+ end = INT_MIN;
+ for (e = u_node->out; e != 0; e = e->next_out)
+ {
+ ddg_node_ptr v_node = e->dest;
+
+ if (dump_file)
+ {
+ fprintf (dump_file, "\nProcessing edge:");
+ print_ddg_edge (dump_file, e);
+ fprintf (dump_file,
+ "\nScheduling %d (%d) in pss_not_empty,"
+ " checking s %d (%d): ", u_node->cuid,
+ INSN_UID (u_node->insn), v_node->cuid, INSN_UID
+ (v_node->insn));
+ }
+
+ if (TEST_BIT (sched_nodes, v_node->cuid))
+ {
+ int s_st = SCHED_TIME (v_node);
+
+ late_start = MIN (late_start,
+ s_st - e->latency + (e->distance * ii));
+
+ if (dump_file)
+ fprintf (dump_file,
+ "succ st = %d; late_start = %d; latency = %d",
+ s_st, late_start, e->latency);
+
+ if (e->data_type == MEM_DEP)
+ end = MAX (end, SCHED_TIME (v_node) - ii + 1);
+ if (dump_file)
+ fprintf (dump_file, "end = %d\n", end);
+
+ }
+ else if (dump_file)
+ fprintf (dump_file, "the node is not scheduled\n");
+
+ }
+ start = late_start;
+ end = MAX (end, late_start - ii);
+ /* Schedule the node close to it's successors. */
+ step = -1;
+
+ if (dump_file)
+ fprintf (dump_file,
+ "\nScheduling %d (%d) in a window (%d..%d) with step %d\n",
+ u_node->cuid, INSN_UID (u_node->insn), start, end, step);
+
+ }
+
+ else if (psp_not_empty && pss_not_empty)
+ {
+ int early_start = INT_MIN;
+ int late_start = INT_MAX;
+ int count_preds = 0;
+ int count_succs = 0;
+
+ start = INT_MIN;
+ end = INT_MAX;
+ for (e = u_node->in; e != 0; e = e->next_in)
+ {
+ ddg_node_ptr v_node = e->src;
+
+ if (dump_file)
+ {
+ fprintf (dump_file, "\nProcessing edge:");
+ print_ddg_edge (dump_file, e);
+ fprintf (dump_file,
+ "\nScheduling %d (%d) in psp_pss_not_empty,"
+ " checking p %d (%d): ", u_node->cuid, INSN_UID
+ (u_node->insn), v_node->cuid, INSN_UID
+ (v_node->insn));
+ }
+
+ if (TEST_BIT (sched_nodes, v_node->cuid))
+ {
+ int p_st = SCHED_TIME (v_node);
+
+ early_start = MAX (early_start,
+ p_st + e->latency
+ - (e->distance * ii));
+
+ if (dump_file)
+ fprintf (dump_file,
+ "pred st = %d; early_start = %d; latency = %d",
+ p_st, early_start, e->latency);
+
+ if (e->type == TRUE_DEP && e->data_type == REG_DEP)
+ count_preds++;
+
+ if (e->data_type == MEM_DEP)
+ end = MIN (end, SCHED_TIME (v_node) + ii - 1);
+ }
+ else if (dump_file)
+ fprintf (dump_file, "the node is not scheduled\n");
+
+ }
+ for (e = u_node->out; e != 0; e = e->next_out)
+ {
+ ddg_node_ptr v_node = e->dest;
+
+ if (dump_file)
+ {
+ fprintf (dump_file, "\nProcessing edge:");
+ print_ddg_edge (dump_file, e);
+ fprintf (dump_file,
+ "\nScheduling %d (%d) in psp_pss_not_empty,"
+ " checking s %d (%d): ", u_node->cuid, INSN_UID
+ (u_node->insn), v_node->cuid, INSN_UID
+ (v_node->insn));
+ }
+
+ if (TEST_BIT (sched_nodes, v_node->cuid))
+ {
+ int s_st = SCHED_TIME (v_node);
+
+ late_start = MIN (late_start,
+ s_st - e->latency
+ + (e->distance * ii));
+
+ if (dump_file)
+ fprintf (dump_file,
+ "succ st = %d; late_start = %d; latency = %d",
+ s_st, late_start, e->latency);
+
+ if (e->type == TRUE_DEP && e->data_type == REG_DEP)
+ count_succs++;
+
+ if (e->data_type == MEM_DEP)
+ start = MAX (start, SCHED_TIME (v_node) - ii + 1);
+ }
+ else if (dump_file)
+ fprintf (dump_file, "the node is not scheduled\n");
+
+ }
+ start = MAX (start, early_start);
+ end = MIN (end, MIN (early_start + ii, late_start + 1));
+ step = 1;
+ /* If there are more successors than predecessors schedule the
+ node close to it's successors. */
+ if (count_succs >= count_preds)
+ {
+ int old_start = start;
+
+ start = end - 1;
+ end = old_start - 1;
+ step = -1;
+ }
+ }
+ else /* psp is empty && pss is empty. */
+ {
+ start = SCHED_ASAP (u_node);
+ end = start + ii;
+ step = 1;
+ }
+
+ *start_p = start;
+ *step_p = step;
+ *end_p = end;
+ sbitmap_free (psp);
+ sbitmap_free (pss);
+
+ if ((start >= end && step == 1) || (start <= end && step == -1))
+ {
+ if (dump_file)
+ fprintf (dump_file, "\nEmpty window: start=%d, end=%d, step=%d\n",
+ start, end, step);
+ return -1;
+ }
+
+ return 0;
+}
+
+/* Calculate MUST_PRECEDE/MUST_FOLLOW bitmaps of U_NODE; which is the
+ node currently been scheduled. At the end of the calculation
+ MUST_PRECEDE/MUST_FOLLOW contains all predecessors/successors of
+ U_NODE which are (1) already scheduled in the first/last row of
+ U_NODE's scheduling window, (2) whose dependence inequality with U
+ becomes an equality when U is scheduled in this same row, and (3)
+ whose dependence latency is zero.
+
+ The first and last rows are calculated using the following parameters:
+ START/END rows - The cycles that begins/ends the traversal on the window;
+ searching for an empty cycle to schedule U_NODE.
+ STEP - The direction in which we traverse the window.
+ II - The initiation interval. */
+
+static void
+calculate_must_precede_follow (ddg_node_ptr u_node, int start, int end,
+ int step, int ii, sbitmap sched_nodes,
+ sbitmap must_precede, sbitmap must_follow)
+{
+ ddg_edge_ptr e;
+ int first_cycle_in_window, last_cycle_in_window;
+
+ gcc_assert (must_precede && must_follow);
+
+ /* Consider the following scheduling window:
+ {first_cycle_in_window, first_cycle_in_window+1, ...,
+ last_cycle_in_window}. If step is 1 then the following will be
+ the order we traverse the window: {start=first_cycle_in_window,
+ first_cycle_in_window+1, ..., end=last_cycle_in_window+1},
+ or {start=last_cycle_in_window, last_cycle_in_window-1, ...,
+ end=first_cycle_in_window-1} if step is -1. */
+ first_cycle_in_window = (step == 1) ? start : end - step;
+ last_cycle_in_window = (step == 1) ? end - step : start;
+
+ sbitmap_zero (must_precede);
+ sbitmap_zero (must_follow);
+
+ if (dump_file)
+ fprintf (dump_file, "\nmust_precede: ");
+
+ /* Instead of checking if:
+ (SMODULO (SCHED_TIME (e->src), ii) == first_row_in_window)
+ && ((SCHED_TIME (e->src) + e->latency - (e->distance * ii)) ==
+ first_cycle_in_window)
+ && e->latency == 0
+ we use the fact that latency is non-negative:
+ SCHED_TIME (e->src) - (e->distance * ii) <=
+ SCHED_TIME (e->src) + e->latency - (e->distance * ii)) <=
+ first_cycle_in_window
+ and check only if
+ SCHED_TIME (e->src) - (e->distance * ii) == first_cycle_in_window */
+ for (e = u_node->in; e != 0; e = e->next_in)
+ if (TEST_BIT (sched_nodes, e->src->cuid)
+ && ((SCHED_TIME (e->src) - (e->distance * ii)) ==
+ first_cycle_in_window))
+ {
+ if (dump_file)
+ fprintf (dump_file, "%d ", e->src->cuid);
+
+ SET_BIT (must_precede, e->src->cuid);
+ }
+
+ if (dump_file)
+ fprintf (dump_file, "\nmust_follow: ");
+
+ /* Instead of checking if:
+ (SMODULO (SCHED_TIME (e->dest), ii) == last_row_in_window)
+ && ((SCHED_TIME (e->dest) - e->latency + (e->distance * ii)) ==
+ last_cycle_in_window)
+ && e->latency == 0
+ we use the fact that latency is non-negative:
+ SCHED_TIME (e->dest) + (e->distance * ii) >=
+ SCHED_TIME (e->dest) - e->latency + (e->distance * ii)) >=
+ last_cycle_in_window
+ and check only if
+ SCHED_TIME (e->dest) + (e->distance * ii) == last_cycle_in_window */
+ for (e = u_node->out; e != 0; e = e->next_out)
+ if (TEST_BIT (sched_nodes, e->dest->cuid)
+ && ((SCHED_TIME (e->dest) + (e->distance * ii)) ==
+ last_cycle_in_window))
+ {
+ if (dump_file)
+ fprintf (dump_file, "%d ", e->dest->cuid);
+
+ SET_BIT (must_follow, e->dest->cuid);
+ }
+
+ if (dump_file)
+ fprintf (dump_file, "\n");
+}
+
+/* Return 1 if U_NODE can be scheduled in CYCLE. Use the following
+ parameters to decide if that's possible:
+ PS - The partial schedule.
+ U - The serial number of U_NODE.
+ NUM_SPLITS - The number of row splits made so far.
+ MUST_PRECEDE - The nodes that must precede U_NODE. (only valid at
+ the first row of the scheduling window)
+ MUST_FOLLOW - The nodes that must follow U_NODE. (only valid at the
+ last row of the scheduling window) */
+
+static bool
+try_scheduling_node_in_cycle (partial_schedule_ptr ps, ddg_node_ptr u_node,
+ int u, int cycle, sbitmap sched_nodes,
+ int *num_splits, sbitmap must_precede,
+ sbitmap must_follow)
+{
+ ps_insn_ptr psi;
+ bool success = 0;
+
+ verify_partial_schedule (ps, sched_nodes);
+ psi = ps_add_node_check_conflicts (ps, u_node, cycle,
+ must_precede, must_follow);
+ if (psi)
+ {
+ SCHED_TIME (u_node) = cycle;
+ SET_BIT (sched_nodes, u);
+ success = 1;
+ *num_splits = 0;
+ if (dump_file)
+ fprintf (dump_file, "Scheduled w/o split in %d\n", cycle);
+
+ }
+
+ return success;
+}
+
+/* This function implements the scheduling algorithm for SMS according to the
+ above algorithm. */
static partial_schedule_ptr
-sms_schedule_by_order (ddg_ptr g, int mii, int maxii, int *nodes_order, FILE *dump_file)
+sms_schedule_by_order (ddg_ptr g, int mii, int maxii, int *nodes_order)
{
int ii = mii;
- int i, c, success;
- int try_again_with_larger_ii = true;
+ int i, c, success, num_splits = 0;
+ int flush_and_start_over = true;
int num_nodes = g->num_nodes;
- ddg_edge_ptr e;
int start, end, step; /* Place together into one struct? */
sbitmap sched_nodes = sbitmap_alloc (num_nodes);
sbitmap must_precede = sbitmap_alloc (num_nodes);
sbitmap must_follow = sbitmap_alloc (num_nodes);
+ sbitmap tobe_scheduled = sbitmap_alloc (num_nodes);
partial_schedule_ptr ps = create_partial_schedule (ii, g, DFA_HISTORY);
- while (try_again_with_larger_ii && ii < maxii)
+ sbitmap_ones (tobe_scheduled);
+ sbitmap_zero (sched_nodes);
+
+ while (flush_and_start_over && (ii < maxii))
{
+
if (dump_file)
- fprintf(dump_file, "Starting with ii=%d\n", ii);
- try_again_with_larger_ii = false;
+ fprintf (dump_file, "Starting with ii=%d\n", ii);
+ flush_and_start_over = false;
sbitmap_zero (sched_nodes);
for (i = 0; i < num_nodes; i++)
{
int u = nodes_order[i];
- ddg_node_ptr u_node = &g->nodes[u];
- sbitmap u_node_preds = NODE_PREDECESSORS (u_node);
- sbitmap u_node_succs = NODE_SUCCESSORS (u_node);
- int psp_not_empty;
- int pss_not_empty;
+ ddg_node_ptr u_node = &ps->g->nodes[u];
rtx insn = u_node->insn;
- if (!INSN_P (insn))
- continue;
+ if (!NONDEBUG_INSN_P (insn))
+ {
+ RESET_BIT (tobe_scheduled, u);
+ continue;
+ }
if (JUMP_P (insn)) /* Closing branch handled later. */
+ {
+ RESET_BIT (tobe_scheduled, u);
+ continue;
+ }
+
+ if (TEST_BIT (sched_nodes, u))
continue;
- /* 1. compute sched window for u (start, end, step). */
- psp_not_empty = sbitmap_any_common_bits (u_node_preds, sched_nodes);
- pss_not_empty = sbitmap_any_common_bits (u_node_succs, sched_nodes);
+ /* Try to get non-empty scheduling window. */
+ success = 0;
+ if (get_sched_window (ps, nodes_order, i, sched_nodes, ii, &start,
+ &step, &end) == 0)
+ {
+ if (dump_file)
+ fprintf (dump_file, "\nTrying to schedule node %d \
+ INSN = %d in (%d .. %d) step %d\n", u, (INSN_UID
+ (g->nodes[u].insn)), start, end, step);
+
+ gcc_assert ((step > 0 && start < end)
+ || (step < 0 && start > end));
+
+ calculate_must_precede_follow (u_node, start, end, step, ii,
+ sched_nodes, must_precede,
+ must_follow);
+
+ for (c = start; c != end; c += step)
+ {
+ sbitmap tmp_precede = NULL;
+ sbitmap tmp_follow = NULL;
+
+ if (c == start)
+ {
+ if (step == 1)
+ tmp_precede = must_precede;
+ else /* step == -1. */
+ tmp_follow = must_follow;
+ }
+ if (c == end - step)
+ {
+ if (step == 1)
+ tmp_follow = must_follow;
+ else /* step == -1. */
+ tmp_precede = must_precede;
+ }
+
+ success =
+ try_scheduling_node_in_cycle (ps, u_node, u, c,
+ sched_nodes,
+ &num_splits, tmp_precede,
+ tmp_follow);
+ if (success)
+ break;
+ }
+
+ verify_partial_schedule (ps, sched_nodes);
+ }
+ if (!success)
+ {
+ int split_row;
+
+ if (ii++ == maxii)
+ break;
+
+ if (num_splits >= MAX_SPLIT_NUM)
+ {
+ num_splits = 0;
+ flush_and_start_over = true;
+ verify_partial_schedule (ps, sched_nodes);
+ reset_partial_schedule (ps, ii);
+ verify_partial_schedule (ps, sched_nodes);
+ break;
+ }
+
+ num_splits++;
+ /* The scheduling window is exclusive of 'end'
+ whereas compute_split_window() expects an inclusive,
+ ordered range. */
+ if (step == 1)
+ split_row = compute_split_row (sched_nodes, start, end - 1,
+ ps->ii, u_node);
+ else
+ split_row = compute_split_row (sched_nodes, end + 1, start,
+ ps->ii, u_node);
+
+ ps_insert_empty_row (ps, split_row, sched_nodes);
+ i--; /* Go back and retry node i. */
+
+ if (dump_file)
+ fprintf (dump_file, "num_splits=%d\n", num_splits);
+ }
- if (psp_not_empty && !pss_not_empty)
- {
- int early_start = 0;
+ /* ??? If (success), check register pressure estimates. */
+ } /* Continue with next node. */
+ } /* While flush_and_start_over. */
+ if (ii >= maxii)
+ {
+ free_partial_schedule (ps);
+ ps = NULL;
+ }
+ else
+ gcc_assert (sbitmap_equal (tobe_scheduled, sched_nodes));
- end = INT_MAX;
- for (e = u_node->in; e != 0; e = e->next_in)
- {
- ddg_node_ptr v_node = e->src;
- if (TEST_BIT (sched_nodes, v_node->cuid))
- {
- int node_st = SCHED_TIME (v_node)
- + e->latency - (e->distance * ii);
+ sbitmap_free (sched_nodes);
+ sbitmap_free (must_precede);
+ sbitmap_free (must_follow);
+ sbitmap_free (tobe_scheduled);
- early_start = MAX (early_start, node_st);
+ return ps;
+}
- if (e->data_type == MEM_DEP)
- end = MIN (end, SCHED_TIME (v_node) + ii - 1);
- }
- }
- start = early_start;
- end = MIN (end, early_start + ii);
- step = 1;
- }
+/* This function inserts a new empty row into PS at the position
+ according to SPLITROW, keeping all already scheduled instructions
+ intact and updating their SCHED_TIME and cycle accordingly. */
+static void
+ps_insert_empty_row (partial_schedule_ptr ps, int split_row,
+ sbitmap sched_nodes)
+{
+ ps_insn_ptr crr_insn;
+ ps_insn_ptr *rows_new;
+ int ii = ps->ii;
+ int new_ii = ii + 1;
+ int row;
- else if (!psp_not_empty && pss_not_empty)
- {
- int late_start = INT_MAX;
+ verify_partial_schedule (ps, sched_nodes);
- end = INT_MIN;
- for (e = u_node->out; e != 0; e = e->next_out)
- {
- ddg_node_ptr v_node = e->dest;
- if (TEST_BIT (sched_nodes, v_node->cuid))
- {
- late_start = MIN (late_start,
- SCHED_TIME (v_node) - e->latency
- + (e->distance * ii));
- if (e->data_type == MEM_DEP)
- end = MAX (end, SCHED_TIME (v_node) - ii + 1);
- }
- }
- start = late_start;
- end = MAX (end, late_start - ii);
- step = -1;
- }
+ /* We normalize sched_time and rotate ps to have only non-negative sched
+ times, for simplicity of updating cycles after inserting new row. */
+ split_row -= ps->min_cycle;
+ split_row = SMODULO (split_row, ii);
+ if (dump_file)
+ fprintf (dump_file, "split_row=%d\n", split_row);
- else if (psp_not_empty && pss_not_empty)
- {
- int early_start = 0;
- int late_start = INT_MAX;
+ normalize_sched_times (ps);
+ rotate_partial_schedule (ps, ps->min_cycle);
- start = INT_MIN;
- end = INT_MAX;
- for (e = u_node->in; e != 0; e = e->next_in)
- {
- ddg_node_ptr v_node = e->src;
-
- if (TEST_BIT (sched_nodes, v_node->cuid))
- {
- early_start = MAX (early_start,
- SCHED_TIME (v_node) + e->latency
- - (e->distance * ii));
- if (e->data_type == MEM_DEP)
- end = MIN (end, SCHED_TIME (v_node) + ii - 1);
- }
- }
- for (e = u_node->out; e != 0; e = e->next_out)
- {
- ddg_node_ptr v_node = e->dest;
-
- if (TEST_BIT (sched_nodes, v_node->cuid))
- {
- late_start = MIN (late_start,
- SCHED_TIME (v_node) - e->latency
- + (e->distance * ii));
- if (e->data_type == MEM_DEP)
- start = MAX (start, SCHED_TIME (v_node) - ii + 1);
- }
- }
- start = MAX (start, early_start);
- end = MIN (end, MIN (early_start + ii, late_start + 1));
- step = 1;
- }
- else /* psp is empty && pss is empty. */
- {
- start = SCHED_ASAP (u_node);
- end = start + ii;
- step = 1;
- }
+ rows_new = (ps_insn_ptr *) xcalloc (new_ii, sizeof (ps_insn_ptr));
+ for (row = 0; row < split_row; row++)
+ {
+ rows_new[row] = ps->rows[row];
+ ps->rows[row] = NULL;
+ for (crr_insn = rows_new[row];
+ crr_insn; crr_insn = crr_insn->next_in_row)
+ {
+ ddg_node_ptr u = crr_insn->node;
+ int new_time = SCHED_TIME (u) + (SCHED_TIME (u) / ii);
- /* 2. Try scheduling u in window. */
- if (dump_file)
- fprintf(dump_file, "Trying to schedule node %d in (%d .. %d) step %d\n",
- u, start, end, step);
-
- /* use must_follow & must_precede bitmaps to determine order
- of nodes within the cycle. */
- sbitmap_zero (must_precede);
- sbitmap_zero (must_follow);
- for (e = u_node->in; e != 0; e = e->next_in)
- if (TEST_BIT (sched_nodes, e->src->cuid)
- && e->latency == (ii * e->distance)
- && start == SCHED_TIME (e->src))
- SET_BIT (must_precede, e->src->cuid);
-
- for (e = u_node->out; e != 0; e = e->next_out)
- if (TEST_BIT (sched_nodes, e->dest->cuid)
- && e->latency == (ii * e->distance)
- && end == SCHED_TIME (e->dest))
- SET_BIT (must_follow, e->dest->cuid);
-
- success = 0;
- if ((step > 0 && start < end) || (step < 0 && start > end))
- for (c = start; c != end; c += step)
- {
- ps_insn_ptr psi;
-
- psi = ps_add_node_check_conflicts (ps, u_node, c,
- must_precede,
- must_follow);
-
- if (psi)
- {
- SCHED_TIME (u_node) = c;
- SET_BIT (sched_nodes, u);
- success = 1;
- if (dump_file)
- fprintf(dump_file, "Schedule in %d\n", c);
- break;
- }
- }
- if (!success)
- {
- /* ??? Try backtracking instead of immediately ii++? */
- ii++;
- try_again_with_larger_ii = true;
- reset_partial_schedule (ps, ii);
- break;
- }
- /* ??? If (success), check register pressure estimates. */
- } /* Continue with next node. */
- } /* While try_again_with_larger_ii. */
+ SCHED_TIME (u) = new_time;
+ crr_insn->cycle = new_time;
+ SCHED_ROW (u) = new_time % new_ii;
+ SCHED_STAGE (u) = new_time / new_ii;
+ }
- sbitmap_free (sched_nodes);
+ }
- if (ii >= maxii)
+ rows_new[split_row] = NULL;
+
+ for (row = split_row; row < ii; row++)
{
- free_partial_schedule (ps);
- ps = NULL;
+ rows_new[row + 1] = ps->rows[row];
+ ps->rows[row] = NULL;
+ for (crr_insn = rows_new[row + 1];
+ crr_insn; crr_insn = crr_insn->next_in_row)
+ {
+ ddg_node_ptr u = crr_insn->node;
+ int new_time = SCHED_TIME (u) + (SCHED_TIME (u) / ii) + 1;
+
+ SCHED_TIME (u) = new_time;
+ crr_insn->cycle = new_time;
+ SCHED_ROW (u) = new_time % new_ii;
+ SCHED_STAGE (u) = new_time / new_ii;
+ }
}
- return ps;
+
+ /* Updating ps. */
+ ps->min_cycle = ps->min_cycle + ps->min_cycle / ii
+ + (SMODULO (ps->min_cycle, ii) >= split_row ? 1 : 0);
+ ps->max_cycle = ps->max_cycle + ps->max_cycle / ii
+ + (SMODULO (ps->max_cycle, ii) >= split_row ? 1 : 0);
+ free (ps->rows);
+ ps->rows = rows_new;
+ ps->ii = new_ii;
+ gcc_assert (ps->min_cycle >= 0);
+
+ verify_partial_schedule (ps, sched_nodes);
+
+ if (dump_file)
+ fprintf (dump_file, "min_cycle=%d, max_cycle=%d\n", ps->min_cycle,
+ ps->max_cycle);
+}
+
+/* Given U_NODE which is the node that failed to be scheduled; LOW and
+ UP which are the boundaries of it's scheduling window; compute using
+ SCHED_NODES and II a row in the partial schedule that can be split
+ which will separate a critical predecessor from a critical successor
+ thereby expanding the window, and return it. */
+static int
+compute_split_row (sbitmap sched_nodes, int low, int up, int ii,
+ ddg_node_ptr u_node)
+{
+ ddg_edge_ptr e;
+ int lower = INT_MIN, upper = INT_MAX;
+ ddg_node_ptr crit_pred = NULL;
+ ddg_node_ptr crit_succ = NULL;
+ int crit_cycle;
+
+ for (e = u_node->in; e != 0; e = e->next_in)
+ {
+ ddg_node_ptr v_node = e->src;
+
+ if (TEST_BIT (sched_nodes, v_node->cuid)
+ && (low == SCHED_TIME (v_node) + e->latency - (e->distance * ii)))
+ if (SCHED_TIME (v_node) > lower)
+ {
+ crit_pred = v_node;
+ lower = SCHED_TIME (v_node);
+ }
+ }
+
+ if (crit_pred != NULL)
+ {
+ crit_cycle = SCHED_TIME (crit_pred) + 1;
+ return SMODULO (crit_cycle, ii);
+ }
+
+ for (e = u_node->out; e != 0; e = e->next_out)
+ {
+ ddg_node_ptr v_node = e->dest;
+ if (TEST_BIT (sched_nodes, v_node->cuid)
+ && (up == SCHED_TIME (v_node) - e->latency + (e->distance * ii)))
+ if (SCHED_TIME (v_node) < upper)
+ {
+ crit_succ = v_node;
+ upper = SCHED_TIME (v_node);
+ }
+ }
+
+ if (crit_succ != NULL)
+ {
+ crit_cycle = SCHED_TIME (crit_succ);
+ return SMODULO (crit_cycle, ii);
+ }
+
+ if (dump_file)
+ fprintf (dump_file, "Both crit_pred and crit_succ are NULL\n");
+
+ return SMODULO ((low + up + 1) / 2, ii);
+}
+
+static void
+verify_partial_schedule (partial_schedule_ptr ps, sbitmap sched_nodes)
+{
+ int row;
+ ps_insn_ptr crr_insn;
+
+ for (row = 0; row < ps->ii; row++)
+ for (crr_insn = ps->rows[row]; crr_insn; crr_insn = crr_insn->next_in_row)
+ {
+ ddg_node_ptr u = crr_insn->node;
+
+ gcc_assert (TEST_BIT (sched_nodes, u->cuid));
+ /* ??? Test also that all nodes of sched_nodes are in ps, perhaps by
+ popcount (sched_nodes) == number of insns in ps. */
+ gcc_assert (SCHED_TIME (u) >= ps->min_cycle);
+ gcc_assert (SCHED_TIME (u) <= ps->max_cycle);
+ }
}
\f
static void order_nodes_of_sccs (ddg_all_sccs_ptr, int * result);
static int order_nodes_in_scc (ddg_ptr, sbitmap, sbitmap, int*, int);
-static nopa calculate_order_params (ddg_ptr, int mii);
+static nopa calculate_order_params (ddg_ptr, int, int *);
static int find_max_asap (ddg_ptr, sbitmap);
static int find_max_hv_min_mob (ddg_ptr, sbitmap);
static int find_max_dv_min_mob (ddg_ptr, sbitmap);
sbitmap_zero (tmp);
+ if (dump_file)
+ fprintf (dump_file, "SMS final nodes order: \n");
+
for (i = 0; i < num_nodes; i++)
{
int u = node_order[i];
- if (u >= num_nodes || u < 0 || TEST_BIT (tmp, u))
- abort ();
+ if (dump_file)
+ fprintf (dump_file, "%d ", u);
+ gcc_assert (u < num_nodes && u >= 0 && !TEST_BIT (tmp, u));
SET_BIT (tmp, u);
}
+ if (dump_file)
+ fprintf (dump_file, "\n");
+
sbitmap_free (tmp);
}
/* Order the nodes of G for scheduling and pass the result in
NODE_ORDER. Also set aux.count of each node to ASAP.
- Return the recMII for the given DDG. */
+ Put maximal ASAP to PMAX_ASAP. Return the recMII for the given DDG. */
static int
-sms_order_nodes (ddg_ptr g, int mii, int * node_order)
+sms_order_nodes (ddg_ptr g, int mii, int * node_order, int *pmax_asap)
{
int i;
int rec_mii = 0;
ddg_all_sccs_ptr sccs = create_ddg_all_sccs (g);
- nopa nops = calculate_order_params (g, mii);
+ nopa nops = calculate_order_params (g, mii, pmax_asap);
+
+ if (dump_file)
+ print_sccs (dump_file, sccs, g);
order_nodes_of_sccs (sccs, node_order);
sbitmap_zero (prev_sccs);
sbitmap_ones (ones);
- /* Perfrom the node ordering starting from the SCC with the highest recMII.
+ /* Perform the node ordering starting from the SCC with the highest recMII.
For each SCC order the nodes according to their ASAP/ALAP/HEIGHT etc. */
for (i = 0; i < all_sccs->num_sccs; i++)
{
/* MII is needed if we consider backarcs (that do not close recursive cycles). */
static struct node_order_params *
-calculate_order_params (ddg_ptr g, int mii ATTRIBUTE_UNUSED)
+calculate_order_params (ddg_ptr g, int mii ATTRIBUTE_UNUSED, int *pmax_asap)
{
int u;
int max_asap;
HEIGHT (e->dest) + e->latency);
}
}
+ if (dump_file)
+ {
+ fprintf (dump_file, "\nOrder params\n");
+ for (u = 0; u < num_nodes; u++)
+ {
+ ddg_node_ptr u_node = &g->nodes[u];
+
+ fprintf (dump_file, "node %d, ASAP: %d, ALAP: %d, HEIGHT: %d\n", u,
+ ASAP (u_node), ALAP (u_node), HEIGHT (u_node));
+ }
+ }
+ *pmax_asap = max_asap;
return node_order_params_arr;
}
static int
find_max_asap (ddg_ptr g, sbitmap nodes)
{
- int u;
+ unsigned int u = 0;
int max_asap = -1;
int result = -1;
+ sbitmap_iterator sbi;
- EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u,
+ EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u, sbi)
{
ddg_node_ptr u_node = &g->nodes[u];
max_asap = ASAP (u_node);
result = u;
}
- });
+ }
return result;
}
static int
find_max_hv_min_mob (ddg_ptr g, sbitmap nodes)
{
- int u;
+ unsigned int u = 0;
int max_hv = -1;
int min_mob = INT_MAX;
int result = -1;
+ sbitmap_iterator sbi;
- EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u,
+ EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u, sbi)
{
ddg_node_ptr u_node = &g->nodes[u];
min_mob = MOB (u_node);
result = u;
}
- });
+ }
return result;
}
static int
find_max_dv_min_mob (ddg_ptr g, sbitmap nodes)
{
- int u;
+ unsigned int u = 0;
int max_dv = -1;
int min_mob = INT_MAX;
int result = -1;
+ sbitmap_iterator sbi;
- EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u,
+ EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u, sbi)
{
ddg_node_ptr u_node = &g->nodes[u];
min_mob = MOB (u_node);
result = u;
}
- });
+ }
return result;
}
modulo scheduling. */
/* Create a partial schedule and allocate a memory to hold II rows. */
+
static partial_schedule_ptr
create_partial_schedule (int ii, ddg_ptr g, int history)
{
- partial_schedule_ptr ps = (partial_schedule_ptr)
- xmalloc (sizeof (struct partial_schedule));
+ partial_schedule_ptr ps = XNEW (struct partial_schedule);
ps->rows = (ps_insn_ptr *) xcalloc (ii, sizeof (ps_insn_ptr));
ps->ii = ii;
ps->history = history;
}
/* Free all the memory allocated to the partial schedule. */
+
static void
free_partial_schedule (partial_schedule_ptr ps)
{
/* Clear the rows array with its PS_INSNs, and create a new one with
NEW_II rows. */
+
static void
reset_partial_schedule (partial_schedule_ptr ps, int new_ii)
{
{
ps_insn_ptr ps_i = ps->rows[i];
- fprintf (dump, "\n[CYCLE %d ]: ", i);
+ fprintf (dump, "\n[ROW %d ]: ", i);
while (ps_i)
{
fprintf (dump, "%d, ",
static ps_insn_ptr
create_ps_insn (ddg_node_ptr node, int rest_count, int cycle)
{
- ps_insn_ptr ps_i = xmalloc (sizeof (struct ps_insn));
+ ps_insn_ptr ps_i = XNEW (struct ps_insn);
ps_i->node = node;
ps_i->next_in_row = NULL;
/* Removes the given PS_INSN from the partial schedule. Returns false if the
node is not found in the partial schedule, else returns true. */
-static int
+static bool
remove_node_from_ps (partial_schedule_ptr ps, ps_insn_ptr ps_i)
{
int row;
next_ps_i;
next_ps_i = next_ps_i->next_in_row)
{
- if (TEST_BIT (must_follow, next_ps_i->node->cuid)
+ if (must_follow && TEST_BIT (must_follow, next_ps_i->node->cuid)
&& ! first_must_follow)
first_must_follow = next_ps_i;
- if (TEST_BIT (must_precede, next_ps_i->node->cuid))
+ if (must_precede && TEST_BIT (must_precede, next_ps_i->node->cuid))
{
/* If we have already met a node that must follow, then
there is no possible column. */
}
/* Advances the PS_INSN one column in its current row; returns false
- in failure and true in success. Bit N is set in MUST_FOLLOW if
- the node with cuid N must be come after the node pointed to by
+ in failure and true in success. Bit N is set in MUST_FOLLOW if
+ the node with cuid N must be come after the node pointed to by
PS_I when scheduled in the same cycle. */
static int
ps_insn_advance_column (partial_schedule_ptr ps, ps_insn_ptr ps_i,
/* Check if next_in_row is dependent on ps_i, both having same sched
times (typically ANTI_DEP). If so, ps_i cannot skip over it. */
- if (TEST_BIT (must_follow, next_node->cuid))
+ if (must_follow && TEST_BIT (must_follow, next_node->cuid))
return false;
/* Advance PS_I over its next_in_row in the doubly linked list. */
}
/* Inserts a DDG_NODE to the given partial schedule at the given cycle.
- Returns 0 if this is not possible and a PS_INSN otherwise. Bit N is
- set in MUST_PRECEDE/MUST_FOLLOW if the node with cuid N must be come
- before/after (respectively) the node pointed to by PS_I when scheduled
+ Returns 0 if this is not possible and a PS_INSN otherwise. Bit N is
+ set in MUST_PRECEDE/MUST_FOLLOW if the node with cuid N must be come
+ before/after (respectively) the node pointed to by PS_I when scheduled
in the same cycle. */
static ps_insn_ptr
add_node_to_ps (partial_schedule_ptr ps, ddg_node_ptr node, int cycle,
{
if (targetm.sched.dfa_pre_cycle_insn)
state_transition (curr_state,
- (*targetm.sched.dfa_pre_cycle_insn) ());
+ targetm.sched.dfa_pre_cycle_insn ());
state_transition (curr_state, NULL);
if (targetm.sched.dfa_post_cycle_insn)
state_transition (curr_state,
- (*targetm.sched.dfa_post_cycle_insn) ());
+ targetm.sched.dfa_post_cycle_insn ());
}
+
+
/* Checks if PS has resource conflicts according to DFA, starting from
FROM cycle to TO cycle; returns true if there are conflicts and false
if there are no conflicts. Assumes DFA is being used. */
{
rtx insn = crr_insn->node->insn;
- if (!INSN_P (insn))
+ if (!NONDEBUG_INSN_P (insn))
continue;
/* Check if there is room for the current insn. */
return true;
/* Update the DFA state and return with failure if the DFA found
- recource conflicts. */
+ resource conflicts. */
if (state_transition (curr_state, insn) >= 0)
return true;
if (targetm.sched.variable_issue)
can_issue_more =
- (*targetm.sched.variable_issue) (sched_dump, sched_verbose,
- insn, can_issue_more);
+ targetm.sched.variable_issue (sched_dump, sched_verbose,
+ insn, can_issue_more);
/* A naked CLOBBER or USE generates no instruction, so don't
let them consume issue slots. */
else if (GET_CODE (PATTERN (insn)) != USE
/* Checks if the given node causes resource conflicts when added to PS at
cycle C. If not the node is added to PS and returned; otherwise zero
- is returned. Bit N is set in MUST_PRECEDE/MUST_FOLLOW if the node with
- cuid N must be come before/after (respectively) the node pointed to by
+ is returned. Bit N is set in MUST_PRECEDE/MUST_FOLLOW if the node with
+ cuid N must be come before/after (respectively) the node pointed to by
PS_I when scheduled in the same cycle. */
-static ps_insn_ptr
+ps_insn_ptr
ps_add_node_check_conflicts (partial_schedule_ptr ps, ddg_node_ptr n,
int c, sbitmap must_precede,
sbitmap must_follow)
/* Rotate the rows of PS such that insns scheduled at time
START_CYCLE will appear in row 0. Updates max/min_cycles. */
-static void
+void
rotate_partial_schedule (partial_schedule_ptr ps, int start_cycle)
{
int i, row, backward_rotates;
ps->min_cycle -= start_cycle;
}
-#endif /* INSN_SCHEDULING*/
+#endif /* INSN_SCHEDULING */
+\f
+static bool
+gate_handle_sms (void)
+{
+ return (optimize > 0 && flag_modulo_sched);
+}
+
+
+/* Run instruction scheduler. */
+/* Perform SMS module scheduling. */
+static unsigned int
+rest_of_handle_sms (void)
+{
+#ifdef INSN_SCHEDULING
+ basic_block bb;
+
+ /* Collect loop information to be used in SMS. */
+ cfg_layout_initialize (0);
+ sms_schedule ();
+
+ /* Update the life information, because we add pseudos. */
+ max_regno = max_reg_num ();
+
+ /* Finalize layout changes. */
+ FOR_EACH_BB (bb)
+ if (bb->next_bb != EXIT_BLOCK_PTR)
+ bb->aux = bb->next_bb;
+ free_dominance_info (CDI_DOMINATORS);
+ cfg_layout_finalize ();
+#endif /* INSN_SCHEDULING */
+ return 0;
+}
+
+struct rtl_opt_pass pass_sms =
+{
+ {
+ RTL_PASS,
+ "sms", /* name */
+ gate_handle_sms, /* gate */
+ rest_of_handle_sms, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ TV_SMS, /* tv_id */
+ 0, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ TODO_dump_func, /* todo_flags_start */
+ TODO_df_finish | TODO_verify_rtl_sharing |
+ TODO_dump_func |
+ TODO_ggc_collect /* todo_flags_finish */
+ }
+};
+
OSDN Git Service
