Hi Richard, 2011/8/4 Richard Sandiford <richard.sandif...@linaro.org> > > Hi Ayal, > > Thanks to you and Revital for the replies. The reason I asked is that > I wanted to rewrite gen_sched_window so that it has only one loop over > the PSPs and one loop over the PSSs.
This rewrite makes perfect sense regardless of any follow-up patches, as it clarifies and reuses code. > > I have a follow-up patch to use > iv analysis to reduce the number of memory dependencies (or at least > increase the distance between them), and it was easier to do that > after this change. Reducing memory dependencies is definitely important. > > Ayal Zaks <ayal.z...@gmail.com> writes: > >>> I ask because in the final range: > >>> > >>> start = early_start; > >>> end = MIN (end, early_start + ii); > >>> /* Schedule the node close to it's predecessors. */ > >>> step = 1; > >>> > >>> END is an exclusive bound. It seems like we might be double-counting > > here, > >>> and effectively limiting the schedule to SCHED_TIME (v_node) + ii - 2. > >> > >> > >>Yes, I think it indeed should be fixed. Thanks for reporting on this. > >> > >>Revital > > > > Agreed; > > > > if (e->data_type == MEM_DEP) > > end = MIN (end, SCHED_TIME (v_node) + ii - > > 1); > > > > should be replaced with > > > > if (e->data_type == MEM_DEP) > > end = MIN (end, p_st + ii); > > > > also for the (3rd) case when there are both previously-scheduled > > predessors and previously-scheduled successors. The range is inclusive > > of start and exclusive of end: for (c = start; c != end; c += step)... > > OK. For the follow-on iv patch, it seemed easier to keep both bounds > inclusive for the loop, then make the "end" exclusive when setting the > out parameters. (Note that there shouldn't be any problem with overflow > when making the bound exclusive, because the size of the range has been > restricted to "ii" by that stage. The follow-on patch does use > saturating maths for all ops though.) Sure, no problem having "end" inclusive, as it simplifies things. We can even keep it inclusive all the way through, iterating over: for (c = start; c != end+step; c += step)... > > >>This doesn't seem to be in the paper, and the comment suggests > >>"count_succs > count_preds" rather than "count_succs >= count_preds". > >>Is the ">=" vs ">" important? > > > > I think not: in both cases you'll be trying to minimize the same > > number of live ranges. But indeed it's good to be consistent with the > > comment. > > OK. For no particular reason other than cowardice, I ended up keeping > this as: > > ! if (count_succs && count_succs >= count_preds) > > The reason for asking was that: > > ! if (count_succs > count_preds) > > seemed more natural, and would match the existing comment. I'm happy > to test that instead if you prefer. > I wouldn't worry about this tie breaker, unless there's a reason (in which case the reason should hopefully provide a secondary criteria). > > I don't have powerpc hardware that I can do meaningful performance > testing on, but I did run it through a Popular* Embedded Benchmark > on an ARM Cortex-A8 board with -O3 -fmodulo-sched > -fmodulo-sched-allow-regmoves. There were no changes. (And this is > a benchmark that does benefit from modulo scheduling, in some cases > by a significant amount.) > Ok, the patch should be neutral performance-wise. One could check btw if SMS produces exactly the same output in both cases, even w/o a powerpc (or any other) HW. > > Bootstrapped & regression-tested on powerpc-ibm-aix5.3 with the > additional patch: > > Index: gcc/opts.c > =================================================================== > --- gcc/opts.c 2011-08-03 10:56:50.000000000 +0100 > +++ gcc/opts.c 2011-08-03 10:56:50.000000000 +0100 > @@ -449,6 +449,8 @@ static const struct default_options defa > { OPT_LEVELS_1_PLUS, OPT_ftree_ch, NULL, 1 }, > { OPT_LEVELS_1_PLUS, OPT_fcombine_stack_adjustments, NULL, 1 }, > { OPT_LEVELS_1_PLUS, OPT_fcompare_elim, NULL, 1 }, > + { OPT_LEVELS_1_PLUS, OPT_fmodulo_sched, NULL, 1 }, > + { OPT_LEVELS_1_PLUS, OPT_fmodulo_sched_allow_regmoves, NULL, 1 }, > > /* -O2 optimizations. */ > { OPT_LEVELS_2_PLUS, OPT_finline_small_functions, NULL, 1 }, > > applied for both the "before" and "after" runs. OK to install? Yes, with just a couple of minor non-mandatory comments: 1. Setting "count_preds = psp_not_empty;" and "count_succs = pss_not_empty;" suggests that you want to decrement non-interesting neighbors instead of incrementing interesting ones. Otherwise can initialize to zero (doesn't really matter, just a bit confusing). 2. I find it easier to read "late_start = MIN (late_start, early_start + (ii - 1));" instead of "late_start = MIN (early_start + (ii - 1), late_start);". 3. Suggest to set step=1 at the beginning, explaining from the start that we first compute a forward range (start<end), and may later possibly revert it. 4. "late_start" would better be renamed "late_end". 5. While we're at it, as you've unified the treatments, we can now actually do with "start" and "end" only, and do away with early_start and late_start altogether... Thanks, Ayal. > > Thanks, > Richard > > > gcc/ > * modulo-sched.c (get_sched_window): Use just one loop for predecessors > and one loop for successors. Fix upper bound of memory range. > > Index: gcc/modulo-sched.c > =================================================================== > *** gcc/modulo-sched.c 2011-08-04 09:09:29.000000000 +0100 > --- gcc/modulo-sched.c 2011-08-04 09:49:16.000000000 +0100 > *************** #define MAX_SPLIT_NUM 10 > *** 1630,1638 **** > > 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) > { > int start, step, end; > ddg_edge_ptr e; > sbitmap psp = sbitmap_alloc (ps->g->num_nodes); > sbitmap pss = sbitmap_alloc (ps->g->num_nodes); > --- 1630,1640 ---- > > 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) > { > 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); > *************** get_sched_window (partial_schedule_ptr p > *** 1640,1645 **** > --- 1642,1649 ---- > 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); > *************** get_sched_window (partial_schedule_ptr p > *** 1647,1861 **** > 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)); > ! } > ! > ! 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); > > ! } > > ! 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); > ! > ! 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->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"); > > ! } > ! 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 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 (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->type == TRUE_DEP && e->data_type == REG_DEP) > ! count_succs++; > > ! 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"); > > ! } > ! 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; > > ! start = end - 1; > ! end = old_start - 1; > ! step = -1; > ! } > ! } > ! else /* psp is empty && pss is empty. */ > ! { > ! start = SCHED_ASAP (u_node); > ! end = start + ii; > ! step = 1; > } > > *start_p = start; > *step_p = step; > *end_p = end; > --- 1651,1769 ---- > 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); > > ! early_start = INT_MIN; > ! late_start = INT_MAX; > ! start = INT_MIN; > ! end = INT_MAX; > ! count_preds = psp_not_empty; > ! count_succs = pss_not_empty; > ! > ! /* 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, "\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 (e->data_type == MEM_DEP) > ! end = MIN (end, p_st + ii - 1); > > ! if (e->type == TRUE_DEP && e->data_type == REG_DEP) > ! count_preds++; > > ! if (dump_file) > fprintf (dump_file, > ! "pred st = %d; early_start = %d; latency: %d;" > ! " end: %d\n", p_st, early_start, e->latency, end); > > ! } > ! 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) > ! { > ! 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 (e->data_type == MEM_DEP) > ! start = MAX (start, s_st - ii + 1); > > ! 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;" > ! " start=%d", s_st, late_start, e->latency, start); > > ! } > ! 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 (early_start + (ii - 1), late_start); > ! > ! /* Apply memory dependence limits. */ > ! start = MAX (start, early_start); > ! end = MIN (end, late_start); > ! step = 1; > ! > ! /* If there are at least as many successors as predecessors, schedule the > ! node close to its successors. */ > ! if (count_succs && count_succs >= count_preds) > ! { > ! 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; > *************** get_sched_window (partial_schedule_ptr p > *** 1867,1876 **** > if (dump_file) > fprintf (dump_file, "\nEmpty window: start=%d, end=%d, step=%d\n", > start, end, step); > ! return -1; > } > > ! return 0; > } > > /* Calculate MUST_PRECEDE/MUST_FOLLOW bitmaps of U_NODE; which is the > --- 1775,1784 ---- > if (dump_file) > fprintf (dump_file, "\nEmpty window: start=%d, end=%d, step=%d\n", > start, end, step); > ! return -1; > } > > ! return 0; > } > > /* Calculate MUST_PRECEDE/MUST_FOLLOW bitmaps of U_NODE; which is the