Hello,
This patch support the estimation of register pressure in SMS.
Although GCC is in stage 3 I would appreciate comments on it.
Thanks to Richard and Ayal for discussing the implementation and their insights.
This part of the patch enables iterating on the partial schedule in the
reverse order (from the last instruction the the first).
Tested and bootstrap with the other patches in the series on
ppc64-redhat-linux,
enabling SMS on loops with SC 1.
Comments are welcome.
Thanks,
Revital
Changelog:
* modulo-sched.c (rows_reverse): New field in struct partial_schedule.
(create_partial_schedule, free_partial_schedule,
ps_insert_empty_row, ps_insn_advance_column,
ps_insn_find_column, remove_node_from_ps, reset_partial_schedule,
rotate_partial_schedule, verify_partial_schedule): Update the
new field.
Index: modulo-sched.c
===================================================================
--- modulo-sched.c (revision 181149)
+++ modulo-sched.c (working copy)
@@ -177,6 +177,10 @@ struct partial_schedule
/* rows[i] points to linked list of insns scheduled in row i (0<=i<ii). */
ps_insn_ptr *rows;
+ /* rows_reverse[i] points to the last insn in the linked list pointed
+ by rows[i]. */
+ ps_insn_ptr *rows_reverse;
+
/* 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;
@@ -2272,6 +2276,7 @@ ps_insert_empty_row (partial_schedule_pt
{
ps_insn_ptr crr_insn;
ps_insn_ptr *rows_new;
+ ps_insn_ptr *rows_reverse_new;
int ii = ps->ii;
int new_ii = ii + 1;
int row;
@@ -2290,10 +2295,12 @@ ps_insert_empty_row (partial_schedule_pt
rotate_partial_schedule (ps, PS_MIN_CYCLE (ps));
rows_new = (ps_insn_ptr *) xcalloc (new_ii, sizeof (ps_insn_ptr));
+ rows_reverse_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_reverse_new[row] = ps->rows_reverse[row];
rows_length_new[row] = ps->rows_length[row];
ps->rows[row] = NULL;
for (crr_insn = rows_new[row];
@@ -2315,6 +2322,7 @@ ps_insert_empty_row (partial_schedule_pt
for (row = split_row; row < ii; row++)
{
rows_new[row + 1] = ps->rows[row];
+ rows_reverse_new[row + 1] = ps->rows_reverse[row];
rows_length_new[row + 1] = ps->rows_length[row];
ps->rows[row] = NULL;
for (crr_insn = rows_new[row + 1];
@@ -2337,6 +2345,8 @@ ps_insert_empty_row (partial_schedule_pt
+ (SMODULO (ps->max_cycle, ii) >= split_row ? 1 : 0);
free (ps->rows);
ps->rows = rows_new;
+ free (ps->rows_reverse);
+ ps->rows_reverse = rows_reverse_new;
free (ps->rows_length);
ps->rows_length = rows_length_new;
ps->ii = new_ii;
@@ -2428,6 +2438,9 @@ verify_partial_schedule (partial_schedul
popcount (sched_nodes) == number of insns in ps. */
gcc_assert (SCHED_TIME (u) >= ps->min_cycle);
gcc_assert (SCHED_TIME (u) <= ps->max_cycle);
+ if (ps->rows_length[row] == length)
+ gcc_assert (ps->rows_reverse[row] == crr_insn);
+
}
gcc_assert (ps->rows_length[row] == length);
@@ -2837,6 +2850,7 @@ create_partial_schedule (int ii, ddg_ptr
{
partial_schedule_ptr ps = XNEW (struct partial_schedule);
ps->rows = (ps_insn_ptr *) xcalloc (ii, sizeof (ps_insn_ptr));
+ ps->rows_reverse = (ps_insn_ptr *) xcalloc (ii, sizeof (ps_insn_ptr));
ps->rows_length = (int *) xcalloc (ii, sizeof (int));
ps->reg_moves = NULL;
ps->ii = ii;
@@ -2885,6 +2899,7 @@ free_partial_schedule (partial_schedule_
free_ps_insns (ps);
free (ps->rows);
+ free (ps->rows_reverse);
free (ps->rows_length);
free (ps);
}
@@ -2903,6 +2918,9 @@ reset_partial_schedule (partial_schedule
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_reverse = (ps_insn_ptr *) xrealloc (ps->rows_reverse, new_ii
+ * sizeof (ps_insn_ptr));
+ memset (ps->rows_reverse, 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;
@@ -2960,6 +2978,15 @@ remove_node_from_ps (partial_schedule_pt
gcc_assert (ps && ps_i);
row = SMODULO (ps_i->cycle, ps->ii);
+
+ if (! ps_i->next_in_row)
+ {
+ if (ps_i->prev_in_row)
+ ps->rows_reverse[row] = ps_i->prev_in_row;
+ else
+ ps->rows_reverse[row] = NULL;
+ }
+
if (! ps_i->prev_in_row)
{
gcc_assert (ps_i == ps->rows[row]);
@@ -3048,6 +3075,8 @@ ps_insn_find_column (partial_schedule_pt
}
else
ps->rows[row] = ps_i;
+
+ ps->rows_reverse[row] = ps_i;
return true;
}
@@ -3070,6 +3099,9 @@ ps_insn_find_column (partial_schedule_pt
ps_i->next_in_row->prev_in_row = ps_i;
}
+ if (! ps_i->next_in_row)
+ ps->rows_reverse[row] = ps_i;
+
return true;
}
@@ -3116,6 +3148,9 @@ ps_insn_advance_column (partial_schedule
if (prev)
prev->next_in_row = next;
+ if (ps_i->next_in_row == NULL)
+ ps->rows_reverse[row] = ps_i;
+
return true;
}
@@ -3298,14 +3333,17 @@ rotate_partial_schedule (partial_schedul
for (i = 0; i < backward_rotates; i++)
{
ps_insn_ptr first_row = ps->rows[0];
+ ps_insn_ptr rows_reverse = ps->rows_reverse[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_reverse[row] = ps->rows_reverse[row + 1];
ps->rows_length[row] = ps->rows_length[row + 1];
}
+ ps->rows_reverse[last_row] = rows_reverse;
ps->rows[last_row] = first_row;
ps->rows_length[last_row] = first_row_length;
}
