This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH][modulo-sched] Revisit order of insns within a row
- From: Ayal Zaks <ZAKS at il dot ibm dot com>
- To: Revital1 Eres <ERES at il dot ibm dot com>
- Cc: "Andrey Belevantsev" <abel at ispras dot ru>, "Alexander Monakov" <amonakov at ispras dot ru>, gcc-patches at gcc dot gnu dot org
- Date: Fri, 4 Jan 2008 00:49:13 +0200
- Subject: Re: [PATCH][modulo-sched] Revisit order of insns within a row
Revital1 Eres/Haifa/IBM wrote on 30/12/2007 15:28:11:
> Hello,
>
> When two dependent insns are scheduled in the same row; which is the
> first/last row of their scheduling window; they are currently ordered
> according to their dependency (i.e. if x -> y then x will precede y in
> the row).
>
> The following example demonstrates why imposing an order on two dependent
> insns based on the fact that they are scheduled in the same row is a
> conservative approach:
>
> Consider the following two insns which are scheduled in the same cycle C
> (and thus in the same row):
>
> insn 1) a[i+2] = rhs
> insn 2) lhs = a[i]
>
> The producer of insn 2 is insn a[i] = rhs which appears in cycle:
> C - 2 * II. Thus the order of insn 1 and insn 2 in the row is
> not important.
>
> The attached patch changes this approach by imposing an order between two
> dependent insns only if the producer and the consumer are been scheduled
> in the same cycle (and thus in the same row). This happens when the
> latency between them is zero.
>
> Tested on powerpc64-linux and SPU. OK for 4.4?
>
Yes, with the documentation comments below.
> :ADDPATCH modulo-sched:
>
> Thanks,
> Revital
>
> 2007-12-30 Ayal Zaks <zaks@il.ibm.com>
> Revital Eres <eres@il.ibm.com>
>
> * modulo-sched.c (calculate_must_precede_follow): Address TODO
> regarding the order of two dependent insns in the same row.
>
> attachment "patch_27_12_todo.txt:
>
> Index: modulo-sched.c
> ===================================================================
> --- modulo-sched.c (revision 131150)
> +++ modulo-sched.c (working copy)
> @@ -1587,18 +1587,17 @@
>
> /* Calculate MUST_PRECEDE/MUST_FOLLOW bitmaps of U_NODE; which is the
> node currently been scheduled. At the end of the calculation
> - MUST_PRECEDE/MUST_FOLLOW contains all predecessors/successors of
U_NODE
> - which are in SCHED_NODES (already scheduled nodes) and scheduled at
> - the same row as the first/last row of U_NODE's scheduling window.
> + MUST_PRECEDE/MUST_FOLLOW contains all predecessors/successors of.
> + U_NODE which are in SCHED_NODES (already scheduled nodes) and have
> + tight dependence to U which indicates that a producer and a consumer
> + with distance and latency zero are both scheduled in the same cycle
> + (and thus in the same row) as the first/last cycle of U_NODE's
> + scheduling window.
This last sentence is hard to follow (or precede ;-). Suggest something
like:
/* Calculate MUST_PRECEDE/MUST_FOLLOW bitmaps of U_NODE; which is the
node currently been scheduled. At the end of the calculation
- MUST_PRECEDE/MUST_FOLLOW contains all predecessors/successors of U_NODE
- which are in SCHED_NODES (already scheduled nodes) and scheduled at
- the same row as the first/last row of U_NODE's scheduling window.
+ MUST_PRECEDE/MUST_FOLLOW contains all predecessors/successors of.
+ U_NODE which are (1) already scheduled in the first/last row of
U_NODE's
+ scheduling window, (2) whose dependence inequality with U becomes an
+ equality when U is scheduled in this same row, and (3) whose dependence
+ latency is zero.
> The first and last rows are calculated using the following
paramaters:
> START/END rows - The cycles that begins/ends the traversal on the
window;
> searching for an empty cycle to schedule U_NODE.
> STEP - The direction in which we traverse the window.
> - II - The initiation interval.
> - TODO: We can add an insn to the must_precede/must_follow bitmap only
> - if it has tight dependence to U and they are both scheduled in the
> - same row. The current check is more conservative and content with
> - the fact that both U and the insn are scheduled in the same row. */
> + II - The initiation interval. */
>
> static void
> calculate_must_precede_follow (ddg_node_ptr u_node, int start, int end,
> @@ -1607,7 +1606,6 @@
> {
> ddg_edge_ptr e;
> int first_cycle_in_window, last_cycle_in_window;,
> - int first_row_in_window, last_row_in_window;
>
> gcc_assert (must_precede && must_follow);
>
> @@ -1621,9 +1619,6 @@
> first_cycle_in_window = (step == 1) ? start : end - step;
> last_cycle_in_window = (step == 1) ? end - step : start;;
>
> - first_row_in_window = SMODULO (first_cycle_in_window, ii);
> - last_row_in_window = SMODULO (last_cycle_in_window, ii);
> -
> sbitmap_zero (must_precede);
> sbitmap_zero (must_follow);;
>
> @@ -1632,7 +1627,8 @@
>
> for (e = u_node->in; e != 0; e = e->next_in)
> if (TEST_BIT (sched_nodes, e->src->cuid)
> - && (SMODULO (SCHED_TIME (e->src), ii) == first_row_in_window))
Please add comment such as:
+ /* Instead of checking if
+ SMODULO (SCHED_TIME (e->src), ii) == first_row_in_window
+ && (SCHED_TIME (e->src) + e->latency - (e->distance * ii)) ==
+ first_cycle_in_window>
+ && e->latency == 0
+ we use the fact that latency is non-negative:>
+ SCHED_TIME (e->src) - (e->distance * ii) <=
+ SCHED_TIME (e->src) + e->latency - (e->distance * ii)) <=)
+ first_cycle_in_window
+ and check only if
+ SCHED_TIME (e->src) - (e->distance * ii) == first_cycle_in_window
+ */
> + && ((SCHED_TIME (e->src) - (e->distance * ii)) ==
> + first_cycle_in_window))
> {
> if (dump_file)
> fprintf (dump_file, "%d ", e->src->cuid);
> @@ -1645,7 +1641,8 @@
>
> for (e = u_node->out; e != 0; e = e->next_out)
> if (TEST_BIT (sched_nodes, e->dest->cuid)
> - && (SMODULO (SCHED_TIME (e->dest), ii) == last_row_in_window))
> + && ((SCHED_TIME (e->dest) + (e->distance * ii)) ==
> + last_cycle_in_window))
ditto.
Ayal..
> {
> if (dump_file)
> fprintf (dump_file, "%d ", e->dest->cuid);