+/* This function inserts a new empty row into PS at the position
+ according to SPLITROW, keeping all already scheduled instructions
+ intact and updating their SCHED_TIME and cycle accordingly. */
+static void
+ps_insert_empty_row (partial_schedule_ptr ps, int split_row,
+ sbitmap sched_nodes)
+{
+ ps_insn_ptr crr_insn;
+ ps_insn_ptr *rows_new;
+ int ii = ps->ii;
+ int new_ii = ii + 1;
+ int row;
+
+ verify_partial_schedule (ps, sched_nodes);
+
+ /* We normalize sched_time and rotate ps to have only non-negative sched
+ times, for simplicity of updating cycles after inserting new row. */
+ split_row -= ps->min_cycle;
+ split_row = SMODULO (split_row, ii);
+ if (dump_file)
+ fprintf (dump_file, "split_row=%d\n", split_row);
+
+ normalize_sched_times (ps);
+ rotate_partial_schedule (ps, ps->min_cycle);
+
+ rows_new = (ps_insn_ptr *) xcalloc (new_ii, sizeof (ps_insn_ptr));
+ for (row = 0; row < split_row; row++)
+ {
+ rows_new[row] = ps->rows[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 new_time = SCHED_TIME (u) + (SCHED_TIME (u) / ii);
+
+ SCHED_TIME (u) = new_time;
+ crr_insn->cycle = new_time;
+ SCHED_ROW (u) = new_time % new_ii;
+ SCHED_STAGE (u) = new_time / new_ii;
+ }
+
+ }
+
+ rows_new[split_row] = NULL;
+
+ for (row = split_row; row < ii; row++)
+ {
+ rows_new[row + 1] = ps->rows[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 new_time = SCHED_TIME (u) + (SCHED_TIME (u) / ii) + 1;
+
+ SCHED_TIME (u) = new_time;
+ crr_insn->cycle = new_time;
+ SCHED_ROW (u) = new_time % new_ii;
+ SCHED_STAGE (u) = new_time / new_ii;
+ }
+ }
+
+ /* Updating ps. */
+ ps->min_cycle = ps->min_cycle + ps->min_cycle / ii
+ + (SMODULO (ps->min_cycle, ii) >= split_row ? 1 : 0);
+ ps->max_cycle = ps->max_cycle + ps->max_cycle / ii
+ + (SMODULO (ps->max_cycle, ii) >= split_row ? 1 : 0);
+ free (ps->rows);
+ ps->rows = rows_new;
+ ps->ii = new_ii;
+ gcc_assert (ps->min_cycle >= 0);
+
+ verify_partial_schedule (ps, sched_nodes);
+
+ if (dump_file)
+ fprintf (dump_file, "min_cycle=%d, max_cycle=%d\n", ps->min_cycle,
+ ps->max_cycle);
+}
+
+/* Given U_NODE which is the node that failed to be scheduled; LOW and
+ UP which are the boundaries of it's scheduling window; compute using
+ SCHED_NODES and II a row in the partial schedule that can be split
+ which will separate a critical predecessor from a critical successor
+ thereby expanding the window, and return it. */
+static int
+compute_split_row (sbitmap sched_nodes, int low, int up, int ii,
+ ddg_node_ptr u_node)
+{
+ 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_cycle;
+
+ for (e = u_node->in; e != 0; e = e->next_in)
+ {
+ ddg_node_ptr v_node = e->src;
+
+ if (TEST_BIT (sched_nodes, v_node->cuid)
+ && (low == SCHED_TIME (v_node) + e->latency - (e->distance * ii)))
+ if (SCHED_TIME (v_node) > lower)
+ {
+ crit_pred = v_node;
+ lower = SCHED_TIME (v_node);
+ }
+ }
+
+ if (crit_pred != NULL)
+ {
+ 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)
+ {
+ crit_succ = v_node;
+ upper = SCHED_TIME (v_node);
+ }
+ }
+
+ if (crit_succ != NULL)
+ {
+ crit_cycle = SCHED_TIME (crit_succ);
+ return SMODULO (crit_cycle, ii);
+ }
+
+ if (dump_file)
+ fprintf (dump_file, "Both crit_pred and crit_succ are NULL\n");
+
+ return SMODULO ((low + up + 1) / 2, ii);
+}
+
+static void
+verify_partial_schedule (partial_schedule_ptr ps, sbitmap sched_nodes)
+{
+ int row;
+ 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);
+ }
+}
+