/* Swing Modulo Scheduling implementation.
- Copyright (C) 2004, 2005, 2006, 2007, 2008
+ Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011
Free Software Foundation, Inc.
Contributed by Ayal Zaks and Mustafa Hagog <zaks,mustafa@il.ibm.com>
#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 "timevar.h"
#include "tree-pass.h"
#include "dbgcnt.h"
+#include "df.h"
#ifdef INSN_SCHEDULING
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
+ SMS works with countable loops 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.
+ 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
/* The number of different iterations the nodes in ps span, assuming
the stage boundaries are placed efficiently. */
-#define PS_STAGE_COUNT(ps) ((PS_MAX_CYCLE (ps) - PS_MIN_CYCLE (ps) \
- + 1 + (ps)->ii - 1) / (ps)->ii)
+#define CALC_STAGE_COUNT(max_cycle,min_cycle,ii) ((max_cycle - min_cycle \
+ + 1 + ii - 1) / ii)
+/* The stage count of ps. */
+#define PS_STAGE_COUNT(ps) (((partial_schedule_ptr)(ps))->stage_count)
/* A single instruction in the partial schedule. */
struct ps_insn
int max_cycle;
ddg_ptr g; /* The DDG of the insns in the partial schedule. */
+
+ int stage_count; /* The stage count of the partial schedule. */
};
/* We use this to record all the register replacements we do in
};
-
+
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);
rtx, rtx);
static void duplicate_insns_of_cycles (partial_schedule_ptr,
int, int, int, rtx);
-
+static int calculate_stage_count (partial_schedule_ptr ps);
#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) \
NULL, NULL,
0, 0,
- NULL, NULL, NULL,
+ NULL, NULL, NULL, NULL,
0
};
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));
+ : prev_nondebug_insn (tail));
for (insn = head; insn != first_insn_not_to_check; insn = NEXT_INSN (insn))
- if (reg_mentioned_p (reg, insn))
+ if (!DEBUG_INSN_P (insn) && reg_mentioned_p (reg, insn))
{
if (dump_file)
{
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);
res_MII (ddg_ptr g)
{
if (targetm.sched.sms_res_mii)
- return targetm.sched.sms_res_mii (g);
-
- return (g->num_nodes / issue_rate);
+ return targetm.sched.sms_res_mii (g);
+
+ return ((g->num_nodes - g->num_debug) / issue_rate);
}
}
}
-/* Bump the SCHED_TIMEs of all nodes to start from zero. Set the values
- of SCHED_ROW and SCHED_STAGE. */
+/* Bump the SCHED_TIMEs of all nodes by AMOUNT. Set the values of
+ SCHED_ROW and SCHED_STAGE. Instruction scheduled on cycle AMOUNT
+ will move to cycle zero. */
static void
-normalize_sched_times (partial_schedule_ptr ps)
+reset_sched_times (partial_schedule_ptr ps, int amount)
{
int row;
- int amount = PS_MIN_CYCLE (ps);
int ii = ps->ii;
ps_insn_ptr crr_insn;
{
ddg_node_ptr u = crr_insn->node;
int normalized_time = SCHED_TIME (u) - amount;
+ int new_min_cycle = PS_MIN_CYCLE (ps) - amount;
+ int sc_until_cycle_zero, stage;
- 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);
+ if (dump_file)
+ {
+ /* Print the scheduling times after the rotation. */
+ fprintf (dump_file, "crr_insn->node=%d (insn id %d), "
+ "crr_insn->cycle=%d, min_cycle=%d", crr_insn->node->cuid,
+ INSN_UID (crr_insn->node->insn), SCHED_TIME (u),
+ normalized_time);
+ if (JUMP_P (crr_insn->node->insn))
+ fprintf (dump_file, " (branch)");
+ fprintf (dump_file, "\n");
+ }
+
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;
+ SCHED_ROW (u) = SMODULO (normalized_time, ii);
+
+ /* The calculation of stage count is done adding the number
+ of stages before cycle zero and after cycle zero. */
+ sc_until_cycle_zero = CALC_STAGE_COUNT (-1, new_min_cycle, ii);
+
+ if (SCHED_TIME (u) < 0)
+ {
+ stage = CALC_STAGE_COUNT (-1, SCHED_TIME (u), ii);
+ SCHED_STAGE (u) = sc_until_cycle_zero - stage;
+ }
+ else
+ {
+ stage = CALC_STAGE_COUNT (SCHED_TIME (u), 0, ii);
+ SCHED_STAGE (u) = sc_until_cycle_zero + stage - 1;
+ }
}
}
-
+
/* Set SCHED_COLUMN of each node according to its position in PS. */
static void
set_columns_for_ps (partial_schedule_ptr ps)
/* Do not duplicate any insn which refers to count_reg as it
belongs to the control part.
+ The closing branch is scheduled as well and thus should
+ be ignored.
TODO: This should be done by analyzing the control part of
the loop. */
- if (reg_mentioned_p (count_reg, u_node->insn))
+ if (reg_mentioned_p (count_reg, u_node->insn)
+ || JUMP_P (ps_ij->node->insn))
continue;
if (for_prolog)
int i;
int last_stage = PS_STAGE_COUNT (ps) - 1;
edge e;
-
+
/* Generate the prolog, inserting its insns on the loop-entry edge. */
start_sequence ();
for (i = 0; i < last_stage; i++)
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 ());
for (i = 0; i < last_stage; i++)
duplicate_insns_of_cycles (ps, i + 1, last_stage, 0, count_reg);
-
+
/* Put the epilogue on the exit edge. */
gcc_assert (single_exit (loop));
e = single_exit (loop);
for (; head != NEXT_INSN (tail); head = NEXT_INSN (head))
{
if (NOTE_P (head) || LABEL_P (head)
- || (INSN_P (head) && JUMP_P (head)))
+ || (INSN_P (head) && (DEBUG_INSN_P (head) || JUMP_P (head))))
continue;
empty_bb = false;
break;
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));
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));
continue;
}
- /* 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).
+ /* Don't handle BBs with calls or barriers or auto-increment insns
+ (to avoid creating invalid reg-moves for the auto-increment insns),
+ or !single_set with the exception of instructions that include
+ count_reg---these instructions are part of the control part
+ that do-loop recognizes.
??? Should handle auto-increment insns.
??? Should handle insns defining subregs. */
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)
+ || (NONDEBUG_INSN_P (insn) && !JUMP_P (insn)
+ && !single_set (insn) && GET_CODE (PATTERN (insn)) != USE
+ && !reg_mentioned_p (count_reg, insn))
|| (FIND_REG_INC_NOTE (insn, NULL_RTX) != 0)
|| (INSN_P (insn) && (set = single_set (insn))
&& GET_CODE (SET_DEST (set)) == SUBREG))
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 ((INSN_P (insn) && !JUMP_P (insn)
+ 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
continue;
}
- if (! (g = create_ddg (bb, 0)))
+ /* Always schedule the closing branch with the rest of the
+ instructions. The branch is rotated to be in row ii-1 at the
+ end of the scheduling procedure to make sure it's the last
+ instruction in the iteration. */
+ if (! (g = create_ddg (bb, 1)))
{
if (dump_file)
fprintf (dump_file, "SMS create_ddg failed\n");
ps = sms_schedule_by_order (g, mii, maxii, node_order);
- if (ps)
- stage_count = PS_STAGE_COUNT (ps);
-
- /* Stage count of 1 means that there is no interleaving between
- iterations, let the scheduling passes do the job. */
- if (stage_count < 1
+ if (ps)
+ {
+ stage_count = calculate_stage_count (ps);
+ gcc_assert(stage_count >= 1);
+ PS_STAGE_COUNT(ps) = stage_count;
+ }
+
+ /* The default value of PARAM_SMS_MIN_SC is 2 as stage count of
+ 1 means that there is no interleaving between iterations thus
+ we let the scheduling passes do the job in this case. */
+ if (stage_count < (unsigned) PARAM_VALUE (PARAM_SMS_MIN_SC)
|| (count_init && (loop_count <= stage_count))
|| (flag_branch_probabilities && (trip_count <= stage_count)))
{
fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, trip_count);
fprintf (dump_file, ")\n");
}
- continue;
}
else
{
struct undo_replace_buff_elem *reg_move_replaces;
+ int amount = SCHED_TIME (g->closing_branch) + 1;
+
+ /* Set the stage boundaries. The closing_branch was scheduled
+ and should appear in the last (ii-1) row. */
+ reset_sched_times (ps, amount);
+ rotate_partial_schedule (ps, amount);
+ set_columns_for_ps (ps);
- if (dump_file)
- {
+ canon_loop (loop);
+
+ if (dump_file)
+ {
fprintf (dump_file,
"SMS succeeded %d %d (with ii, sc)\n", ps->ii,
stage_count);
print_partial_schedule (ps, dump_file);
- fprintf (dump_file,
- "SMS Branch (%d) will later be scheduled at cycle %d.\n",
- g->closing_branch->cuid, PS_MIN_CYCLE (ps) - 1);
}
-
- /* 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.
- 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)
{
print_node_sched_params (dump_file, g->num_nodes, g);
/* Generate prolog and epilog. */
generate_prolog_epilog (ps, loop, count_reg, count_init);
-
+
free_undo_replace_buff (reg_move_replaces);
}
ddg_node_ptr v_node = e->src;
if (dump_file)
- {
+ {
fprintf (dump_file, "\nProcessing edge: ");
print_ddg_edge (dump_file, e);
fprintf (dump_file,
MAX (early_start, p_st + e->latency - (e->distance * ii));
if (dump_file)
- fprintf (dump_file,
+ fprintf (dump_file,
"pred st = %d; early_start = %d; latency: %d",
p_st, early_start, e->latency);
s_st - e->latency + (e->distance * ii));
if (dump_file)
- fprintf (dump_file,
+ fprintf (dump_file,
"succ st = %d; late_start = %d; latency = %d",
s_st, late_start, e->latency);
- (e->distance * ii));
if (dump_file)
- fprintf (dump_file,
+ fprintf (dump_file,
"pred st = %d; early_start = %d; latency = %d",
p_st, early_start, e->latency);
+ (e->distance * ii));
if (dump_file)
- fprintf (dump_file,
+ fprintf (dump_file,
"succ st = %d; late_start = %d; latency = %d",
s_st, late_start, e->latency);
&& 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)) >=
+ 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 */
ddg_node_ptr u_node = &ps->g->nodes[u];
rtx insn = u_node->insn;
- if (!INSN_P (insn))
- {
- RESET_BIT (tobe_scheduled, u);
- continue;
- }
-
- if (JUMP_P (insn)) /* Closing branch handled later. */
+ if (!NONDEBUG_INSN_P (insn))
{
RESET_BIT (tobe_scheduled, u);
continue;
if (dump_file)
fprintf (dump_file, "split_row=%d\n", split_row);
- normalize_sched_times (ps);
- rotate_partial_schedule (ps, ps->min_cycle);
+ reset_sched_times (ps, PS_MIN_CYCLE (ps));
+ rotate_partial_schedule (ps, PS_MIN_CYCLE (ps));
rows_new = (ps_insn_ptr *) xcalloc (new_ii, sizeof (ps_insn_ptr));
for (row = 0; row < split_row; row++)
SET_BIT (tmp, u);
}
-
+
if (dump_file)
fprintf (dump_file, "\n");
-
+
sbitmap_free (tmp);
}
ps_insn_ptr next_ps_i;
ps_insn_ptr first_must_follow = NULL;
ps_insn_ptr last_must_precede = NULL;
+ ps_insn_ptr last_in_row = NULL;
int row;
if (! ps_i)
else
last_must_precede = next_ps_i;
}
+ /* The closing branch must be the last in the row. */
+ if (must_precede
+ && TEST_BIT (must_precede, next_ps_i->node->cuid)
+ && JUMP_P (next_ps_i->node->insn))
+ return false;
+
+ last_in_row = next_ps_i;
}
+ /* The closing branch is scheduled as well. Make sure there is no
+ dependent instruction after it as the branch should be the last
+ instruction in the row. */
+ if (JUMP_P (ps_i->node->insn))
+ {
+ if (first_must_follow)
+ return false;
+ if (last_in_row)
+ {
+ /* Make the branch the last in the row. New instructions
+ will be inserted at the beginning of the row or after the
+ last must_precede instruction thus the branch is guaranteed
+ to remain the last instruction in the row. */
+ last_in_row->next_in_row = ps_i;
+ ps_i->prev_in_row = last_in_row;
+ ps_i->next_in_row = NULL;
+ }
+ else
+ ps->rows[row] = ps_i;
+ return true;
+ }
+
/* Now insert the node after INSERT_AFTER_PSI. */
if (! last_must_precede)
}
/* 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,
}
/* 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,
{
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. */
/* 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. */
ps_insn_ptr
ps_add_node_check_conflicts (partial_schedule_ptr ps, ddg_node_ptr n,
return ps_i;
}
+/* Calculate the stage count of the partial schedule PS. The calculation
+ takes into account the rotation to bring the closing branch to row
+ ii-1. */
+int
+calculate_stage_count (partial_schedule_ptr ps)
+{
+ int rotation_amount = (SCHED_TIME (ps->g->closing_branch)) + 1;
+ int new_min_cycle = PS_MIN_CYCLE (ps) - rotation_amount;
+ int new_max_cycle = PS_MAX_CYCLE (ps) - rotation_amount;
+ int stage_count = CALC_STAGE_COUNT (-1, new_min_cycle, ps->ii);
+
+ /* The calculation of stage count is done adding the number of stages
+ before cycle zero and after cycle zero. */
+ stage_count += CALC_STAGE_COUNT (new_max_cycle, 0, ps->ii);
+
+ return stage_count;
+}
+
/* Rotate the rows of PS such that insns scheduled at time
START_CYCLE will appear in row 0. Updates max/min_cycles. */
void
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 */
+ TODO_df_finish
+ | TODO_verify_flow
+ | TODO_verify_rtl_sharing
+ | TODO_dump_func
+ | TODO_ggc_collect /* todo_flags_finish */
}
};
OSDN Git Service
