/* Swing Modulo Scheduling implementation.
- Copyright (C) 2004, 2005, 2006, 2007, 2008
+ Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
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
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
{
- /* The corresponding DDG_NODE. */
- ddg_node_ptr node;
+ /* Identifies the instruction to be scheduled. Values smaller than
+ the ddg's num_nodes refer directly to ddg nodes. A value of
+ X - num_nodes refers to register move X. */
+ int id;
/* The (absolute) cycle in which the PS instruction is scheduled.
Same as SCHED_TIME (node). */
ps_insn_ptr next_in_row,
prev_in_row;
- /* The number of nodes in the same row that come after this node. */
- int row_rest_count;
};
+/* Information about a register move that has been added to a partial
+ schedule. */
+struct ps_reg_move_info
+{
+ /* The source of the move is defined by the ps_insn with id DEF.
+ The destination is used by the ps_insns with the ids in USES. */
+ int def;
+ sbitmap uses;
+
+ /* The original form of USES' instructions used OLD_REG, but they
+ should now use NEW_REG. */
+ rtx old_reg;
+ rtx new_reg;
+
+ /* The number of consecutive stages that the move occupies. */
+ int num_consecutive_stages;
+
+ /* An instruction that sets NEW_REG to the correct value. The first
+ move associated with DEF will have an rhs of OLD_REG; later moves
+ use the result of the previous move. */
+ rtx insn;
+};
+
+typedef struct ps_reg_move_info ps_reg_move_info;
+DEF_VEC_O (ps_reg_move_info);
+DEF_VEC_ALLOC_O (ps_reg_move_info, heap);
+
/* Holds the partial schedule as an array of II rows. Each entry of the
array points to a linked list of PS_INSNs, which represents the
instructions that are scheduled for that row. */
/* rows[i] points to linked list of insns scheduled in row i (0<=i<ii). */
ps_insn_ptr *rows;
+ /* All the moves added for this partial schedule. Index X has
+ a ps_insn id of X + g->num_nodes. */
+ VEC (ps_reg_move_info, heap) *reg_moves;
+
+ /* rows_length[i] holds the number of instructions in the row.
+ It is used only (as an optimization) to back off quickly from
+ trying to schedule a node in a full row; that is, to avoid running
+ through futile DFA state transitions. */
+ int *rows_length;
+
/* The earliest absolute cycle of an insn in the partial schedule. */
int min_cycle;
int max_cycle;
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;
+ int stage_count; /* The stage count of the partial schedule. */
};
-
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);
+ int, int, sbitmap, sbitmap);
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 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)
-#define SCHED_FIRST_REG_MOVE(x) \
- (((node_sched_params_ptr)(x)->aux.info)->first_reg_move)
-#define SCHED_NREG_MOVES(x) \
- (((node_sched_params_ptr)(x)->aux.info)->nreg_moves)
-#define SCHED_ROW(x) (((node_sched_params_ptr)(x)->aux.info)->row)
-#define SCHED_STAGE(x) (((node_sched_params_ptr)(x)->aux.info)->stage)
-#define SCHED_COLUMN(x) (((node_sched_params_ptr)(x)->aux.info)->column)
+static int calculate_stage_count (partial_schedule_ptr, int);
+static void calculate_must_precede_follow (ddg_node_ptr, int, int,
+ int, int, sbitmap, sbitmap, sbitmap);
+static int get_sched_window (partial_schedule_ptr, ddg_node_ptr,
+ sbitmap, int, int *, int *, int *);
+static bool try_scheduling_node_in_cycle (partial_schedule_ptr, int, int,
+ sbitmap, int *, sbitmap, sbitmap);
+static void remove_node_from_ps (partial_schedule_ptr, ps_insn_ptr);
+
+#define NODE_ASAP(node) ((node)->aux.count)
+
+#define SCHED_PARAMS(x) VEC_index (node_sched_params, node_sched_param_vec, x)
+#define SCHED_TIME(x) (SCHED_PARAMS (x)->time)
+#define SCHED_ROW(x) (SCHED_PARAMS (x)->row)
+#define SCHED_STAGE(x) (SCHED_PARAMS (x)->stage)
+#define SCHED_COLUMN(x) (SCHED_PARAMS (x)->column)
/* The scheduling parameters held for each node. */
typedef struct node_sched_params
{
- int asap; /* A lower-bound on the absolute scheduling cycle. */
- int time; /* The absolute scheduling cycle (time >= asap). */
-
- /* The following field (first_reg_move) is a pointer to the first
- register-move instruction added to handle the modulo-variable-expansion
- of the register defined by this node. This register-move copies the
- original register defined by the node. */
- rtx first_reg_move;
-
- /* The number of register-move instructions added, immediately preceding
- first_reg_move. */
- int nreg_moves;
+ int time; /* The absolute scheduling cycle. */
int row; /* Holds time % ii. */
int stage; /* Holds time / ii. */
int column;
} *node_sched_params_ptr;
+typedef struct node_sched_params node_sched_params;
+DEF_VEC_O (node_sched_params);
+DEF_VEC_ALLOC_O (node_sched_params, heap);
\f
/* The following three functions are copied from the current scheduler
code in order to use sched_analyze() for computing the dependencies.
static void
compute_jump_reg_dependencies (rtx insn ATTRIBUTE_UNUSED,
- regset cond_exec ATTRIBUTE_UNUSED,
- regset used ATTRIBUTE_UNUSED,
- regset set ATTRIBUTE_UNUSED)
+ regset used ATTRIBUTE_UNUSED)
{
}
NULL,
sms_print_insn,
NULL,
+ NULL, /* insn_finishes_block_p */
NULL, NULL,
NULL, NULL,
0, 0,
- NULL, NULL, NULL,
+ NULL, NULL, NULL, NULL,
+ NULL, NULL,
0
};
+/* Partial schedule instruction ID in PS is a register move. Return
+ information about it. */
+static struct ps_reg_move_info *
+ps_reg_move (partial_schedule_ptr ps, int id)
+{
+ gcc_checking_assert (id >= ps->g->num_nodes);
+ return VEC_index (ps_reg_move_info, ps->reg_moves, id - ps->g->num_nodes);
+}
+
+/* Return the rtl instruction that is being scheduled by partial schedule
+ instruction ID, which belongs to schedule PS. */
+static rtx
+ps_rtl_insn (partial_schedule_ptr ps, int id)
+{
+ if (id < ps->g->num_nodes)
+ return ps->g->nodes[id].insn;
+ else
+ return ps_reg_move (ps, id)->insn;
+}
+
+/* Partial schedule instruction ID, which belongs to PS, occured in
+ the original (unscheduled) loop. Return the first instruction
+ in the loop that was associated with ps_rtl_insn (PS, ID).
+ If the instruction had some notes before it, this is the first
+ of those notes. */
+static rtx
+ps_first_note (partial_schedule_ptr ps, int id)
+{
+ gcc_assert (id < ps->g->num_nodes);
+ return ps->g->nodes[id].first_note;
+}
+
+/* Return the number of consecutive stages that are occupied by
+ partial schedule instruction ID in PS. */
+static int
+ps_num_consecutive_stages (partial_schedule_ptr ps, int id)
+{
+ if (id < ps->g->num_nodes)
+ return 1;
+ else
+ return ps_reg_move (ps, id)->num_consecutive_stages;
+}
+
/* 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
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);
- if (GET_CODE (SET_SRC (pat)) == CONST_INT)
+ if (CONST_INT_P (SET_SRC (pat)))
{
*count = INTVAL (SET_SRC (pat));
return 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);
}
-/* Points to the array that contains the sched data for each node. */
-static node_sched_params_ptr node_sched_params;
+/* A vector that contains the sched data for each ps_insn. */
+static VEC (node_sched_params, heap) *node_sched_param_vec;
-/* Allocate sched_params for each node and initialize it. Assumes that
- the aux field of each node contain the asap bound (computed earlier),
- and copies it into the sched_params field. */
+/* Allocate sched_params for each node and initialize it. */
static void
set_node_sched_params (ddg_ptr g)
{
- int i;
+ VEC_truncate (node_sched_params, node_sched_param_vec, 0);
+ VEC_safe_grow_cleared (node_sched_params, heap,
+ node_sched_param_vec, g->num_nodes);
+}
+
+/* Make sure that node_sched_param_vec has an entry for every move in PS. */
+static void
+extend_node_sched_params (partial_schedule_ptr ps)
+{
+ VEC_safe_grow_cleared (node_sched_params, heap, node_sched_param_vec,
+ ps->g->num_nodes + VEC_length (ps_reg_move_info,
+ ps->reg_moves));
+}
- /* Allocate for each node in the DDG a place to hold the "sched_data". */
- /* Initialize ASAP/ALAP/HIGHT to zero. */
- node_sched_params = (node_sched_params_ptr)
- xcalloc (g->num_nodes,
- sizeof (struct node_sched_params));
+/* Update the sched_params (time, row and stage) for node U using the II,
+ the CYCLE of U and MIN_CYCLE.
+ We're not simply taking the following
+ SCHED_STAGE (u) = CALC_STAGE_COUNT (SCHED_TIME (u), min_cycle, ii);
+ because the stages may not be aligned on cycle 0. */
+static void
+update_node_sched_params (int u, int ii, int cycle, int min_cycle)
+{
+ int sc_until_cycle_zero;
+ int stage;
- /* Set the pointer of the general data of the node to point to the
- appropriate sched_params structure. */
- for (i = 0; i < g->num_nodes; i++)
+ SCHED_TIME (u) = cycle;
+ SCHED_ROW (u) = SMODULO (cycle, 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, 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
{
- /* Watch out for aliasing problems? */
- node_sched_params[i].asap = g->nodes[i].aux.count;
- g->nodes[i].aux.info = &node_sched_params[i];
+ stage = CALC_STAGE_COUNT (SCHED_TIME (u), 0, ii);
+ SCHED_STAGE (u) = sc_until_cycle_zero + stage - 1;
}
}
static void
-print_node_sched_params (FILE *file, int num_nodes, ddg_ptr g)
+print_node_sched_params (FILE *file, int num_nodes, partial_schedule_ptr ps)
{
int i;
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;
+ node_sched_params_ptr nsp = SCHED_PARAMS (i);
fprintf (file, "Node = %d; INSN = %d\n", i,
- (INSN_UID (g->nodes[i].insn)));
- fprintf (file, " asap = %d:\n", nsp->asap);
+ INSN_UID (ps_rtl_insn (ps, i)));
+ fprintf (file, " asap = %d:\n", NODE_ASAP (&ps->g->nodes[i]));
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 (file, " stage = %d:\n", nsp->stage);
+ }
+}
+
+/* Set SCHED_COLUMN for each instruction in row ROW of PS. */
+static void
+set_columns_for_row (partial_schedule_ptr ps, int row)
+{
+ ps_insn_ptr cur_insn;
+ int column;
+
+ column = 0;
+ for (cur_insn = ps->rows[row]; cur_insn; cur_insn = cur_insn->next_in_row)
+ SCHED_COLUMN (cur_insn->id) = column++;
+}
+
+/* Set SCHED_COLUMN for each instruction in PS. */
+static void
+set_columns_for_ps (partial_schedule_ptr ps)
+{
+ int row;
+
+ for (row = 0; row < ps->ii; row++)
+ set_columns_for_row (ps, row);
+}
+
+/* Try to schedule the move with ps_insn identifier I_REG_MOVE in PS.
+ Its single predecessor has already been scheduled, as has its
+ ddg node successors. (The move may have also another move as its
+ successor, in which case that successor will be scheduled later.)
+
+ The move is part of a chain that satisfies register dependencies
+ between a producing ddg node and various consuming ddg nodes.
+ If some of these dependencies have a distance of 1 (meaning that
+ the use is upward-exposed) then DISTANCE1_USES is nonnull and
+ contains the set of uses with distance-1 dependencies.
+ DISTANCE1_USES is null otherwise.
+
+ MUST_FOLLOW is a scratch bitmap that is big enough to hold
+ all current ps_insn ids.
+
+ Return true on success. */
+static bool
+schedule_reg_move (partial_schedule_ptr ps, int i_reg_move,
+ sbitmap distance1_uses, sbitmap must_follow)
+{
+ unsigned int u;
+ int this_time, this_distance, this_start, this_end, this_latency;
+ int start, end, c, ii;
+ sbitmap_iterator sbi;
+ ps_reg_move_info *move;
+ rtx this_insn;
+ ps_insn_ptr psi;
+
+ move = ps_reg_move (ps, i_reg_move);
+ ii = ps->ii;
+ if (dump_file)
+ {
+ fprintf (dump_file, "Scheduling register move INSN %d; ii = %d"
+ ", min cycle = %d\n\n", INSN_UID (move->insn), ii,
+ PS_MIN_CYCLE (ps));
+ print_rtl_single (dump_file, move->insn);
+ fprintf (dump_file, "\n%11s %11s %5s\n", "start", "end", "time");
+ fprintf (dump_file, "=========== =========== =====\n");
+ }
+
+ start = INT_MIN;
+ end = INT_MAX;
+
+ /* For dependencies of distance 1 between a producer ddg node A
+ and consumer ddg node B, we have a chain of dependencies:
+
+ A --(T,L1,1)--> M1 --(T,L2,0)--> M2 ... --(T,Ln,0)--> B
+
+ where Mi is the ith move. For dependencies of distance 0 between
+ a producer ddg node A and consumer ddg node C, we have a chain of
+ dependencies:
+
+ A --(T,L1',0)--> M1' --(T,L2',0)--> M2' ... --(T,Ln',0)--> C
+
+ where Mi' occupies the same position as Mi but occurs a stage later.
+ We can only schedule each move once, so if we have both types of
+ chain, we model the second as:
+
+ A --(T,L1',1)--> M1 --(T,L2',0)--> M2 ... --(T,Ln',-1)--> C
+
+ First handle the dependencies between the previously-scheduled
+ predecessor and the move. */
+ this_insn = ps_rtl_insn (ps, move->def);
+ this_latency = insn_latency (this_insn, move->insn);
+ this_distance = distance1_uses && move->def < ps->g->num_nodes ? 1 : 0;
+ this_time = SCHED_TIME (move->def) - this_distance * ii;
+ this_start = this_time + this_latency;
+ this_end = this_time + ii;
+ if (dump_file)
+ fprintf (dump_file, "%11d %11d %5d %d --(T,%d,%d)--> %d\n",
+ this_start, this_end, SCHED_TIME (move->def),
+ INSN_UID (this_insn), this_latency, this_distance,
+ INSN_UID (move->insn));
+
+ if (start < this_start)
+ start = this_start;
+ if (end > this_end)
+ end = this_end;
+
+ /* Handle the dependencies between the move and previously-scheduled
+ successors. */
+ EXECUTE_IF_SET_IN_SBITMAP (move->uses, 0, u, sbi)
+ {
+ this_insn = ps_rtl_insn (ps, u);
+ this_latency = insn_latency (move->insn, this_insn);
+ if (distance1_uses && !TEST_BIT (distance1_uses, u))
+ this_distance = -1;
+ else
+ this_distance = 0;
+ this_time = SCHED_TIME (u) + this_distance * ii;
+ this_start = this_time - ii;
+ this_end = this_time - this_latency;
+ if (dump_file)
+ fprintf (dump_file, "%11d %11d %5d %d --(T,%d,%d)--> %d\n",
+ this_start, this_end, SCHED_TIME (u), INSN_UID (move->insn),
+ this_latency, this_distance, INSN_UID (this_insn));
+
+ if (start < this_start)
+ start = this_start;
+ if (end > this_end)
+ end = this_end;
+ }
+
+ if (dump_file)
+ {
+ fprintf (dump_file, "----------- ----------- -----\n");
+ fprintf (dump_file, "%11d %11d %5s %s\n", start, end, "", "(max, min)");
+ }
+
+ sbitmap_zero (must_follow);
+ SET_BIT (must_follow, move->def);
+
+ start = MAX (start, end - (ii - 1));
+ for (c = end; c >= start; c--)
+ {
+ psi = ps_add_node_check_conflicts (ps, i_reg_move, c,
+ move->uses, must_follow);
+ if (psi)
{
- fprintf (file, " reg_move = ");
- print_rtl_single (file, reg_move);
- reg_move = PREV_INSN (reg_move);
+ update_node_sched_params (i_reg_move, ii, c, PS_MIN_CYCLE (ps));
+ if (dump_file)
+ fprintf (dump_file, "\nScheduled register move INSN %d at"
+ " time %d, row %d\n\n", INSN_UID (move->insn), c,
+ SCHED_ROW (i_reg_move));
+ return true;
}
}
+
+ if (dump_file)
+ fprintf (dump_file, "\nNo available slot\n\n");
+
+ return false;
}
/*
nreg_moves = ----------------------------------- + 1 - { dependence.
ii { 1 if not.
*/
-static struct undo_replace_buff_elem *
-generate_reg_moves (partial_schedule_ptr ps, bool rescan)
+static bool
+schedule_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++)
{
ddg_node_ptr u = &g->nodes[i];
ddg_edge_ptr e;
int nreg_moves = 0, i_reg_move;
- sbitmap *uses_of_defs;
- rtx last_reg_move;
rtx prev_reg, old_reg;
-
+ int first_move;
+ int distances[2];
+ sbitmap must_follow;
+ sbitmap distance1_uses;
+ rtx set = single_set (u->insn);
+
+ /* Skip instructions that do not set a register. */
+ if ((set && !REG_P (SET_DEST (set))))
+ continue;
+
/* Compute the number of reg_moves needed for u, by looking at life
ranges started at u (excluding self-loops). */
+ distances[0] = distances[1] = false;
for (e = u->out; e; e = e->next_out)
if (e->type == TRUE_DEP && e->dest != e->src)
{
- int nreg_moves4e = (SCHED_TIME (e->dest) - SCHED_TIME (e->src)) / ii;
+ int nreg_moves4e = (SCHED_TIME (e->dest->cuid)
+ - SCHED_TIME (e->src->cuid)) / ii;
if (e->distance == 1)
- nreg_moves4e = (SCHED_TIME (e->dest) - SCHED_TIME (e->src) + ii) / ii;
+ nreg_moves4e = (SCHED_TIME (e->dest->cuid)
+ - SCHED_TIME (e->src->cuid) + 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)
- && SCHED_COLUMN (e->dest) < SCHED_COLUMN (e->src))
+ if (SCHED_ROW (e->dest->cuid) == SCHED_ROW (e->src->cuid)
+ && SCHED_COLUMN (e->dest->cuid) < SCHED_COLUMN (e->src->cuid))
nreg_moves4e--;
+ if (nreg_moves4e >= 1)
+ {
+ /* !single_set instructions are not supported yet and
+ thus we do not except to encounter them in the loop
+ except from the doloop part. For the latter case
+ we assume no regmoves are generated as the doloop
+ instructions are tied to the branch with an edge. */
+ gcc_assert (set);
+ /* If the instruction contains auto-inc register then
+ validate that the regmov is being generated for the
+ target regsiter rather then the inc'ed register. */
+ gcc_assert (!autoinc_var_is_used_p (u->insn, e->dest->insn));
+ }
+
+ if (nreg_moves4e)
+ {
+ gcc_assert (e->distance < 2);
+ distances[e->distance] = true;
+ }
nreg_moves = MAX (nreg_moves, nreg_moves4e);
}
if (nreg_moves == 0)
continue;
+ /* Create NREG_MOVES register moves. */
+ first_move = VEC_length (ps_reg_move_info, ps->reg_moves);
+ VEC_safe_grow_cleared (ps_reg_move_info, heap, ps->reg_moves,
+ first_move + nreg_moves);
+ extend_node_sched_params (ps);
+
+ /* Record the moves associated with this node. */
+ first_move += ps->g->num_nodes;
+
+ /* Generate each move. */
+ old_reg = prev_reg = SET_DEST (single_set (u->insn));
+ for (i_reg_move = 0; i_reg_move < nreg_moves; i_reg_move++)
+ {
+ ps_reg_move_info *move = ps_reg_move (ps, first_move + i_reg_move);
+
+ move->def = i_reg_move > 0 ? first_move + i_reg_move - 1 : i;
+ move->uses = sbitmap_alloc (first_move + nreg_moves);
+ move->old_reg = old_reg;
+ move->new_reg = gen_reg_rtx (GET_MODE (prev_reg));
+ move->num_consecutive_stages = distances[0] && distances[1] ? 2 : 1;
+ move->insn = gen_move_insn (move->new_reg, copy_rtx (prev_reg));
+ sbitmap_zero (move->uses);
+
+ prev_reg = move->new_reg;
+ }
+
+ distance1_uses = distances[1] ? sbitmap_alloc (g->num_nodes) : NULL;
+
/* Every use of the register defined by node may require a different
copy of this register, depending on the time the use is scheduled.
- Set a bitmap vector, telling which nodes use each copy of this
- register. */
- uses_of_defs = sbitmap_vector_alloc (nreg_moves, g->num_nodes);
- sbitmap_vector_zero (uses_of_defs, nreg_moves);
+ Record which uses require which move results. */
for (e = u->out; e; e = e->next_out)
if (e->type == TRUE_DEP && e->dest != e->src)
{
- int dest_copy = (SCHED_TIME (e->dest) - SCHED_TIME (e->src)) / ii;
+ int dest_copy = (SCHED_TIME (e->dest->cuid)
+ - SCHED_TIME (e->src->cuid)) / ii;
if (e->distance == 1)
- dest_copy = (SCHED_TIME (e->dest) - SCHED_TIME (e->src) + ii) / ii;
+ dest_copy = (SCHED_TIME (e->dest->cuid)
+ - SCHED_TIME (e->src->cuid) + ii) / ii;
- if (SCHED_ROW (e->dest) == SCHED_ROW (e->src)
- && SCHED_COLUMN (e->dest) < SCHED_COLUMN (e->src))
+ if (SCHED_ROW (e->dest->cuid) == SCHED_ROW (e->src->cuid)
+ && SCHED_COLUMN (e->dest->cuid) < SCHED_COLUMN (e->src->cuid))
dest_copy--;
if (dest_copy)
- SET_BIT (uses_of_defs[dest_copy - 1], e->dest->cuid);
- }
+ {
+ ps_reg_move_info *move;
- /* 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)));
- /* Insert the reg-moves right before the notes which precede
- the insn they relates to. */
- last_reg_move = u->first_note;
+ move = ps_reg_move (ps, first_move + dest_copy - 1);
+ SET_BIT (move->uses, e->dest->cuid);
+ if (e->distance == 1)
+ SET_BIT (distance1_uses, e->dest->cuid);
+ }
+ }
+ must_follow = sbitmap_alloc (first_move + nreg_moves);
for (i_reg_move = 0; i_reg_move < nreg_moves; i_reg_move++)
- {
- 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, 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, 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);
+ if (!schedule_reg_move (ps, first_move + i_reg_move,
+ distance1_uses, must_follow))
+ break;
+ sbitmap_free (must_follow);
+ if (distance1_uses)
+ sbitmap_free (distance1_uses);
+ if (i_reg_move < nreg_moves)
+ return false;
}
- return reg_move_replaces;
+ return true;
}
-/* Free memory allocated for the undo buffer. */
+/* Emit the moves associatied with PS. Apply the substitutions
+ associated with them. */
static void
-free_undo_replace_buff (struct undo_replace_buff_elem *reg_move_replaces)
+apply_reg_moves (partial_schedule_ptr ps)
{
+ ps_reg_move_info *move;
+ int i;
- while (reg_move_replaces)
+ FOR_EACH_VEC_ELT (ps_reg_move_info, ps->reg_moves, i, move)
{
- struct undo_replace_buff_elem *rep = reg_move_replaces;
+ unsigned int i_use;
+ sbitmap_iterator sbi;
- reg_move_replaces = reg_move_replaces->next;
- free (rep);
+ EXECUTE_IF_SET_IN_SBITMAP (move->uses, 0, i_use, sbi)
+ {
+ replace_rtx (ps->g->nodes[i_use].insn, move->old_reg, move->new_reg);
+ df_insn_rescan (ps->g->nodes[i_use].insn);
+ }
}
}
-/* 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;
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 u = crr_insn->id;
int normalized_time = SCHED_TIME (u) - amount;
+ int new_min_cycle = PS_MIN_CYCLE (ps) - 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);
+ if (dump_file)
+ {
+ /* Print the scheduling times after the rotation. */
+ rtx insn = ps_rtl_insn (ps, u);
+
+ fprintf (dump_file, "crr_insn->node=%d (insn id %d), "
+ "crr_insn->cycle=%d, min_cycle=%d", u,
+ INSN_UID (insn), normalized_time, new_min_cycle);
+ if (JUMP_P (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;
- }
-}
-
-/* Set SCHED_COLUMN of each node according to its position in PS. */
-static void
-set_columns_for_ps (partial_schedule_ptr ps)
-{
- int row;
-
- for (row = 0; row < ps->ii; row++)
- {
- ps_insn_ptr cur_insn = ps->rows[row];
- int column = 0;
- for (; cur_insn; cur_insn = cur_insn->next_in_row)
- SCHED_COLUMN (cur_insn->node) = column++;
- }
+ crr_insn->cycle = normalized_time;
+ update_node_sched_params (u, ii, normalized_time, new_min_cycle);
+ }
}
-
+
/* Permute the insns according to their order in PS, from row 0 to
row ii-1, and position them right before LAST. This schedules
the insns of the loop kernel. */
for (row = 0; row < ii ; row++)
for (ps_ij = ps->rows[row]; ps_ij; ps_ij = ps_ij->next_in_row)
- if (PREV_INSN (last) != ps_ij->node->insn)
- reorder_insns_nobb (ps_ij->node->first_note, ps_ij->node->insn,
- PREV_INSN (last));
+ {
+ rtx insn = ps_rtl_insn (ps, ps_ij->id);
+
+ if (PREV_INSN (last) != insn)
+ {
+ if (ps_ij->id < ps->g->num_nodes)
+ reorder_insns_nobb (ps_first_note (ps, ps_ij->id), insn,
+ PREV_INSN (last));
+ else
+ add_insn_before (insn, last, NULL);
+ }
+ }
+}
+
+/* Set bitmaps TMP_FOLLOW and TMP_PRECEDE to MUST_FOLLOW and MUST_PRECEDE
+ respectively only if cycle C falls on the border of the scheduling
+ window boundaries marked by START and END cycles. STEP is the
+ direction of the window. */
+static inline void
+set_must_precede_follow (sbitmap *tmp_follow, sbitmap must_follow,
+ sbitmap *tmp_precede, sbitmap must_precede, int c,
+ int start, int end, int step)
+{
+ *tmp_precede = NULL;
+ *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;
+ }
+
+}
+
+/* Return True if the branch can be moved to row ii-1 while
+ normalizing the partial schedule PS to start from cycle zero and thus
+ optimize the SC. Otherwise return False. */
+static bool
+optimize_sc (partial_schedule_ptr ps, ddg_ptr g)
+{
+ int amount = PS_MIN_CYCLE (ps);
+ sbitmap sched_nodes = sbitmap_alloc (g->num_nodes);
+ int start, end, step;
+ int ii = ps->ii;
+ bool ok = false;
+ int stage_count, stage_count_curr;
+
+ /* Compare the SC after normalization and SC after bringing the branch
+ to row ii-1. If they are equal just bail out. */
+ stage_count = calculate_stage_count (ps, amount);
+ stage_count_curr =
+ calculate_stage_count (ps, SCHED_TIME (g->closing_branch->cuid) - (ii - 1));
+
+ if (stage_count == stage_count_curr)
+ {
+ if (dump_file)
+ fprintf (dump_file, "SMS SC already optimized.\n");
+
+ ok = false;
+ goto clear;
+ }
+
+ if (dump_file)
+ {
+ fprintf (dump_file, "SMS Trying to optimize branch location\n");
+ fprintf (dump_file, "SMS partial schedule before trial:\n");
+ print_partial_schedule (ps, dump_file);
+ }
+
+ /* First, normalize the partial scheduling. */
+ reset_sched_times (ps, amount);
+ rotate_partial_schedule (ps, amount);
+ if (dump_file)
+ {
+ fprintf (dump_file,
+ "SMS partial schedule after normalization (ii, %d, SC %d):\n",
+ ii, stage_count);
+ print_partial_schedule (ps, dump_file);
+ }
+
+ if (SMODULO (SCHED_TIME (g->closing_branch->cuid), ii) == ii - 1)
+ {
+ ok = true;
+ goto clear;
+ }
+
+ sbitmap_ones (sched_nodes);
+
+ /* Calculate the new placement of the branch. It should be in row
+ ii-1 and fall into it's scheduling window. */
+ if (get_sched_window (ps, g->closing_branch, sched_nodes, ii, &start,
+ &step, &end) == 0)
+ {
+ bool success;
+ ps_insn_ptr next_ps_i;
+ int branch_cycle = SCHED_TIME (g->closing_branch->cuid);
+ int row = SMODULO (branch_cycle, ps->ii);
+ int num_splits = 0;
+ sbitmap must_precede, must_follow, tmp_precede, tmp_follow;
+ int c;
+
+ if (dump_file)
+ fprintf (dump_file, "\nTrying to schedule node %d "
+ "INSN = %d in (%d .. %d) step %d\n",
+ g->closing_branch->cuid,
+ (INSN_UID (g->closing_branch->insn)), start, end, step);
+
+ gcc_assert ((step > 0 && start < end) || (step < 0 && start > end));
+ if (step == 1)
+ {
+ c = start + ii - SMODULO (start, ii) - 1;
+ gcc_assert (c >= start);
+ if (c >= end)
+ {
+ ok = false;
+ if (dump_file)
+ fprintf (dump_file,
+ "SMS failed to schedule branch at cycle: %d\n", c);
+ goto clear;
+ }
+ }
+ else
+ {
+ c = start - SMODULO (start, ii) - 1;
+ gcc_assert (c <= start);
+
+ if (c <= end)
+ {
+ if (dump_file)
+ fprintf (dump_file,
+ "SMS failed to schedule branch at cycle: %d\n", c);
+ ok = false;
+ goto clear;
+ }
+ }
+
+ must_precede = sbitmap_alloc (g->num_nodes);
+ must_follow = sbitmap_alloc (g->num_nodes);
+
+ /* Try to schedule the branch is it's new cycle. */
+ calculate_must_precede_follow (g->closing_branch, start, end,
+ step, ii, sched_nodes,
+ must_precede, must_follow);
+
+ set_must_precede_follow (&tmp_follow, must_follow, &tmp_precede,
+ must_precede, c, start, end, step);
+
+ /* Find the element in the partial schedule related to the closing
+ branch so we can remove it from it's current cycle. */
+ for (next_ps_i = ps->rows[row];
+ next_ps_i; next_ps_i = next_ps_i->next_in_row)
+ if (next_ps_i->id == g->closing_branch->cuid)
+ break;
+
+ remove_node_from_ps (ps, next_ps_i);
+ success =
+ try_scheduling_node_in_cycle (ps, g->closing_branch->cuid, c,
+ sched_nodes, &num_splits,
+ tmp_precede, tmp_follow);
+ gcc_assert (num_splits == 0);
+ if (!success)
+ {
+ if (dump_file)
+ fprintf (dump_file,
+ "SMS failed to schedule branch at cycle: %d, "
+ "bringing it back to cycle %d\n", c, branch_cycle);
+
+ /* The branch was failed to be placed in row ii - 1.
+ Put it back in it's original place in the partial
+ schedualing. */
+ set_must_precede_follow (&tmp_follow, must_follow, &tmp_precede,
+ must_precede, branch_cycle, start, end,
+ step);
+ success =
+ try_scheduling_node_in_cycle (ps, g->closing_branch->cuid,
+ branch_cycle, sched_nodes,
+ &num_splits, tmp_precede,
+ tmp_follow);
+ gcc_assert (success && (num_splits == 0));
+ ok = false;
+ }
+ else
+ {
+ /* The branch is placed in row ii - 1. */
+ if (dump_file)
+ fprintf (dump_file,
+ "SMS success in moving branch to cycle %d\n", c);
+
+ update_node_sched_params (g->closing_branch->cuid, ii, c,
+ PS_MIN_CYCLE (ps));
+ ok = true;
+ }
+
+ free (must_precede);
+ free (must_follow);
+ }
+
+clear:
+ free (sched_nodes);
+ return ok;
}
static void
duplicate_insns_of_cycles (partial_schedule_ptr ps, int from_stage,
- int to_stage, int for_prolog, rtx count_reg)
+ int to_stage, rtx count_reg)
{
int row;
ps_insn_ptr ps_ij;
for (row = 0; row < ps->ii; row++)
for (ps_ij = ps->rows[row]; ps_ij; ps_ij = ps_ij->next_in_row)
{
- ddg_node_ptr u_node = ps_ij->node;
- int j, i_reg_moves;
- rtx reg_move = NULL_RTX;
+ int u = ps_ij->id;
+ int first_u, last_u;
+ rtx u_insn;
/* 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))
+ u_insn = ps_rtl_insn (ps, u);
+ if (reg_mentioned_p (count_reg, u_insn)
+ || JUMP_P (u_insn))
continue;
- if (for_prolog)
+ first_u = SCHED_STAGE (u);
+ last_u = first_u + ps_num_consecutive_stages (ps, u) - 1;
+ if (from_stage <= last_u && to_stage >= first_u)
{
- /* 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) + 1;
- i_reg_moves = MAX (i_reg_moves, 0);
- i_reg_moves = MIN (i_reg_moves, SCHED_NREG_MOVES (u_node));
-
- /* The reg_moves start from the *first* reg_move backwards. */
- if (i_reg_moves)
- {
- reg_move = SCHED_FIRST_REG_MOVE (u_node);
- for (j = 1; j < i_reg_moves; j++)
- reg_move = PREV_INSN (reg_move);
- }
+ if (u < ps->g->num_nodes)
+ duplicate_insn_chain (ps_first_note (ps, u), u_insn);
+ else
+ emit_insn (copy_rtx (PATTERN (u_insn)));
}
- else /* It's for the epilog. */
- {
- /* SCHED_STAGE (u_node) <= to_stage. Generate all reg_moves,
- starting to decrease one stage after u_node no longer occurs;
- that is, generate all reg_moves until
- SCHED_STAGE (u_node) == from_stage - 1. */
- i_reg_moves = SCHED_NREG_MOVES (u_node)
- - (from_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));
-
- /* The reg_moves start from the *last* reg_move forwards. */
- if (i_reg_moves)
- {
- reg_move = SCHED_FIRST_REG_MOVE (u_node);
- for (j = 1; j < SCHED_NREG_MOVES (u_node); j++)
- reg_move = PREV_INSN (reg_move);
- }
- }
-
- 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);
}
}
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);
-
+ duplicate_insns_of_cycles (ps, 0, i, count_reg);
+
/* Put the prolog on the entry edge. */
e = loop_preheader_edge (loop);
split_edge_and_insert (e, get_insns ());
+ if (!flag_resched_modulo_sched)
+ e->dest->flags |= BB_DISABLE_SCHEDULE;
end_sequence ();
start_sequence ();
for (i = 0; i < last_stage; i++)
- duplicate_insns_of_cycles (ps, i + 1, last_stage, 0, count_reg);
-
+ duplicate_insns_of_cycles (ps, i + 1, last_stage, count_reg);
+
/* Put the epilogue on the exit edge. */
gcc_assert (single_exit (loop));
e = single_exit (loop);
split_edge_and_insert (e, get_insns ());
+ if (!flag_resched_modulo_sched)
+ e->dest->flags |= BB_DISABLE_SCHEDULE;
+
end_sequence ();
}
+/* Mark LOOP as software pipelined so the later
+ scheduling passes don't touch it. */
+static void
+mark_loop_unsched (struct loop *loop)
+{
+ unsigned i;
+ basic_block *bbs = get_loop_body (loop);
+
+ for (i = 0; i < loop->num_nodes; i++)
+ bbs[i]->flags |= BB_DISABLE_SCHEDULE;
+
+ free (bbs);
+}
+
/* Return true if all the BBs of the loop are empty except the
loop header. */
static bool
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;
return true;
}
+/* Dump file:line from INSN's location info to dump_file. */
+
+static void
+dump_insn_locator (rtx insn)
+{
+ if (dump_file && INSN_LOCATOR (insn))
+ {
+ const char *file = insn_file (insn);
+ if (file)
+ fprintf (dump_file, " %s:%i", file, insn_line (insn));
+ }
+}
+
/* 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 ) \
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));
+
+ fprintf (dump_file, "SMS loop many exits");
+ dump_insn_locator (insn);
+ fprintf (dump_file, "\n");
}
return false;
}
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));
+
+ fprintf (dump_file, "SMS loop many BBs.");
+ dump_insn_locator (insn);
+ fprintf (dump_file, "\n");
}
return false;
}
}
if (dump_file)
- {
- rtx insn = BB_END (loop->header);
-
- fprintf (dump_file, "SMS loop num: %d, file: %s, line: %d\n",
- loop->num, insn_file (insn), insn_line (insn));
+ {
+ rtx insn = BB_END (loop->header);
- }
+ fprintf (dump_file, "SMS loop num: %d", loop->num);
+ dump_insn_locator (insn);
+ fprintf (dump_file, "\n");
+ }
if (! loop_canon_p (loop))
continue;
{
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");
+ dump_insn_locator (tail);
+ fprintf (dump_file, "\nSMS single-bb-loop\n");
if (profile_info && flag_branch_probabilities)
{
fprintf (dump_file, "SMS loop-count ");
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).
- ??? Should handle auto-increment insns.
+ /* Don't handle BBs with calls or barriers
+ 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 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)
- || (FIND_REG_INC_NOTE (insn, NULL_RTX) != 0)
+ || (NONDEBUG_INSN_P (insn) && !JUMP_P (insn)
+ && !single_set (insn) && GET_CODE (PATTERN (insn)) != USE
+ && !reg_mentioned_p (count_reg, insn))
|| (INSN_P (insn) && (set = single_set (insn))
&& GET_CODE (SET_DEST (set)) == SUBREG))
break;
fprintf (dump_file, "SMS loop-with-call\n");
else if (BARRIER_P (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 ((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");
{
rtx head, tail;
rtx count_reg, count_init;
- int mii, rec_mii;
- unsigned stage_count = 0;
+ int mii, rec_mii, stage_count, min_cycle;
HOST_WIDEST_INT loop_count = 0;
+ bool opt_sc_p;
if (! (g = g_arr[loop->num]))
continue;
if (dump_file)
- {
- rtx insn = BB_END (loop->header);
+ {
+ rtx insn = BB_END (loop->header);
- fprintf (dump_file, "SMS loop num: %d, file: %s, line: %d\n",
- loop->num, insn_file (insn), insn_line (insn));
+ fprintf (dump_file, "SMS loop num: %d", loop->num);
+ dump_insn_locator (insn);
+ fprintf (dump_file, "\n");
- print_ddg (dump_file, g);
- }
+ print_ddg (dump_file, g);
+ }
get_ebb_head_tail (loop->header, loop->header, &head, &tail);
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");
+ dump_insn_locator (tail);
+ fprintf (dump_file, "\nSMS single-bb-loop\n");
if (profile_info && flag_branch_probabilities)
{
fprintf (dump_file, "SMS loop-count ");
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);
+ for (;;)
+ {
+ set_node_sched_params (g);
- if (ps)
- stage_count = PS_STAGE_COUNT (ps);
+ stage_count = 0;
+ opt_sc_p = false;
+ ps = sms_schedule_by_order (g, mii, maxii, node_order);
- /* 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)
+ if (ps)
{
- 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");
+ /* Try to achieve optimized SC by normalizing the partial
+ schedule (having the cycles start from cycle zero).
+ The branch location must be placed in row ii-1 in the
+ final scheduling. If failed, shift all instructions to
+ position the branch in row ii-1. */
+ opt_sc_p = optimize_sc (ps, g);
+ if (opt_sc_p)
+ stage_count = calculate_stage_count (ps, 0);
+ else
+ {
+ /* Bring the branch to cycle ii-1. */
+ int amount = (SCHED_TIME (g->closing_branch->cuid)
+ - (ps->ii - 1));
+
+ if (dump_file)
+ fprintf (dump_file, "SMS schedule branch at cycle ii-1\n");
+
+ stage_count = calculate_stage_count (ps, amount);
+ }
+
+ gcc_assert (stage_count >= 1);
}
- continue;
- }
- else
- {
- struct undo_replace_buff_elem *reg_move_replaces;
- if (dump_file)
+ /* 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 < PARAM_VALUE (PARAM_SMS_MIN_SC)
+ || (count_init && (loop_count <= stage_count))
+ || (flag_branch_probabilities && (trip_count <= stage_count)))
{
- 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);
+ if (dump_file)
+ {
+ 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");
+ }
+ break;
}
- /* 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);
+ if (!opt_sc_p)
+ {
+ /* Rotate the partial schedule to have the branch in row ii-1. */
+ int amount = SCHED_TIME (g->closing_branch->cuid) - (ps->ii - 1);
+
+ reset_sched_times (ps, amount);
+ rotate_partial_schedule (ps, amount);
+ }
+ set_columns_for_ps (ps);
+
+ min_cycle = PS_MIN_CYCLE (ps) - SMODULO (PS_MIN_CYCLE (ps), ps->ii);
+ if (!schedule_reg_moves (ps))
+ {
+ mii = ps->ii + 1;
+ free_partial_schedule (ps);
+ continue;
+ }
+
+ /* Moves that handle incoming values might have been added
+ to a new first stage. Bump the stage count if so.
+
+ ??? Perhaps we could consider rotating the schedule here
+ instead? */
+ if (PS_MIN_CYCLE (ps) < min_cycle)
+ {
+ reset_sched_times (ps, 0);
+ stage_count++;
+ }
+
+ /* The stage count should now be correct without rotation. */
+ gcc_checking_assert (stage_count == calculate_stage_count (ps, 0));
+ PS_STAGE_COUNT (ps) = stage_count;
+
canon_loop (loop);
+ if (dump_file)
+ {
+ dump_insn_locator (tail);
+ fprintf (dump_file, " SMS succeeded %d %d (with ii, sc)\n",
+ ps->ii, stage_count);
+ print_partial_schedule (ps, dump_file);
+ }
+
/* case the BCT count is not known , Do loop-versioning */
if (count_reg && ! count_init)
{
permute_partial_schedule (ps, g->closing_branch->first_note);
/* Mark this loop as software pipelined so the later
- scheduling passes doesn't touch it. */
+ scheduling passes don't touch it. */
if (! flag_resched_modulo_sched)
- g->bb->flags |= BB_DISABLE_SCHEDULE;
+ mark_loop_unsched (loop);
+
/* The life-info is not valid any more. */
df_set_bb_dirty (g->bb);
- reg_move_replaces = generate_reg_moves (ps, true);
+ apply_reg_moves (ps);
if (dump_file)
- print_node_sched_params (dump_file, g->num_nodes, g);
+ print_node_sched_params (dump_file, g->num_nodes, ps);
/* Generate prolog and epilog. */
generate_prolog_epilog (ps, loop, count_reg, count_init);
-
- free_undo_replace_buff (reg_move_replaces);
+ break;
}
free_partial_schedule (ps);
- free (node_sched_params);
+ VEC_free (node_sched_params, heap, node_sched_param_vec);
free (node_order);
free_ddg (g);
}
41. endif
42. compute epilogue & prologue
43. finish - succeeded to schedule
-*/
+
+ ??? The algorithm restricts the scheduling window to II cycles.
+ In rare cases, it may be better to allow windows of II+1 cycles.
+ The window would then start and end on the same row, but with
+ different "must precede" and "must follow" requirements. */
/* A limit on the number of cycles that resource conflicts can span. ??? Should
be provided by DFA, and be dependent on the type of insn scheduled. Currently
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)
+get_sched_window (partial_schedule_ptr ps, ddg_node_ptr u_node,
+ sbitmap sched_nodes, int ii, int *start_p, int *step_p,
+ int *end_p)
{
int start, step, end;
+ int early_start, late_start;
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;
+ int count_preds;
+ int count_succs;
/* 1. compute sched window for u (start, end, step). */
sbitmap_zero (psp);
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;
+ /* We first compute a forward range (start <= end), then decide whether
+ to reverse it. */
+ early_start = INT_MIN;
+ late_start = INT_MAX;
+ start = INT_MIN;
+ end = INT_MAX;
+ step = 1;
- 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));
- }
+ count_preds = 0;
+ count_succs = 0;
- 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)
+ if (dump_file && (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);
-
+ fprintf (dump_file, "\nAnalyzing dependencies for node %d (INSN %d)"
+ "; ii = %d\n\n", u_node->cuid, INSN_UID (u_node->insn), ii);
+ fprintf (dump_file, "%11s %11s %11s %11s %5s\n",
+ "start", "early start", "late start", "end", "time");
+ fprintf (dump_file, "=========== =========== =========== ==========="
+ " =====\n");
}
+ /* Calculate early_start and limit end. Both bounds are inclusive. */
+ if (psp_not_empty)
+ for (e = u_node->in; e != 0; e = e->next_in)
+ {
+ int v = e->src->cuid;
- 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);
+ if (TEST_BIT (sched_nodes, v))
+ {
+ int p_st = SCHED_TIME (v);
+ int earliest = p_st + e->latency - (e->distance * ii);
+ int latest = (e->data_type == MEM_DEP ? p_st + ii - 1 : INT_MAX);
- early_start = MAX (early_start,
- p_st + e->latency
- - (e->distance * ii));
+ if (dump_file)
+ {
+ fprintf (dump_file, "%11s %11d %11s %11d %5d",
+ "", earliest, "", latest, p_st);
+ print_ddg_edge (dump_file, e);
+ fprintf (dump_file, "\n");
+ }
- if (dump_file)
- fprintf (dump_file,
- "pred st = %d; early_start = %d; latency = %d",
- p_st, early_start, e->latency);
+ early_start = MAX (early_start, earliest);
+ end = MIN (end, latest);
- if (e->type == TRUE_DEP && e->data_type == REG_DEP)
- count_preds++;
+ 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");
+ /* Calculate late_start and limit start. Both bounds are inclusive. */
+ if (pss_not_empty)
+ for (e = u_node->out; e != 0; e = e->next_out)
+ {
+ int v = e->dest->cuid;
- }
- for (e = u_node->out; e != 0; e = e->next_out)
- {
- ddg_node_ptr v_node = e->dest;
+ if (TEST_BIT (sched_nodes, v))
+ {
+ int s_st = SCHED_TIME (v);
+ int earliest = (e->data_type == MEM_DEP ? s_st - ii + 1 : INT_MIN);
+ int latest = s_st - e->latency + (e->distance * ii);
- 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 (dump_file)
+ {
+ fprintf (dump_file, "%11d %11s %11d %11s %5d",
+ earliest, "", latest, "", s_st);
+ print_ddg_edge (dump_file, e);
+ fprintf (dump_file, "\n");
+ }
- if (TEST_BIT (sched_nodes, v_node->cuid))
- {
- int s_st = SCHED_TIME (v_node);
+ start = MAX (start, earliest);
+ late_start = MIN (late_start, latest);
- late_start = MIN (late_start,
- s_st - e->latency
- + (e->distance * ii));
+ if (e->type == TRUE_DEP && e->data_type == REG_DEP)
+ count_succs++;
+ }
+ }
- if (dump_file)
- fprintf (dump_file,
- "succ st = %d; late_start = %d; latency = %d",
- s_st, late_start, e->latency);
+ if (dump_file && (psp_not_empty || pss_not_empty))
+ {
+ fprintf (dump_file, "----------- ----------- ----------- -----------"
+ " -----\n");
+ fprintf (dump_file, "%11d %11d %11d %11d %5s %s\n",
+ start, early_start, late_start, end, "",
+ "(max, max, min, min)");
+ }
- if (e->type == TRUE_DEP && e->data_type == REG_DEP)
- count_succs++;
+ /* Get a target scheduling window no bigger than ii. */
+ if (early_start == INT_MIN && late_start == INT_MAX)
+ early_start = NODE_ASAP (u_node);
+ else if (early_start == INT_MIN)
+ early_start = late_start - (ii - 1);
+ late_start = MIN (late_start, early_start + (ii - 1));
- 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");
+ /* Apply memory dependence limits. */
+ start = MAX (start, early_start);
+ end = MIN (end, late_start);
- }
- 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;
+ if (dump_file && (psp_not_empty || pss_not_empty))
+ fprintf (dump_file, "%11s %11d %11d %11s %5s final window\n",
+ "", start, end, "", "");
- start = end - 1;
- end = old_start - 1;
- step = -1;
- }
- }
- else /* psp is empty && pss is empty. */
+ /* If there are at least as many successors as predecessors, schedule the
+ node close to its successors. */
+ if (pss_not_empty && count_succs >= count_preds)
{
- start = SCHED_ASAP (u_node);
- end = start + ii;
- step = 1;
+ int tmp = end;
+ end = start;
+ start = tmp;
+ step = -1;
}
+ /* Now that we've finalized the window, make END an exclusive rather
+ than an inclusive bound. */
+ end += step;
+
*start_p = start;
*step_p = step;
*end_p = end;
if (dump_file)
fprintf (dump_file, "\nEmpty window: start=%d, end=%d, step=%d\n",
start, end, step);
- return -1;
+ return -1;
}
- return 0;
+ return 0;
}
/* Calculate MUST_PRECEDE/MUST_FOLLOW bitmaps of U_NODE; which is the
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)) ==
+ && ((SCHED_TIME (e->src->cuid) - (e->distance * ii)) ==
first_cycle_in_window))
{
if (dump_file)
&& 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 */
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)) ==
+ && ((SCHED_TIME (e->dest->cuid) + (e->distance * ii)) ==
last_cycle_in_window))
{
if (dump_file)
last row of the scheduling window) */
static bool
-try_scheduling_node_in_cycle (partial_schedule_ptr ps, ddg_node_ptr u_node,
+try_scheduling_node_in_cycle (partial_schedule_ptr ps,
int u, int cycle, sbitmap sched_nodes,
int *num_splits, sbitmap must_precede,
sbitmap must_follow)
bool success = 0;
verify_partial_schedule (ps, sched_nodes);
- psi = ps_add_node_check_conflicts (ps, u_node, cycle,
- must_precede, must_follow);
+ psi = ps_add_node_check_conflicts (ps, u, cycle, must_precede, must_follow);
if (psi)
{
- SCHED_TIME (u_node) = cycle;
+ SCHED_TIME (u) = cycle;
SET_BIT (sched_nodes, u);
success = 1;
*num_splits = 0;
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;
/* Try to get non-empty scheduling window. */
success = 0;
- if (get_sched_window (ps, nodes_order, i, sched_nodes, ii, &start,
+ if (get_sched_window (ps, u_node, 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
+ 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)
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;
- }
+ sbitmap tmp_precede, tmp_follow;
+ set_must_precede_follow (&tmp_follow, must_follow,
+ &tmp_precede, must_precede,
+ c, start, end, step);
success =
- try_scheduling_node_in_cycle (ps, u_node, u, c,
+ try_scheduling_node_in_cycle (ps, u, c,
sched_nodes,
&num_splits, tmp_precede,
tmp_follow);
int ii = ps->ii;
int new_ii = ii + 1;
int row;
+ int *rows_length_new;
verify_partial_schedule (ps, sched_nodes);
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));
+ rows_length_new = (int *) xcalloc (new_ii, sizeof (int));
for (row = 0; row < split_row; row++)
{
rows_new[row] = ps->rows[row];
+ rows_length_new[row] = ps->rows_length[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 u = crr_insn->id;
int new_time = SCHED_TIME (u) + (SCHED_TIME (u) / ii);
SCHED_TIME (u) = new_time;
for (row = split_row; row < ii; row++)
{
rows_new[row + 1] = ps->rows[row];
+ rows_length_new[row + 1] = ps->rows_length[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 u = crr_insn->id;
int new_time = SCHED_TIME (u) + (SCHED_TIME (u) / ii) + 1;
SCHED_TIME (u) = new_time;
+ (SMODULO (ps->max_cycle, ii) >= split_row ? 1 : 0);
free (ps->rows);
ps->rows = rows_new;
+ free (ps->rows_length);
+ ps->rows_length = rows_length_new;
ps->ii = new_ii;
gcc_assert (ps->min_cycle >= 0);
{
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_pred = -1;
+ int crit_succ = -1;
int crit_cycle;
for (e = u_node->in; e != 0; e = e->next_in)
{
- ddg_node_ptr v_node = e->src;
+ int v = e->src->cuid;
- if (TEST_BIT (sched_nodes, v_node->cuid)
- && (low == SCHED_TIME (v_node) + e->latency - (e->distance * ii)))
- if (SCHED_TIME (v_node) > lower)
+ if (TEST_BIT (sched_nodes, v)
+ && (low == SCHED_TIME (v) + e->latency - (e->distance * ii)))
+ if (SCHED_TIME (v) > lower)
{
- crit_pred = v_node;
- lower = SCHED_TIME (v_node);
+ crit_pred = v;
+ lower = SCHED_TIME (v);
}
}
- if (crit_pred != NULL)
+ if (crit_pred >= 0)
{
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)
+ int v = e->dest->cuid;
+
+ if (TEST_BIT (sched_nodes, v)
+ && (up == SCHED_TIME (v) - e->latency + (e->distance * ii)))
+ if (SCHED_TIME (v) < upper)
{
- crit_succ = v_node;
- upper = SCHED_TIME (v_node);
+ crit_succ = v;
+ upper = SCHED_TIME (v);
}
}
- if (crit_succ != NULL)
+ if (crit_succ >= 0)
{
crit_cycle = SCHED_TIME (crit_succ);
return SMODULO (crit_cycle, ii);
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);
- }
+ {
+ int length = 0;
+
+ for (crr_insn = ps->rows[row]; crr_insn; crr_insn = crr_insn->next_in_row)
+ {
+ int u = crr_insn->id;
+
+ length++;
+ gcc_assert (TEST_BIT (sched_nodes, u));
+ /* ??? 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);
+ }
+
+ gcc_assert (ps->rows_length[row] == length);
+ }
}
\f
SET_BIT (tmp, u);
}
-
+
if (dump_file)
fprintf (dump_file, "\n");
-
+
sbitmap_free (tmp);
}
{
partial_schedule_ptr ps = XNEW (struct partial_schedule);
ps->rows = (ps_insn_ptr *) xcalloc (ii, sizeof (ps_insn_ptr));
+ ps->rows_length = (int *) xcalloc (ii, sizeof (int));
+ ps->reg_moves = NULL;
ps->ii = ii;
ps->history = history;
ps->min_cycle = INT_MAX;
static void
free_partial_schedule (partial_schedule_ptr ps)
{
+ ps_reg_move_info *move;
+ unsigned int i;
+
if (!ps)
return;
+
+ FOR_EACH_VEC_ELT (ps_reg_move_info, ps->reg_moves, i, move)
+ sbitmap_free (move->uses);
+ VEC_free (ps_reg_move_info, heap, ps->reg_moves);
+
free_ps_insns (ps);
free (ps->rows);
+ free (ps->rows_length);
free (ps);
}
ps->rows = (ps_insn_ptr *) xrealloc (ps->rows, new_ii
* sizeof (ps_insn_ptr));
memset (ps->rows, 0, new_ii * sizeof (ps_insn_ptr));
+ ps->rows_length = (int *) xrealloc (ps->rows_length, new_ii * sizeof (int));
+ memset (ps->rows_length, 0, new_ii * sizeof (int));
ps->ii = new_ii;
ps->min_cycle = INT_MAX;
ps->max_cycle = INT_MIN;
fprintf (dump, "\n[ROW %d ]: ", i);
while (ps_i)
{
- fprintf (dump, "%d, ",
- INSN_UID (ps_i->node->insn));
+ rtx insn = ps_rtl_insn (ps, ps_i->id);
+
+ if (JUMP_P (insn))
+ fprintf (dump, "%d (branch), ", INSN_UID (insn));
+ else
+ fprintf (dump, "%d, ", INSN_UID (insn));
+
ps_i = ps_i->next_in_row;
}
}
/* Creates an object of PS_INSN and initializes it to the given parameters. */
static ps_insn_ptr
-create_ps_insn (ddg_node_ptr node, int rest_count, int cycle)
+create_ps_insn (int id, int cycle)
{
ps_insn_ptr ps_i = XNEW (struct ps_insn);
- ps_i->node = node;
+ ps_i->id = id;
ps_i->next_in_row = NULL;
ps_i->prev_in_row = NULL;
- ps_i->row_rest_count = rest_count;
ps_i->cycle = cycle;
return ps_i;
}
-/* 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 bool
+/* Removes the given PS_INSN from the partial schedule. */
+static void
remove_node_from_ps (partial_schedule_ptr ps, ps_insn_ptr ps_i)
{
int row;
- if (!ps || !ps_i)
- return false;
-
+ gcc_assert (ps && ps_i);
+
row = SMODULO (ps_i->cycle, ps->ii);
if (! ps_i->prev_in_row)
{
- if (ps_i != ps->rows[row])
- return false;
-
+ gcc_assert (ps_i == ps->rows[row]);
ps->rows[row] = ps_i->next_in_row;
if (ps->rows[row])
ps->rows[row]->prev_in_row = NULL;
if (ps_i->next_in_row)
ps_i->next_in_row->prev_in_row = ps_i->prev_in_row;
}
+
+ ps->rows_length[row] -= 1;
free (ps_i);
- return true;
+ return;
}
/* Unlike what literature describes for modulo scheduling (which focuses
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)
next_ps_i;
next_ps_i = next_ps_i->next_in_row)
{
- if (must_follow && TEST_BIT (must_follow, next_ps_i->node->cuid)
+ if (must_follow
+ && TEST_BIT (must_follow, next_ps_i->id)
&& ! first_must_follow)
first_must_follow = next_ps_i;
- if (must_precede && TEST_BIT (must_precede, next_ps_i->node->cuid))
+ if (must_precede && TEST_BIT (must_precede, next_ps_i->id))
{
/* If we have already met a node that must follow, then
there is no possible column. */
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->id)
+ && JUMP_P (ps_rtl_insn (ps, next_ps_i->id)))
+ 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_rtl_insn (ps, ps_i->id)))
+ {
+ 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,
{
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 (must_follow && TEST_BIT (must_follow, next_node->cuid))
+ if (must_follow && TEST_BIT (must_follow, ps_i->next_in_row->id))
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,
+add_node_to_ps (partial_schedule_ptr ps, int id, int cycle,
sbitmap must_precede, sbitmap must_follow)
{
ps_insn_ptr ps_i;
- int rest_count = 1;
int row = SMODULO (cycle, ps->ii);
- if (ps->rows[row]
- && ps->rows[row]->row_rest_count >= issue_rate)
+ if (ps->rows_length[row] >= issue_rate)
return NULL;
- if (ps->rows[row])
- rest_count += ps->rows[row]->row_rest_count;
-
- ps_i = create_ps_insn (node, rest_count, cycle);
+ ps_i = create_ps_insn (id, cycle);
/* Finds and inserts PS_I according to MUST_FOLLOW and
MUST_PRECEDE. */
return NULL;
}
+ ps->rows_length[row] += 1;
return ps_i;
}
crr_insn;
crr_insn = crr_insn->next_in_row)
{
- rtx insn = crr_insn->node->insn;
+ rtx insn = ps_rtl_insn (ps, crr_insn->id);
- 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,
+ps_add_node_check_conflicts (partial_schedule_ptr ps, int n,
int c, sbitmap must_precede,
sbitmap must_follow)
{
return ps_i;
}
+/* Calculate the stage count of the partial schedule PS. The calculation
+ takes into account the rotation amount passed in ROTATION_AMOUNT. */
+int
+calculate_stage_count (partial_schedule_ptr ps, int rotation_amount)
+{
+ 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
for (i = 0; i < backward_rotates; i++)
{
ps_insn_ptr first_row = ps->rows[0];
+ int first_row_length = ps->rows_length[0];
for (row = 0; row < last_row; row++)
- ps->rows[row] = ps->rows[row+1];
+ {
+ ps->rows[row] = ps->rows[row + 1];
+ ps->rows_length[row] = ps->rows_length[row + 1];
+ }
ps->rows[last_row] = first_row;
+ ps->rows_length[last_row] = first_row_length;
}
ps->max_cycle -= start_cycle;
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 */
+ 0, /* todo_flags_start */
+ TODO_df_finish
+ | TODO_verify_flow
+ | TODO_verify_rtl_sharing
+ | TODO_ggc_collect /* todo_flags_finish */
}
};
-
OSDN Git Service
