Re: [PATCH][modulo-sched] Revisit order of insns within a row

[Ayal Zaks <ZAKS at il dot ibm dot com>]

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);