Re: [RFC][modulo-sched] Fix scheduling order within a cycle

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

Revital1 Eres/Haifa/IBM wrote on 14/11/2007 18:46:14:

>
> >
> > When scheduling insn 58, we calculate a window of possible cycles
according
> > to already scheduled predecessors and successors. This window looks
like a
> > parallelogram in general rather than a rectangle: in the first cycle
there
> > may be predecessors (already scheduled in the first cycle, or a
multiple of
> > II cycles away) which must_preceed insn 58 (having tight dependence
with
> > insn 58 if it is placed in the first cycle). So insn 58 can be placed
in
> > 'rightmost' slots of the first cycle only. Similarly, in the last
cycle,
> > insn 58 might be placed in 'leftmost' slots only, due to successors
which
> > must_follow insn 58. Inside internal cycles (strictly between first and
> > last cycles), insn 58 can be placed in any vacant slot.
> >
> > Now if (as in the above case) an already scheduled insn 61 is both a
> > successor and a predecessor of insn 58, it may be that (not it the
above
> > case) insn 61 must_precede insn 58 (when looking for available slots
for
> > insn 58 in the first cycle) and must_follow insn 58 (when looking for
> > available slots in the last cycle).
> >
> > Currently we apply the must_precede and must_follow restrictions to all
> > cycles of the window. This is overly conservative (i.e., should not
produce
> > above wrong code!). One way to improve this is to split the window into
> > first cycle (with must_precede), internal part (with neither
must_precede
> > nor must_follow), and last cycle (with must_follow). And, of-course, if
> > first cycle == last cycle, apply both must_precede and must_follow for
it.
> >
> >
> > Finally, note that in the above case we traverse the window backwards
with
> > step -1, so 'start' is the last cycle 4, and 'end' is one past the
first
> > cycle 0 (i.e. -1).
>
> Thanks for the explanation!  Is it reasonable to conclude that for the
> must_follow/must_precede calculation we should not relay on start/end
> rows (as they are influenced from the direction of the window); but
> use win_boundary_close_to_preds row and win_boundary_close_to_succs
> row, calculated from start and ends rows depending on the direction
> of the window (if step is 1 than in_boundery_close_to_preds
> = start; if step is -1 than  in_boundary_close_to_preds = end, etc).
> win_boundary_close_to_preds will be used only for must_precede
calculation
> and win_boundary_close_to_succs row will be used only for must_follow
> as you described above.
>

One way to do this is inside the

for (c = start; c != end; c += step)
  {
    verify_partial_schedule (ps, sched_nodes);

    psi = ps_add_node_check_conflicts (ps, u_node, c,
                                       must_precede,
                                       must_follow);
...

loop, set:

    tmp_precede = zero bitmap
    tmp_follow = zero bitmap
    if (c == start)
      if (step == 1)
        tmp_precede = must_precede;
      else /* step == -1.  */
        tmp_follow = must_follow;
    if (c == end - step)
      if (step == 1)
        tmp_follow = must_follow;
      else /* step == -1.  */
        tmp_precede = must_precede;

and then call
    psi = ps_add_node_check_conflicts (ps, u_node, c,
                                       tmp_precede,
                                       tmp_follow);


Ayal.

> Thanks,
> Revital