From fe43febc8cbcff3a69f17934b501ca55bb30ac8b Mon Sep 17 00:00:00 2001 From: Richard Sandiford Date: Mon, 8 Aug 2011 09:26:54 +0000 Subject: [PATCH] modulo-sched.c (get_sched_window): Use just one loop for predecessors and one loop for successors. gcc/ * modulo-sched.c (get_sched_window): Use just one loop for predecessors and one loop for successors. Fix upper bound of memory range. From-SVN: r177555 --- gcc/ChangeLog | 5 + gcc/modulo-sched.c | 287 ++++++++++++++++----------------------------- 2 files changed, 104 insertions(+), 188 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 7389883248e..495227fe1a5 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,8 @@ +2011-08-08 Richard Sandiford + + * modulo-sched.c (get_sched_window): Use just one loop for predecessors + and one loop for successors. Fix upper bound of memory range. + 2011-08-06 Uros Bizjak PR target/50001 diff --git a/gcc/modulo-sched.c b/gcc/modulo-sched.c index a6d941019fb..e3dc3aa6917 100644 --- a/gcc/modulo-sched.c +++ b/gcc/modulo-sched.c @@ -1630,9 +1630,11 @@ sms_schedule (void) static int 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) + 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; sbitmap psp = sbitmap_alloc (ps->g->num_nodes); sbitmap pss = sbitmap_alloc (ps->g->num_nodes); @@ -1640,6 +1642,8 @@ get_sched_window (partial_schedule_ptr ps, ddg_node_ptr 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); @@ -1647,215 +1651,122 @@ get_sched_window (partial_schedule_ptr ps, ddg_node_ptr u_node, 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; - - 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)); - } - - 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) - { - 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)); - } + /* 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; - if (TEST_BIT (sched_nodes, v_node->cuid)) - { - int s_st = SCHED_TIME (v_node); + count_preds = 0; + count_succs = 0; - late_start = MIN (late_start, - s_st - e->latency + (e->distance * ii)); + /* 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) + { + ddg_node_ptr v_node = e->src; - if (dump_file) - fprintf (dump_file, - "succ st = %d; late_start = %d; latency = %d", - s_st, late_start, e->latency); + 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)); + } - 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); + if (TEST_BIT (sched_nodes, v_node->cuid)) + { + int p_st = SCHED_TIME (v_node); - } - else if (dump_file) - fprintf (dump_file, "the node is not scheduled\n"); + early_start = MAX (early_start, + p_st + e->latency - (e->distance * ii)); - } - start = late_start; - end = MAX (end, late_start - ii); - /* Schedule the node close to it's successors. */ - step = -1; + if (e->data_type == MEM_DEP) + end = MIN (end, p_st + ii - 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); + if (e->type == TRUE_DEP && e->data_type == REG_DEP) + count_preds++; - } - - 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); + if (dump_file) 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); - - early_start = MAX (early_start, - p_st + e->latency - - (e->distance * ii)); + "pred st = %d; early_start = %d; latency: %d;" + " end: %d\n", p_st, early_start, e->latency, end); - if (dump_file) - fprintf (dump_file, - "pred st = %d; early_start = %d; latency = %d", - p_st, early_start, e->latency); + } + else if (dump_file) + fprintf (dump_file, "the node is not scheduled\n"); + } - if (e->type == TRUE_DEP && e->data_type == REG_DEP) - count_preds++; + /* 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) + { + ddg_node_ptr v_node = e->dest; - 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"); + 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)); + } - } - 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)) + { + int s_st = SCHED_TIME (v_node); - 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)); - } + late_start = MIN (late_start, + s_st - e->latency + (e->distance * ii)); - if (TEST_BIT (sched_nodes, v_node->cuid)) - { - int s_st = SCHED_TIME (v_node); + if (e->data_type == MEM_DEP) + start = MAX (start, s_st - ii + 1); - 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) + fprintf (dump_file, + "succ st = %d; late_start = %d; latency = %d;" + " start=%d", s_st, late_start, e->latency, start); - if (e->type == TRUE_DEP && e->data_type == REG_DEP) - count_succs++; + } + else if (dump_file) + fprintf (dump_file, "the node is not scheduled\n"); + } - 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"); + /* Get a target scheduling window no bigger than ii. */ + if (early_start == INT_MIN && late_start == INT_MAX) + early_start = SCHED_ASAP (u_node); + else if (early_start == INT_MIN) + early_start = late_start - (ii - 1); + late_start = MIN (late_start, early_start + (ii - 1)); - } - 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; + /* Apply memory dependence limits. */ + start = MAX (start, early_start); + end = MIN (end, late_start); - 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; @@ -1867,10 +1778,10 @@ get_sched_window (partial_schedule_ptr ps, ddg_node_ptr u_node, 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 -- 2.30.2