Implementing Swing Modulo Scheduling in GCC - continued

[Ayal Zaks]

Canqun>  /* The resource reservation length of this insn?  */
Canqun>  /* latency = insn_latency (u);*/
Mostafa> future = c + insn_latency(u);

Reservation lengths (involving potential resource conflicts) should
not be mixed with latencies (that involve dependences). It should be

future = c + MAX_RESERVATION_LENGTH;
or, if available,
future = c + MAX_RESERVATION_LENGTH (u);

This will basically get you to the same algorithm Vlad provided in:
http://gcc.gnu.org/ml/gcc/2003-10/msg00062.html
(at least it should) without constructing the trace expicitely.


>/*In the case of several insns that go to the same cycle
>  you must take the maximum latency among all of them.  */

We may have a problem if insns are free to move within
their issued cycle, having DFA "alternatives". If an insn has several
possible alternatives from which the DFA is free to select, then
it may choose differently when checking a slightly modified trace.
Adding one insn u to a certain cycle c may cause the DFA to select
a different alternative for some insn w say sometime after cycle c,
and this can start a (time-unbounded) chain reaction.
If this is true (and I'm not mixing NDFA with DFA behavior), I see the
following options:
1. Disregard the potential for conflicts after MAX_RESERVATION_LENGTH,
   knowning that the kernel might contain potential conflicts (which
   is ok for PowerPC). In this case, taking the max of MAX_RESERVATION_
   LENGTHS over the insns of the cycle is somewhat safer.
2. Force the DFA to stick with the alternative it chooses for each insn
   at the time it is scheduled.
3. Use an alternative-free DFA model; note that such a model might fail
   to capture potential conflicts, as it is a relaxation of the general
   alternative-full model. So we're back to -
   knowning that the kernel might contain potential conflicts.

So having alternatives posses some challenges to the support of "can an
insn be scheduled at a given cycle/slot?", not only to MII computation.

A related question is whether, when checking if insn u can be scheduled
at cycle c, given that insns v & w have already been scheduled there,
do we check all possible orders within the cycle? - (u,v,w), (v,u,w),
(v,w,u); should we also try to swap v & w and check all permutations?
This might relate to multipass_dfa_lookahead.

Ayal.