/* Swing Modulo Scheduling implementation.
- Copyright (C) 2004
+ Copyright (C) 2004, 2005
Free Software Foundation, Inc.
Contributed by Ayal Zaks and Mustafa Hagog <zaks,mustafa@il.ibm.com>
#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"
};
-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,
- sbitmap must_precede,
- sbitmap must_follow);
-void rotate_partial_schedule (partial_schedule_ptr, int);
-void set_row_column_for_ps (partial_schedule_ptr);
-
+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);
\f
/* This page defines constants and structures for the modulo scheduling
driver. */
{
rtx insn;
rtx head, tail;
+
+ if (! pre_header)
+ return NULL_RTX;
+
get_block_head_tail (pre_header->index, &head, &tail);
for (insn = tail; insn != PREV_INSN (head); insn = PREV_INSN (insn))
{
int i;
+ if (! dump_file)
+ return;
for (i = 0; i < num_nodes; i++)
{
node_sched_params_ptr nsp = &node_sched_params[i];
return maxii;
}
-
-/* Given the partial schedule, generate register moves when the length
- of the register live range is more than ii; the number of moves is
- determined according to the following equation:
- SCHED_TIME (use) - SCHED_TIME (def) { 1 broken loop-carried
- nreg_moves = ----------------------------------- - { dependence.
- ii { 0 if not.
- This handles the modulo-variable-expansions (mve's) needed for the ps. */
+/*
+ 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 - { dependecnce.
+ ii { 1 if not.
+*/
static void
generate_reg_moves (partial_schedule_ptr ps)
{
{
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--;
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;
- gcc_assert (normalized_time >= 0);
+ if (normalized_time < 0)
+ abort ();
SCHED_TIME (u) = normalized_time;
SCHED_ROW (u) = normalized_time % ii;
/* 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));
rtx orig_loop_bct = NULL_RTX;
/* Loop header edge. */
- e = ps->g->bb->pred;
+ e = EDGE_PRED (ps->g->bb, 0);
if (e->src == ps->g->bb)
- e = e->pred_next;
+ e = EDGE_PRED (ps->g->bb, 1);
/* Generate the prolog, inserting its insns on the loop-entry edge. */
start_sequence ();
label = XEXP (SET_SRC (cmp), 1);
cond = XEXP (SET_SRC (cmp), 0);
- gcc_assert (c_reg);
- gcc_assert (GET_CODE (cond) == NE);
+ if (! c_reg || GET_CODE (cond) != NE)
+ abort ();
XEXP (label, 0) = precond_exit_label;
JUMP_LABEL (orig_loop_bct) = precond_exit_label_insn;
loop_exit_label_insn = emit_label (loop_exit_label);
}
- e = ps->g->bb->succ;
+ e = EDGE_SUCC (ps->g->bb, 0);
if (e->dest == ps->g->bb)
- e = e->succ_next;
+ e = EDGE_SUCC (ps->g->bb, 1);
e->insns.r = get_insns ();
end_sequence ();
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;
+ edge epilog_exit_edge = single_succ_edge (epilog_bb);
/* Do loop preconditioning to take care of cases were the loop count is
less than the stage count. Update the CFG properly. */
continue;
/* Check if bb has two successors, one being itself. */
- e = bb->succ;
- if (!e || !e->succ_next || e->succ_next->succ_next)
+ if (EDGE_COUNT (bb->succs) != 2)
continue;
- if (e->dest != bb && e->succ_next->dest != bb)
+ if (EDGE_SUCC (bb, 0)->dest != bb && EDGE_SUCC (bb, 1)->dest != bb)
continue;
- if ((e->flags & EDGE_COMPLEX)
- || (e->succ_next->flags & EDGE_COMPLEX))
+ if ((EDGE_SUCC (bb, 0)->flags & EDGE_COMPLEX)
+ || (EDGE_SUCC (bb, 1)->flags & EDGE_COMPLEX))
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)
+ if (EDGE_COUNT (bb->preds) != 2)
continue;
- if (e->src != bb && e->pred_next->src != bb)
+ if (EDGE_PRED (bb, 0)->src != bb && EDGE_PRED (bb, 1)->src != bb)
continue;
- if ((e->flags & EDGE_COMPLEX)
- || (e->pred_next->flags & EDGE_COMPLEX))
+ if ((EDGE_PRED (bb, 0)->flags & EDGE_COMPLEX)
+ || (EDGE_PRED (bb, 1)->flags & EDGE_COMPLEX))
continue;
/* For debugging. */
}
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;
+ pre_header_edge = EDGE_PRED (bb, 0);
+ if (EDGE_PRED (bb, 0)->src != bb)
+ pre_header_edge = EDGE_PRED (bb, 1);
/* 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 ( !(count_reg = doloop_register_get (tail, &comp)))
continue;
- e = bb->pred;
+ e = EDGE_PRED (bb, 0);
if (e->src == bb)
- pre_header = e->pred_next->src;
+ pre_header = EDGE_PRED (bb, 1)->src;
else
pre_header = e->src;
get_block_head_tail (g->bb->index, &head, &tail);
- pre_header_edge = g->bb->pred;
- if (g->bb->pred->src != g->bb)
- pre_header_edge = g->bb->pred->pred_next;
+ pre_header_edge = EDGE_PRED (g->bb, 0);
+ if (EDGE_PRED (g->bb, 0)->src != g->bb)
+ pre_header_edge = EDGE_PRED (g->bb, 1);
if (stats_file)
{
}
/* Make sure this is a doloop. */
- count_reg = doloop_register_get (tail, &comp);
- gcc_assert (count_reg);
+ 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);
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;
generate_reg_moves (ps);
if (dump_file)
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);
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);
+ psp_not_empty = sbitmap_any_common_bits (u_node_preds, sched_nodes);
+ pss_not_empty = sbitmap_any_common_bits (u_node_succs, sched_nodes);
if (psp_not_empty && !pss_not_empty)
{
} /* While try_again_with_larger_ii. */
sbitmap_free (sched_nodes);
- sbitmap_free (psp);
- sbitmap_free (pss);
if (ii >= maxii)
{
{
int u = node_order[i];
- gcc_assert (u < num_nodes);
- gcc_assert (u >= 0);
- gcc_assert (!TEST_BIT (tmp, u));
+ if (u >= num_nodes || u < 0 || TEST_BIT (tmp, u))
+ abort ();
SET_BIT (tmp, u);
}
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)
}
/* 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)
/* 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. */
+ 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)
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
+static ps_insn_ptr
ps_add_node_check_conflicts (partial_schedule_ptr ps, ddg_node_ptr n,
int c, sbitmap must_precede,
sbitmap must_follow)
/* Rotate the rows of PS such that insns scheduled at time
START_CYCLE will appear in row 0. Updates max/min_cycles. */
-void
+static void
rotate_partial_schedule (partial_schedule_ptr ps, int start_cycle)
{
int i, row, backward_rotates;
OSDN Git Service
