/* Swing Modulo Scheduling implementation.
- Copyright (C) 2004
+ Copyright (C) 2004, 2005, 2006
Free Software Foundation, Inc.
Contributed by Ayal Zaks and Mustafa Hagog <zaks,mustafa@il.ibm.com>
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. */
+Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301, USA. */
#include "config.h"
#include "rtl.h"
#include "tm_p.h"
#include "hard-reg-set.h"
-#include "basic-block.h"
#include "regs.h"
#include "function.h"
#include "flags.h"
#include "gcov-io.h"
#include "df.h"
#include "ddg.h"
+#include "timevar.h"
+#include "tree-pass.h"
#ifdef INSN_SCHEDULING
here the insns are not scheduled monotonically top-down (nor bottom-
up).
3. If failed in scheduling all insns - bump II++ and try again, unless
- II reaches an upper bound MaxII, inwhich case report failure.
+ II reaches an upper bound MaxII, in which case report failure.
5. If we succeeded in scheduling the loop within II cycles, we now
generate prolog and epilog, decrease the counter of the loop, and
perform modulo variable expansion for live ranges that span more than
#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;
+};
+
-partial_schedule_ptr create_partial_schedule (int ii, ddg_ptr, int history);
-void free_partial_schedule (partial_schedule_ptr);
-void reset_partial_schedule (partial_schedule_ptr, int new_ii);
+
+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 *);
-ps_insn_ptr ps_add_node_check_conflicts (partial_schedule_ptr,
- ddg_node_ptr node, int cycle);
-void rotate_partial_schedule (partial_schedule_ptr, int);
+static int kernel_number_of_cycles (rtx first_insn, rtx last_insn);
+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 bool ps_unschedule_node (partial_schedule_ptr, ddg_node_ptr );
\f
/* This page defines constants and structures for the modulo scheduling
static int issue_rate;
-/* For printing statistics. */
-static FILE *stats_file;
-
static int sms_order_nodes (ddg_ptr, int, int * result);
static void set_node_sched_params (ddg_ptr);
-static partial_schedule_ptr sms_schedule_by_order (ddg_ptr, int, int,
- int *, FILE*);
+static partial_schedule_ptr sms_schedule_by_order (ddg_ptr, int, int, int *);
static void permute_partial_schedule (partial_schedule_ptr ps, rtx last);
-static void generate_prolog_epilog (partial_schedule_ptr, rtx, rtx, int);
+static void generate_prolog_epilog (partial_schedule_ptr ,struct loop * loop, rtx);
static void duplicate_insns_of_cycles (partial_schedule_ptr ps,
int from_stage, int to_stage,
int is_prolog);
-
#define SCHED_ASAP(x) (((node_sched_params_ptr)(x)->aux.info)->asap)
#define SCHED_TIME(x) (((node_sched_params_ptr)(x)->aux.info)->time)
#define SCHED_FIRST_REG_MOVE(x) \
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,
NULL,
NULL,
sms_print_insn,
- contributes_to_priority,
+ NULL,
compute_jump_reg_dependencies,
NULL, NULL,
NULL, NULL,
- 0, 0, 0
+ 0, 0, 0,
+
+ NULL, NULL, NULL, NULL, NULL,
+#ifdef ENABLE_CHECKING
+ NULL,
+#endif
+ 0
};
-/* Return the register decremented and tested or zero if it is not a decrement
- and branch jump insn (similar to doloop_condition_get). */
+/* Return the register decremented and tested in INSN,
+ or zero if it is not a decrement-and-branch insn. */
+
static rtx
-doloop_register_get (rtx insn, rtx *comp)
+doloop_register_get (rtx insn ATTRIBUTE_UNUSED)
{
- rtx pattern, cmp, inc, reg, condition;
+#ifdef HAVE_doloop_end
+ rtx pattern, reg, condition;
- if (GET_CODE (insn) != JUMP_INSN)
+ if (! JUMP_P (insn))
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)
- 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;
-
- /* Extract loop termination condition. */
- condition = XEXP (SET_SRC (cmp), 0);
-
- /* 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)
+ pattern = PATTERN (insn);
+ condition = doloop_condition_get (pattern);
+ if (! condition)
return NULL_RTX;
- if (XEXP (condition, 0) == reg)
- return reg;
+ 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 ();
+ 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) &&
}
static void
-print_node_sched_params (FILE * dump_file, int num_nodes)
+print_node_sched_params (FILE * file, int num_nodes)
{
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:\n", i);
+ 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);
}
}
return maxii;
}
-
-/* Given the partial schdule, 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
+/*
+ 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)
{
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--;
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);
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);
+ }
prev_reg = new_reg;
}
+ sbitmap_vector_free (uses_of_defs);
+ }
+ return reg_move_replaces;
+}
+
+/* We call this when we want to undo the SMS schedule for a given loop.
+ One of the things that we do is to delete the register moves generated
+ for the sake of SMS; this function deletes the register move instructions
+ recorded in the undo buffer. */
+static void
+undo_generate_reg_moves (partial_schedule_ptr ps,
+ struct undo_replace_buff_elem *reg_move_replaces)
+{
+ int i,j;
+
+ for (i = 0; i < ps->g->num_nodes; i++)
+ {
+ ddg_node_ptr u = &ps->g->nodes[i];
+ rtx prev;
+ rtx crr = SCHED_FIRST_REG_MOVE (u);
+
+ for (j = 0; j < SCHED_NREG_MOVES (u); j++)
+ {
+ prev = PREV_INSN (crr);
+ delete_insn (crr);
+ crr = prev;
+ }
+ SCHED_FIRST_REG_MOVE (u) = NULL_RTX;
+ }
+
+ while (reg_move_replaces)
+ {
+ struct undo_replace_buff_elem *rep = reg_move_replaces;
+
+ reg_move_replaces = reg_move_replaces->next;
+ replace_rtx (rep->insn, rep->new_reg, rep->orig_reg);
+ }
+}
+
+/* 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);
}
}
int amount = PS_MIN_CYCLE (ps);
int ii = ps->ii;
- for (i = 0; i < g->num_nodes; i++)
+ /* Don't include the closing branch assuming that it is the last node. */
+ for (i = 0; i < g->num_nodes - 1; i++)
{
ddg_node_ptr u = &g->nodes[i];
int normalized_time = SCHED_TIME (u) - amount;
- if (normalized_time < 0)
- abort ();
+ gcc_assert (normalized_time >= 0);
SCHED_TIME (u) = normalized_time;
SCHED_ROW (u) = normalized_time % ii;
PREV_INSN (last));
}
+/* As part of undoing SMS we return to the original ordering of the
+ instructions inside the loop kernel. Given the partial schedule PS, this
+ function returns the ordering of the instruction according to their CUID
+ in the DDG (PS->G), which is the original order of the instruction before
+ performing SMS. */
+static void
+undo_permute_partial_schedule (partial_schedule_ptr ps, rtx last)
+{
+ int i;
+
+ for (i = 0 ; i < ps->g->num_nodes; i++)
+ if (last == ps->g->nodes[i].insn
+ || last == ps->g->nodes[i].first_note)
+ break;
+ else if (PREV_INSN (last) != ps->g->nodes[i].insn)
+ reorder_insns_nobb (ps->g->nodes[i].first_note, ps->g->nodes[i].insn,
+ 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. */
/* 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)
{
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 = ps->g->bb->pred;
- if (e->src == ps->g->bb)
- e = e->pred_next;
/* 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_reg)
+ /* Generate a subtract instruction at the beginning of the prolog to
+ adjust the loop count by STAGE_COUNT. */
+ emit_insn (gen_sub2_insn (count_reg, GEN_INT (last_stage)));
for (i = 0; i < last_stage; i++)
duplicate_insns_of_cycles (ps, 0, i, 1);
- /* No need to call insert_insn_on_edge; we prepared the sequence. */
- e->insns.r = get_insns ();
+ /* Put the prolog on the entry edge. */
+ e = loop_preheader_edge (loop);
+ split_edge_and_insert (e, get_insns());
+
end_sequence ();
/* Generate the epilog, inserting its insns on the loop-exit edge. */
for (i = 0; i < last_stage; i++)
duplicate_insns_of_cycles (ps, i + 1, last_stage, 0);
- last_epilog_insn = emit_note (NOTE_INSN_DELETED);
-
- /* Emit the label where to put the original loop code. */
- if (unknown_count)
- {
- rtx label, cond;
-
- precond_exit_label = gen_label_rtx ();
- precond_exit_label_insn = emit_label (precond_exit_label);
+ /* 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 ();
+}
- /* Put the original loop code. */
- reorder_insns_nobb (orig_loop_beg, orig_loop_end, precond_exit_label_insn);
+/* 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);
- /* 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);
+ for (i = 0; i < loop->num_nodes ; i++)
+ {
+ rtx head, tail;
+ bool empty_bb = true;
- if (! c_reg || GET_CODE (cond) != NE)
- abort ();
+ if (bbs[i] == loop->header)
+ continue;
- XEXP (label, 0) = precond_exit_label;
- JUMP_LABEL (orig_loop_bct) = precond_exit_label_insn;
- LABEL_NUSES (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) && JUMP_P (head)))
+ continue;
+ empty_bb = false;
+ break;
+ }
- /* Generate the loop exit label. */
- loop_exit_label = gen_label_rtx ();
- loop_exit_label_insn = emit_label (loop_exit_label);
+ if (! empty_bb)
+ {
+ free (bbs);
+ return false;
+ }
}
+ free (bbs);
+ return true;
+}
- e = ps->g->bb->succ;
- if (e->dest == ps->g->bb)
- e = e->succ_next;
+/* 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))
- e->insns.r = get_insns ();
- end_sequence ();
+/* 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)
+ return false;
- commit_edge_insertions ();
+ if (!single_exit (loop))
+ {
+ if (dump_file)
+ {
+ rtx insn = BB_END (loop->header);
+
+ fprintf (dump_file, "SMS loop many exits ");
+ fprintf (dump_file, " %s %d (file, line)\n",
+ insn_file (insn), insn_line (insn));
+ }
+ return false;
+ }
- if (unknown_count)
+ if (! SIMPLE_SMS_LOOP_P (loop) && ! loop_single_full_bb_p (loop))
{
- 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 = epilog_bb->succ;
-
- /* 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));
+ if (dump_file)
+ {
+ rtx insn = BB_END (loop->header);
+
+ fprintf (dump_file, "SMS loop many BBs. ");
+ fprintf (dump_file, " %s %d (file, line)\n",
+ insn_file (insn), insn_line (insn));
+ }
+ return false;
}
+
+ return true;
}
-/* Return the line note insn preceding INSN, for debugging. Taken from
- emit-rtl.c. */
-static rtx
-find_line_note (rtx insn)
+/* 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)
{
- for (; insn; insn = PREV_INSN (insn))
- if (GET_CODE (insn) == NOTE
- && NOTE_LINE_NUMBER (insn) >= 0)
- break;
+ edge e;
+ edge_iterator i;
- return insn;
+ /* 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)
+ {
+ FOR_EACH_EDGE (e, i, loop->header->preds)
+ if (e->src == loop->latch)
+ break;
+ split_edge (e);
+ }
}
/* 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;
+ unsigned i,num_loops;
partial_schedule_ptr ps;
- int max_bb_index = last_basic_block;
struct df *df;
-
- /* SMS uses the DFA interface. */
- if (! targetm.sched.use_dfa_pipeline_interface
- || ! (*targetm.sched.use_dfa_pipeline_interface) ())
- return;
-
- stats_file = dump_file;
-
+ basic_block bb = NULL;
+ /* vars to the versioning only if needed*/
+ struct loop * nloop;
+ basic_block condition_bb = NULL;
+ edge latch_edge;
+ gcov_type trip_count = 0;
+
+ loop_optimizer_init (LOOPS_HAVE_PREHEADERS
+ | LOOPS_HAVE_MARKED_SINGLE_EXITS);
+ if (!current_loops)
+ 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
/* Initialize the scheduler. */
current_sched_info = &sms_sched_info;
- sched_init (NULL);
+ sched_init ();
/* Init Data Flow analysis, to be used in interloop dep calculation. */
- df = df_init ();
- df_analyze (df, 0, DF_ALL);
+ df = df_init (DF_HARD_REGS | DF_EQUIV_NOTES | DF_SUBREGS);
+ df_rd_add_problem (df, 0);
+ df_ru_add_problem (df, 0);
+ df_chain_add_problem (df, DF_DU_CHAIN | DF_UD_CHAIN);
+ df_analyze (df);
+
+ if (dump_file)
+ df_dump (df, dump_file);
+
+ /* 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, current_loops->num);
- /* Allocate memory to hold the DDG array. */
- g_arr = xcalloc (max_bb_index, sizeof (ddg_ptr));
/* 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 (i = 0; i < current_loops->num; i++)
{
rtx head, tail;
- rtx count_reg, comp;
- edge e, pre_header_edge;
+ rtx count_reg;
+ struct loop *loop = current_loops->parray[i];
- if (bb->index < 0)
- 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");
- /* Check if bb has two successors, one being itself. */
- e = bb->succ;
- if (!e || !e->succ_next || e->succ_next->succ_next)
- continue;
+ break;
+ }
- if (e->dest != bb && e->succ_next->dest != bb)
- continue;
+ if (! loop_canon_p (loop))
+ continue;
- if ((e->flags & EDGE_COMPLEX)
- || (e->succ_next->flags & EDGE_COMPLEX))
+ if (! loop_single_full_bb_p (loop))
continue;
- /* Check if bb has two predecessors, one being itself. */
- /* In view of above tests, suffices to check e->pred_next->pred_next? */
- e = bb->pred;
- if (!e || !e->pred_next || e->pred_next->pred_next)
- continue;
+ bb = loop->header;
- if (e->src != bb && e->pred_next->src != bb)
- continue;
+ 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;
- if ((e->flags & EDGE_COMPLEX)
- || (e->pred_next->flags & EDGE_COMPLEX))
- continue;
+ /* Perfrom SMS only on loops that their average count is above threshold. */
- /* For debugging. */
- if (passes++ > MAX_SMS_LOOP_NUMBER && MAX_SMS_LOOP_NUMBER != -1)
+ if ( latch_edge->count
+ && (latch_edge->count < single_exit (loop)->count * SMS_LOOP_AVERAGE_COUNT_THRESHOLD))
{
if (dump_file)
- fprintf (dump_file, "SMS reached MAX_PASSES... \n");
- break;
- }
-
- get_block_head_tail (bb->index, &head, &tail);
- pre_header_edge = bb->pred;
- if (bb->pred->src != bb)
- pre_header_edge = bb->pred->pred_next;
-
- /* 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);
-
- 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");
+ 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 (tail)))
continue;
- e = bb->pred;
- if (e->src == bb)
- pre_header = e->pred_next->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 (GET_CODE (insn) == CALL_INSN
- || GET_CODE (insn) == BARRIER
- || (INSN_P (insn) && GET_CODE (insn) != JUMP_INSN
+ if (CALL_P (insn)
+ || BARRIER_P (insn)
+ || (INSN_P (insn) && !JUMP_P (insn)
&& !single_set (insn) && GET_CODE (PATTERN (insn)) != USE))
break;
if (insn != NEXT_INSN (tail))
{
- if (stats_file)
+ if (dump_file)
{
- if (GET_CODE (insn) == CALL_INSN)
- fprintf (stats_file, "SMS loop-with-call\n");
- else if (GET_CODE (insn) == BARRIER)
- fprintf (stats_file, "SMS loop-with-barrier\n");
+ if (CALL_P (insn))
+ fprintf (dump_file, "SMS loop-with-call\n");
+ else if (BARRIER_P (insn))
+ fprintf (dump_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-not-single-set\n");
+ print_rtl_single (dump_file, insn);
}
continue;
if (! (g = create_ddg (bb, df, 0)))
{
- if (stats_file)
- fprintf (stats_file, "SMS doloop\n");
+ if (dump_file)
+ fprintf (dump_file, "SMS doloop\n");
continue;
}
- g_arr[bb->index] = g;
+ g_arr[i] = g;
}
/* Release Data Flow analysis data structures. */
df_finish (df);
+ df = NULL;
+ /* We don't want to perform SMS on new loops - created by versioning. */
+ num_loops = current_loops->num;
/* Go over the built DDGs and perfrom SMS for each one of them. */
- for (i = 0; i < max_bb_index; i++)
+ for (i = 0; i < num_loops; i++)
{
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;
+ struct loop *loop = current_loops->parray[i];
if (! (g = g_arr[i]))
continue;
if (dump_file)
print_ddg (dump_file, g);
- get_block_head_tail (g->bb->index, &head, &tail);
+ get_ebb_head_tail (loop->header, loop->header, &head, &tail);
- pre_header_edge = g->bb->pred;
- if (g->bb->pred->src != g->bb)
- pre_header_edge = g->bb->pred->pred_next;
+ 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 (stats_file)
+ if (dump_file)
{
- rtx line_note = find_line_note (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");
+ 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 (tail)))
+ {
+ basic_block pre_header;
+
+ pre_header = loop_preheader_edge (loop)->src;
+ count_init = const_iteration_count (count_reg, pre_header,
+ &loop_count);
+ }
+ gcc_assert (count_reg);
- if (stats_file && count_init)
+ 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);
mii = MAX (res_MII (g), rec_mii);
maxii = (calculate_maxii (g) * SMS_MAX_II_FACTOR) / 100;
- 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)
stage_count = PS_STAGE_COUNT (ps);
- 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;
+ int orig_cycles = kernel_number_of_cycles (BB_HEAD (g->bb), BB_END (g->bb));
+ int new_cycles;
+ 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
rotate_partial_schedule (ps, PS_MIN_CYCLE (ps));
set_columns_for_ps (ps);
+ /* Generate the kernel just to be able to measure its cycles. */
permute_partial_schedule (ps, g->closing_branch->first_note);
- generate_reg_moves (ps);
- if (dump_file)
- print_node_sched_params (dump_file, g->num_nodes);
+ reg_move_replaces = generate_reg_moves (ps);
- /* Set new iteration count of loop kernel. */
- if (count_init)
- SET_SRC (single_set (count_init)) = GEN_INT (loop_count
- - stage_count + 1);
+ /* Get the number of cycles the new kernel expect to execute in. */
+ new_cycles = kernel_number_of_cycles (BB_HEAD (g->bb), BB_END (g->bb));
- /* Generate prolog and epilog. */
- generate_prolog_epilog (ps, orig_loop_beg, orig_loop_end,
- count_init ? 0 : 1);
+ /* Get back to the original loop so we can do loop versioning. */
+ undo_permute_partial_schedule (ps, g->closing_branch->first_note);
+ if (reg_move_replaces)
+ undo_generate_reg_moves (ps, reg_move_replaces);
+
+ if ( new_cycles >= orig_cycles)
+ {
+ /* SMS is not profitable so undo the permutation and reg move generation
+ and return the kernel to its original state. */
+ if (dump_file)
+ fprintf (dump_file, "Undoing SMS because it is not profitable.\n");
+
+ }
+ else
+ {
+ 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));
+
+ nloop = loop_version (loop, comp_rtx, &condition_bb, 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. */
+ g->bb->flags |= BB_DIRTY;
+
+ reg_move_replaces = generate_reg_moves (ps);
+ if (dump_file)
+ print_node_sched_params (dump_file, g->num_nodes);
+ /* Generate prolog and epilog. */
+ if (count_reg && !count_init)
+ generate_prolog_epilog (ps, loop, count_reg);
+ else
+ generate_prolog_epilog (ps, loop, NULL_RTX);
+ }
+ 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 ();
+ loop_optimizer_finalize ();
}
/* The SMS scheduling algorithm itself
set to 0 to save compile time. */
#define DFA_HISTORY SMS_DFA_HISTORY
+/* 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 (TEST_BIT (sched_nodes, v_node->cuid))
+ {
+ int node_st = SCHED_TIME (v_node)
+ + e->latency - (e->distance * ii);
+
+ early_start = MAX (early_start, node_st);
+
+ 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;
+ }
+
+ 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 (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;
+ }
+
+ else if (psp_not_empty && pss_not_empty)
+ {
+ int early_start = INT_MIN;
+ int late_start = INT_MAX;
+
+ 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;
+ }
+
+ *start_p = start;
+ *step_p = step;
+ *end_p = end;
+ sbitmap_free (psp);
+ sbitmap_free (pss);
+
+ if ((start >= end && step == 1) || (start <= end && step == -1))
+ return -1;
+ else
+ return 0;
+}
+
+/* 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;
ddg_edge_ptr e;
int start, end, step; /* Place together into one struct? */
sbitmap sched_nodes = sbitmap_alloc (num_nodes);
- sbitmap psp = sbitmap_alloc (num_nodes);
- sbitmap pss = 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 ((! sbitmap_equal (tobe_scheduled, sched_nodes)
+ || try_again_with_larger_ii ) && ii < maxii)
{
+ int j;
+ bool unscheduled_nodes = false;
+
if (dump_file)
fprintf(dump_file, "Starting with ii=%d\n", ii);
- try_again_with_larger_ii = false;
- sbitmap_zero (sched_nodes);
+ if (try_again_with_larger_ii)
+ {
+ try_again_with_larger_ii = 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 (GET_CODE (insn) == JUMP_INSN) /* Closing branch handled later. */
- continue;
-
- /* 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 = 0;
-
- 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);
- }
- }
- start = early_start;
- end = MIN (end, early_start + ii);
- step = 1;
+ RESET_BIT (tobe_scheduled, u);
+ continue;
}
- else if (!psp_not_empty && pss_not_empty)
+ if (JUMP_P (insn)) /* Closing branch handled later. */
{
- 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 (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;
+ RESET_BIT (tobe_scheduled, u);
+ continue;
}
- else if (psp_not_empty && pss_not_empty)
- {
- int early_start = 0;
- int late_start = INT_MAX;
+ if (TEST_BIT (sched_nodes, u))
+ continue;
- 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)
+ /* Try to get non-empty scheduling window. */
+ j = i;
+ while (get_sched_window (ps, nodes_order, i, sched_nodes, ii, &start, &step, &end) < 0
+ && j > 0)
+ {
+ unscheduled_nodes = true;
+ if (TEST_BIT (NODE_PREDECESSORS (u_node), nodes_order[j - 1])
+ || TEST_BIT (NODE_SUCCESSORS (u_node), nodes_order[j - 1]))
{
- 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);
- }
+ ps_unschedule_node (ps, &ps->g->nodes[nodes_order[j - 1]]);
+ RESET_BIT (sched_nodes, nodes_order [j - 1]);
}
- start = MAX (start, early_start);
- end = MIN (end, MIN (early_start + ii, late_start + 1));
- step = 1;
+ j--;
}
- else /* psp is empty && pss is empty. */
+ if (j < 0)
{
- start = SCHED_ASAP (u_node);
- end = start + ii;
- step = 1;
+ /* ??? Try backtracking instead of immediately ii++? */
+ ii++;
+ try_again_with_larger_ii = true;
+ reset_partial_schedule (ps, ii);
+ break;
}
-
/* 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 = ps_add_node_check_conflicts (ps, u_node, c);
+ ps_insn_ptr psi;
+
+ psi = ps_add_node_check_conflicts (ps, u_node, c,
+ must_precede,
+ must_follow);
if (psi)
{
reset_partial_schedule (ps, ii);
break;
}
+ if (unscheduled_nodes)
+ break;
+
/* ??? If (success), check register pressure estimates. */
} /* Continue with next node. */
} /* While try_again_with_larger_ii. */
sbitmap_free (sched_nodes);
- sbitmap_free (psp);
- sbitmap_free (pss);
+ sbitmap_free (must_precede);
+ sbitmap_free (must_follow);
+ sbitmap_free (tobe_scheduled);
if (ii >= maxii)
{
{
int u = node_order[i];
- if (u >= num_nodes || u < 0 || TEST_BIT (tmp, u))
- abort ();
+ gcc_assert (u < num_nodes && u >= 0 && !TEST_BIT (tmp, u));
SET_BIT (tmp, u);
}
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. */
-partial_schedule_ptr
+
+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. */
-void
+
+static void
free_partial_schedule (partial_schedule_ptr ps)
{
if (!ps)
/* Clear the rows array with its PS_INSNs, and create a new one with
NEW_II rows. */
-void
+
+static void
reset_partial_schedule (partial_schedule_ptr ps, int new_ii)
{
if (!ps)
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;
return true;
}
+/* Unlike what literature describes for modulo scheduling (which focuses
+ on VLIW machines) the order of the instructions inside a cycle is
+ important. Given the bitmaps MUST_FOLLOW and MUST_PRECEDE we know
+ where the current instruction should go relative to the already
+ scheduled instructions in the given cycle. Go over these
+ instructions and find the first possible column to put it in. */
+static bool
+ps_insn_find_column (partial_schedule_ptr ps, ps_insn_ptr ps_i,
+ sbitmap must_precede, sbitmap must_follow)
+{
+ ps_insn_ptr next_ps_i;
+ ps_insn_ptr first_must_follow = NULL;
+ ps_insn_ptr last_must_precede = NULL;
+ int row;
+
+ if (! ps_i)
+ return false;
+
+ row = SMODULO (ps_i->cycle, ps->ii);
+
+ /* Find the first must follow and the last must precede
+ and insert the node immediately after the must precede
+ but make sure that it there is no must follow after it. */
+ for (next_ps_i = ps->rows[row];
+ next_ps_i;
+ next_ps_i = next_ps_i->next_in_row)
+ {
+ if (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 we have already met a node that must follow, then
+ there is no possible column. */
+ if (first_must_follow)
+ return false;
+ else
+ last_must_precede = next_ps_i;
+ }
+ }
+
+ /* Now insert the node after INSERT_AFTER_PSI. */
+
+ if (! last_must_precede)
+ {
+ ps_i->next_in_row = ps->rows[row];
+ ps_i->prev_in_row = NULL;
+ if (ps_i->next_in_row)
+ ps_i->next_in_row->prev_in_row = ps_i;
+ ps->rows[row] = ps_i;
+ }
+ else
+ {
+ ps_i->next_in_row = last_must_precede->next_in_row;
+ last_must_precede->next_in_row = ps_i;
+ ps_i->prev_in_row = last_must_precede;
+ if (ps_i->next_in_row)
+ ps_i->next_in_row->prev_in_row = ps_i;
+ }
+
+ return true;
+}
+
/* Advances the PS_INSN one column in its current row; returns false
- in failure and true in success. */
+ 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)
+ps_insn_advance_column (partial_schedule_ptr ps, ps_insn_ptr ps_i,
+ sbitmap must_follow)
{
ps_insn_ptr prev, next;
int row;
+ ddg_node_ptr next_node;
if (!ps || !ps_i)
return false;
if (! ps_i->next_in_row)
return false;
+ next_node = ps_i->next_in_row->node;
+
/* 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 (ps_i->cycle == ps_i->next_in_row->cycle)
- {
- ddg_edge_ptr e;
- ddg_node_ptr next_node = ps_i->next_in_row->node;
-
- for (e = ps_i->node->out; e; e = e->next_out)
- if (e->dest == next_node)
- return false;
- }
+ if (TEST_BIT (must_follow, next_node->cuid))
+ return false;
- /* Advace PS_I over its next_in_row in the doubly linked list. */
+ /* Advance PS_I over its next_in_row in the doubly linked list. */
prev = ps_i->prev_in_row;
next = ps_i->next_in_row;
}
/* 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. */
+ 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)
+add_node_to_ps (partial_schedule_ptr ps, ddg_node_ptr node, int cycle,
+ sbitmap must_precede, sbitmap must_follow)
{
- ps_insn_ptr ps_i, next_ps_i, advance_after;
+ ps_insn_ptr ps_i;
int rest_count = 1;
int row = SMODULO (cycle, ps->ii);
- ddg_edge_ptr e;
if (ps->rows[row]
&& ps->rows[row]->row_rest_count >= issue_rate)
rest_count += ps->rows[row]->row_rest_count;
ps_i = create_ps_insn (node, rest_count, cycle);
- ps_i->next_in_row = ps->rows[row];
- ps_i->prev_in_row = NULL;
- if (ps_i->next_in_row)
- ps_i->next_in_row->prev_in_row = ps_i;
- ps->rows[row] = ps_i;
-
- /* Check if n is dependent on an insn already in row, having same cycle
- (typically ANTI_DEP). If so, n must skip over it. */
- advance_after = NULL;
- for (next_ps_i = ps_i->next_in_row;
- next_ps_i;
- next_ps_i = next_ps_i->next_in_row)
- if (next_ps_i->cycle == cycle)
- for (e = node->in; e; e = e->next_in)
- if (e->src == next_ps_i->node)
- advance_after = next_ps_i;
-
- if (advance_after)
- while (ps_i->prev_in_row != advance_after)
- if (!ps_insn_advance_column (ps, ps_i))
- {
- remove_node_from_ps (ps, ps_i);
- return NULL;
- }
+
+ /* Finds and inserts PS_I according to MUST_FOLLOW and
+ MUST_PRECEDE. */
+ if (! ps_insn_find_column (ps, ps_i, must_precede, must_follow))
+ {
+ free (ps_i);
+ return NULL;
+ }
return ps_i;
}
static void
advance_one_cycle (void)
{
- if (targetm.sched.use_dfa_pipeline_interface
- && (*targetm.sched.use_dfa_pipeline_interface) ())
+ if (targetm.sched.dfa_pre_cycle_insn)
+ state_transition (curr_state,
+ 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 ());
+}
+
+/* Given the kernel of a loop (from FIRST_INSN to LAST_INSN), finds
+ the number of cycles according to DFA that the kernel fits in,
+ we use this to check if we done well with SMS after we add
+ register moves. In some cases register moves overhead makes
+ it even worse than the original loop. We want SMS to be performed
+ when it gives less cycles after register moves are added. */
+static int
+kernel_number_of_cycles (rtx first_insn, rtx last_insn)
+{
+ int cycles = 0;
+ rtx insn;
+ int can_issue_more = issue_rate;
+
+ state_reset (curr_state);
+
+ for (insn = first_insn;
+ insn != NULL_RTX && insn != last_insn;
+ insn = NEXT_INSN (insn))
{
- if (targetm.sched.dfa_pre_cycle_insn)
- state_transition (curr_state,
- (*targetm.sched.dfa_pre_cycle_insn) ());
+ if (! INSN_P (insn) || GET_CODE (PATTERN (insn)) == USE)
+ continue;
- state_transition (curr_state, NULL);
+ /* Check if there is room for the current insn. */
+ if (!can_issue_more || state_dead_lock_p (curr_state))
+ {
+ cycles ++;
+ advance_one_cycle ();
+ can_issue_more = issue_rate;
+ }
- if (targetm.sched.dfa_post_cycle_insn)
- state_transition (curr_state,
- (*targetm.sched.dfa_post_cycle_insn) ());
+ /* Update the DFA state and return with failure if the DFA found
+ recource conflicts. */
+ if (state_transition (curr_state, insn) >= 0)
+ {
+ cycles ++;
+ advance_one_cycle ();
+ can_issue_more = issue_rate;
+ }
+
+ if (targetm.sched.variable_issue)
+ 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
+ && GET_CODE (PATTERN (insn)) != CLOBBER)
+ can_issue_more--;
}
+ return cycles;
}
/* Checks if PS has resource conflicts according to DFA, starting from
{
int cycle;
- if (! targetm.sched.use_dfa_pipeline_interface
- || ! (*targetm.sched.use_dfa_pipeline_interface) ())
- return true;
-
state_reset (curr_state);
for (cycle = from; cycle <= to; cycle++)
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. */
+ 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. */
ps_insn_ptr
-ps_add_node_check_conflicts (partial_schedule_ptr ps, ddg_node_ptr n, int c)
+ps_add_node_check_conflicts (partial_schedule_ptr ps, ddg_node_ptr n,
+ int c, sbitmap must_precede,
+ sbitmap must_follow)
{
int has_conflicts = 0;
ps_insn_ptr ps_i;
- /* First add the node to the PS, if this succeeds check for conflicts,
- trying different issue slots in the same row. */
- if (! (ps_i = add_node_to_ps (ps, n, c)))
+ /* First add the node to the PS, if this succeeds check for
+ conflicts, trying different issue slots in the same row. */
+ if (! (ps_i = add_node_to_ps (ps, n, c, must_precede, must_follow)))
return NULL; /* Failed to insert the node at the given cycle. */
has_conflicts = ps_has_conflicts (ps, c, c)
scheduled in without conflicts. */
while (has_conflicts)
{
- if (! ps_insn_advance_column (ps, ps_i))
+ if (! ps_insn_advance_column (ps, ps_i, must_follow))
break;
has_conflicts = ps_has_conflicts (ps, c, c)
|| (ps->history > 0
ps->min_cycle -= start_cycle;
}
-#endif /* INSN_SCHEDULING*/
+/* Remove the node N from the partial schedule PS; because we restart the DFA
+ each time we want to check for resource conflicts; this is equivalent to
+ unscheduling the node N. */
+static bool
+ps_unschedule_node (partial_schedule_ptr ps, ddg_node_ptr n)
+{
+ ps_insn_ptr ps_i;
+ int row = SMODULO (SCHED_TIME (n), ps->ii);
+
+ if (row < 0 || row > ps->ii)
+ return false;
+
+ for (ps_i = ps->rows[row];
+ ps_i && ps_i->node != n;
+ ps_i = ps_i->next_in_row);
+ if (!ps_i)
+ return false;
+
+ return remove_node_from_ps (ps, ps_i);
+}
+#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;
+
+ /* We want to be able to create new pseudos. */
+ no_new_pseudos = 0;
+ /* Collect loop information to be used in SMS. */
+ cfg_layout_initialize (CLEANUP_UPDATE_LIFE);
+ sms_schedule ();
+
+ /* Update the life information, because we add pseudos. */
+ max_regno = max_reg_num ();
+ allocate_reg_info (max_regno, FALSE, FALSE);
+ update_life_info (NULL, UPDATE_LIFE_GLOBAL_RM_NOTES,
+ (PROP_DEATH_NOTES
+ | PROP_REG_INFO
+ | PROP_KILL_DEAD_CODE
+ | PROP_SCAN_DEAD_CODE));
+
+ no_new_pseudos = 1;
+
+ /* Finalize layout changes. */
+ FOR_EACH_BB (bb)
+ if (bb->next_bb != EXIT_BLOCK_PTR)
+ bb->aux = bb->next_bb;
+ cfg_layout_finalize ();
+ free_dominance_info (CDI_DOMINATORS);
+#endif /* INSN_SCHEDULING */
+ return 0;
+}
+
+struct tree_opt_pass pass_sms =
+{
+ "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_dump_func |
+ TODO_ggc_collect, /* todo_flags_finish */
+ 'm' /* letter */
+};
+
OSDN Git Service
